image
01背包
有N件物品和一個最多能被重量為W 的背包形庭。第i件物品的重量是weight[i]厌漂，得到的價值是value[i] 萨醒。每件物品只能用一次苇倡，求解將哪些物品裝入背包里物品價值總和最大。
image
問題：背包容量為4晓褪，物品以及其重量和價值如下表所示综慎，問背包能背的最大價值是多少？
image.png
01背包——二維dp數(shù)組解法
動態(tài)方程：int[][]dp = new int[n][bagWeight+1]好港，其中n為物品的個數(shù)，bagWeight為背包的容量
dp[i][j]表示從[0-i]中挑選物品钧汹，放入容量為j的背包中，價值總和最大是多少
二維dp數(shù)組如下圖所示：
image.png
初始化：背包重量為0碗降，總價值為0辨宠；當(dāng)只裝入第一個背包且背包重量大于等于weight[0]時货裹，dp[0][j]=val[0]
image.png
動態(tài)轉(zhuǎn)移：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
image.png
Java代碼
// 二維dp數(shù)組01背包 時間復(fù)雜度 O(n^2)
public static void backPack2(int []w,int[] val,int bagWeight){
int n = w.length;
//dp[i][j]表示從[0-i]中挑選物品，放入容量為j的背包中赋兵，價值總和最大是多少
int[][]dp = new int[n][bagWeight+1];
//初始化
for(int i=0;i<dp.length;i++){
dp[i][0] = 0;//背包容量為0時搔预，放入物品的價值為0
}
for(int j = w[0];j<=bagWeight;j++){
dp[0][j] = val[0];//只裝入第一個物品時 ，放入物品的價值就是val[0]
}
for(int i=1;i<dp.length;i++){//遍歷物品
for(int j=1;j<dp[0].length;j++){//遍歷背包容量
if(j<w[i]) dp[i][j] = dp[i-1][j];
else dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i]]+val[i]);
}
}
System.out.println("放入物品的最大價值："+dp[n-1][bagWeight]);
}
01背包——一維dp數(shù)組解法
動態(tài)方程：int[] dp = new int[bagWeight+1];拯田，其中bagWeight為背包的容量
dp[j]表示表示背包容量為j時，能獲得的最大價值
初始化：dp[0] = 0,背包容量為0所背的物品的最大價值就是0吭产。
遞歸公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
Java代碼
//一維dp數(shù)組（滾動數(shù)組） 時間復(fù)雜度O(n)
public static void backPack(int []w,int[] val,int bagWeight){
//定義dp數(shù)組表示dp[j]表示背包容量為j時鸭轮，能獲得的最大價值
int[] dp = new int[bagWeight+1];//初始化全為0
//遍歷順序：先遍歷物品在遍歷背包的重量；
for(int i =0;i<w.length;i++){
//01背包內(nèi)嵌的循環(huán)是從大到小遍歷窃爷，為了保證每個物品僅被添加一次。
for(int j =bagWeight;j>=w[i];j--){
dp[j] = Math.max(dp[j],dp[j-w[i]]+val[i]);
//dp[j-w[i]]+val[i] 表示加上第i個物品的后的總價值
}
}
for(int j=0;j<=bagWeight;j++){
System.out.println("背包容量為"+j+"時医吊，dp["+j+"]="+dp[j]+" ");
}
System.out.println("放入物品的最大價值："+dp[bagWeight]);
}
倒敘遍歷是為了保證物品i只被放入一次逮京！卿堂。但如果一旦正序遍歷了造虏，那么物品0就會被重復(fù)加入多次麦箍！
參考：代碼隨想錄-背包理論
