image
01背包
有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
image
问题：背包容量为4，物品以及其重量和价值如下表所示，问背包能背的最大价值是多少？
image.png
01背包——二维dp数组解法
动态方程：int[][]dp = new int[n][bagWeight+1]，其中n为物品的个数，bagWeight为背包的容量
dp[i][j]表示从[0-i]中挑选物品，放入容量为j的背包中，价值总和最大是多少
二维dp数组如下图所示：
image.png
初始化：背包重量为0，总价值为0；当只装入第一个背包且背包重量大于等于weight[0]时，dp[0][j]=val[0]
image.png
动态转移：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
image.png
Java代码
// 二维dp数组01背包 时间复杂度 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数组解法
动态方程：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数组（滚动数组） 时间复杂度O(n)
public static void backPack(int []w,int[] val,int bagWeight){
//定义dp数组表示dp[j]表示背包容量为j时，能获得的最大价值
int[] dp = new int[bagWeight+1];//初始化全为0
//遍历顺序：先遍历物品在遍历背包的重量；
for(int i =0;i<w.length;i++){
//01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
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就会被重复加入多次！
参考：代码随想录-背包理论
网友评论