背包問題（貪心）
最優(yōu)裝載問題
題目描述
有n件物品和一個(gè)最大承重為w 的背包。第i件物品的重量是weight[i]，每件只能用一次，求裝入背包的最多物品數(shù)量。
題目分析
- 因?yàn)槲覀?strong>只要求裝入物品的數(shù)量，所以裝重的顯然沒有裝輕的劃算。
- 因此將數(shù)組weight[i]按從小到大排序，依次選擇每個(gè)物品，直到裝不下為止，就可以得到裝入背包的最多物品數(shù)量。
代碼
public static int stone(int n, int w, int[] weight) {
Arrays.sort(weight); //將weight數(shù)組從小到大排序
int max = 0;
int num = 0;
for(int i = 0; i < n; i++) {
if(max + weight[i] <= w){
max += weight[i];
num += 1;
}
}
return num;
}
01背包問題
與上面的貪心背包問題而言，貪心背包問題中物品的價(jià)值就是它的重量。
先前題主做的拿金幣問題，也可以說是一道背包問題，不過其中背包的容量是無限的，物品就是金幣。
題目描述
有n件物品和一個(gè)最大承重為bagweight 的背包。第i件物品的重量是weight[i]，得到的價(jià)值是value[i] 。每件物品只能用一次，求解將哪些物品裝入背包里物品價(jià)值總和最大。
卡碼網(wǎng)第46題
題目分析
顯然也是一道動態(tài)規(guī)劃題，也就是說背包問題是動態(tài)規(guī)劃問題的子集，當(dāng)然這不重要。
我們先觀察一下背包的屬性：
- 當(dāng)前裝入物品的個(gè)數(shù)
- 當(dāng)前裝入物品的總重量（容量）
- 當(dāng)前裝入物品的總價(jià)值
- 關(guān)鍵在當(dāng)前重量的基礎(chǔ)上使得價(jià)值最高
注：下文基本轉(zhuǎn)述于代碼隨想錄的網(wǎng)站，只加了部分自己的理解
可轉(zhuǎn)到代碼隨想錄的網(wǎng)站去更深刻地理解01背包知識
代碼隨想錄的鏈接：戳這里進(jìn)入
老規(guī)矩動歸五部曲
定義dp數(shù)組
定義一個(gè)二維數(shù)組dp[i][j]，將i定義為當(dāng)前放入了多少個(gè)物品，表示
- 從下標(biāo)為[0-i]的物品里任意取，
- 放進(jìn)容量為j的背包，
- 價(jià)值總和最大是多少。（dp數(shù)組的值）
確定dp數(shù)組遞歸公式
在決定是否放入第i個(gè)物品時(shí)，顯然有兩種情況
- 要么不滿足放入第i個(gè)物品的情況（當(dāng)物品i的重量大于背包j的重量時(shí)，物品i無法放進(jìn)背包中）
dp[i][j] = dp[i-1][j];
- 要么滿足放入第i個(gè)物品的情況，此時(shí)比較放入前后的價(jià)值總和，判斷是否要放入。
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - weight[i] + value[i];
dp數(shù)組的初始化
從dp[i][j]出發(fā)，
- 當(dāng)背包容量j為0的時(shí)候，則放不下任何物品，背包中價(jià)值總和為0；
for (int i = 0 ; i < weight.length; i++) {
dp[1][0] = 0;
再看其他情況。文章來源：http://www.zghlxwxcb.cn/news/detail-798527.html
- 因?yàn)檫f推公式dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
當(dāng)中含有i-1，即我們在遍歷時(shí)肯定從i=1的時(shí)候開始遍歷，那么物品為0的時(shí)候就一定要初始化。
此時(shí)考慮是否可以加入物品0，- 當(dāng) j < weight[0]的時(shí)候，dp[0][j] 為 0
- 當(dāng)j >= weight[0]時(shí)，dp[0][j] 為value[0]
for (int j = 0 ; j < weight[0]; j++) // 如果把dp數(shù)組預(yù)先初始化為0了，這一步可以省略
dp[0][j] = 0;
for (int j = weight[0]; j <= bagweight; j++)
dp[0][j] = value[0];
- 其他位置可以任意初始化，但是一開始就統(tǒng)一把dp數(shù)組統(tǒng)一初始為0，更方便一些。
dp數(shù)組的遍歷順序
顯然有兩個(gè)遍歷的維度：物品與背包容量
先遍歷物品，或先遍歷背包容量呢。
這里兩種遍歷順序都可以，是因?yàn)?，遞推的方向分別是由上得到與由左得到，而兩個(gè)遍歷順序都是會先得到遞推公式需要的舊數(shù)據(jù)，因此不影響。文章來源地址http://www.zghlxwxcb.cn/news/detail-798527.html
//先遍歷物品
for(int i = 1; i < weight.size(); i++) { // 遍歷物品
for(int j = 0; j <= bagweight; j++) { // 遍歷背包容量
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
//先遍歷背包容量
for(int j = 0; j <= bagweight; j++) { // 遍歷背包容量
for(int i = 1; i < weight.size(); i++) { // 遍歷物品
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
舉例說明dp數(shù)組
代碼
import java.util.Arrays;
public class BagProblem {
public static void main(String[] args) {
int[] weight = {1,3,4};//這里是代碼隨想錄的示范用例
int[] value = {15,20,30};
int bagSize = 4;
testWeightBagProblem(weight,value,bagSize);
}
public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
// 創(chuàng)建dp數(shù)組
int goods = weight.length; // 獲取物品的數(shù)量
int[][] dp = new int[goods + 1][bagSize + 1]; // 給物品增加冗余維，i = 0 表示沒有物品可選
// 初始化dp數(shù)組，默認(rèn)全為0即可
// 填充dp數(shù)組
for (int i = 1; i <= goods; i++) {
for (int j = 1; j <= bagSize; j++) {
if (j < weight[i - 1]) { // i - 1 對應(yīng)物品 i
/**
* 當(dāng)前背包的容量都沒有當(dāng)前物品i大的時(shí)候，是不放物品i的
* 那么前i-1個(gè)物品能放下的最大價(jià)值就是當(dāng)前情況的最大價(jià)值
*/
dp[i][j] = dp[i - 1][j];
} else {
/**
* 當(dāng)前背包的容量可以放下物品i
* 那么此時(shí)分兩種情況：
* 1、不放物品i
* 2、放物品i
* 比較這兩種情況下，哪種背包中物品的最大價(jià)值最大
*/
dp[i][j] = Math.max(dp[i - 1][j] , dp[i - 1][j - weight[i - 1]] + value[i - 1]); // i - 1 對應(yīng)物品 i
}
}
}
// 打印dp數(shù)組
for(int[] arr : dp){
System.out.println(Arrays.toString(arr));
}
}
}
到了這里，關(guān)于背包問題（貪心）& 二維01背包問題 Java的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
