背包问题 - 完全背包

代码随想录-完全背包的二维版本
完全背包的一维版本
有点回溯算法里的 39. 组合总和

有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i]，得到的价值是 value[i] 。每件物品都能使用无数次，求解将物品装入背包里物品价值总和最大是多少。
例如：
背包最大重量为 4。

此时放入 4 个物品 0 的价值最大。

分析

我一开始的想法是，因为一个物品可以放入无限次，因此，当我们确定可以放入某个物品的时候，我们就把可放入的所有次数全都遍历一遍，保留最大值即可，因此我们需要在 背包问题-01背包 的基础上，我们需要添加一层循环，循环变量 k 为放入物品 i 的个数，k 的范围是 [0, j/weight[i]]，然后更新 dp[j] 的值为其最大值。这个方法是可行的，也通过了测试。
但是不够优雅和简洁。多了一层循环，效率也不高。

然后我看到了 代码随想录 的方案。还记得我们在 背包问题-01背包 中专门讲解过，为什么一维 dp 的版本中，内层 for 循环遍历背包容量的时候一定要从右往左遍历，因为从左往右遍历的时候，当遍历右侧的容量的时候，左侧的 dp[j] 实际上已经被更新为 dp[i][j]，而不是 dp[i-1][j]，而这恰恰是完全背包问题所需要的，在背包问题中，我们需要的是 dp[i][j]，而不是 dp[i-1][j]，因为每一个物品是有无限个的，所以当我们在遍历物品 i 这一层的时候，如果不放入物品 i，则直接使用 dp[i-1][j]，而如果要放入物品 i 的时候，我们不需要从 dp[i-1] 这一层中查找容量为 j-weight[i] 的值（从物品 0 到物品 i-1 中选），而是直接可以从 dp[i] 这一层中查找容量为 j-weight[i] 的值（从物品 0 到物品 i 中选），为什么，因为物品 i 不是只有一个，而是有任意个，因此不再需要避开物品 i 。而且我们这样做，其实也自带了物品 i 放入 n 次（n 属于 [0, j/weight[i]]）的检查，举个例子：
假设物品 i 的重量是 2，背包的大小是 7，从左往右遍历

• 那么 j=2 的时候，dp[2] 的结果实际上就是不放物品 i 和放一个物品 i 比较结果。
• 那么 j=4 的时候，dp[4] 的结果为不放物品 i 跟 dp[2] 加一个物品 i 的结果的比较结果，假设 dp[2]+value[1] 更大，同时我们计算 dp[2] 的时候，选的是放一个物品 i 的方案，那此时的 dp[4] 的结果实际上就是选了两个物品 i。也就是实际上也比较了 dp[4] 跟两个物品 i 的值。
• 那么 j=6 的时候，dp[4] 的结果为不放物品 i 跟 dp[4] 然后再放一个物品 i 的结果的比较，实际上，也做了 dp[6] 跟三个物品 i 的值的比较。

现在从头梳理一下 dp 数组五部曲，其实跟 背包问题-01背包 差不多
首先定义 dp 数组 dp[j] 表示容量为 j 的背包所容纳物品的最大值。
状态转移方程为一维版的为 dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i])。（二维版的为 dp[i][j]=Math.max(dp[i-1][j],dp[i][j-weight[i]]+value[i]) ）。

背包问题-01背包 的二维 dp 数组为 dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]) 注意这个区别。

初始化，dp[0]=0，或者也不用初始化，因为 dp 数组默认为 int 数组，所有元素默认为 0。
遍历方式，重点
外层 for 循环遍历物品，内层 for 循环遍历背包容量，且必须从小到大遍历。原因上面介绍过了。

解题

我自己想出来的版本，不够优雅简洁。

public int packageFull(int[] weight, int[] value, int w) {
	int[] dp = new int[w + 1];  
	// 默认初始化为 0 即可  
	dp[0] = 0;  
	for (int i = 0; i < weight.length; ++i) {  
	    for (int j = w; j >= weight[i]; j--) {  
	        // 物品 i 的个数  
	        for (int k = 0; k <= j/weight[i]; k++) {  
	            // 遍历逐步增加物品 i 的过程  
	            // 因为都是更新的一个位置 dp[j] 所以不会有问题  
	            dp[j] = Math.max(dp[j], dp[j - k*weight[i]] + k*value[i]);  
	        }  
	    }  
	}
    return dp[w];
}

优雅解法

public int packageFull(int[] weight, int[] value, int w) {
	int[] dp = new int[w + 1];  
	// 默认初始化为 0 即可  
	dp[0] = 0;  
	for (int i = 0; i < weight.length; ++i) {  
	    for (int j = weight[i]; j < w + 1; j++) {  
	        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);  
	    }  
	}
    return dp[w];
}

相关题

背包问题-01背包