完全背包理论基础
完全背包问题和01背包问题的区别
完全背包问题：
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大
01背包问题：
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大
完全背包和01背包问题唯一不同的地方就只啊，完全背包中每一物品都有无限件
完全背包的解法：
01背包中的物品只能用一次
只要将01背包中物品使用无限次就是完全背包
在之前01背包的一维dp数组中，为了避免物品被重复使用，在遍历背包的时候采用的是倒序遍历
for (int i = 0; i < weight.length; i++) { // 物品 for (int j = bagSize; j >= weight[i]; j-- ) { // 背包 dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]); } }
所以，只要将遍历背包的顺序改成正序遍历，那么物品就可以被重复多次添加了，那么就是完全背包的使用了
for (int i = 0; i < weight.length; i++) { // 物品 for (int j = weight[i]; j <= bagSize ; j++ ) { // 背包 dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]); } }
完全背包的遍历顺序：
- 不同于01背包的一维dp数组，完全背包的时候背包的遍历和物品的遍历是可以交换的
- 遍历方式一：先物品再背包
for (int i = 0; i < weight.length; i++) { // 物品 for (int j = weight[i]; j <= bagSize ; j++ ) { // 背包 dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]); } }
遍历方式二：先背包再物品
for (int j = 1; j <= bagSize ; j++ ) { // 背包 for (int i = 0; i < weight.length; i++) { // 物品 if ( j - weight[i] >= 0) { dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); } } }
- 因为dp[j]是根据下标 j 之前所对应的 dp[j]计算出来的，只要保证下标 j 之前的dp[j]都是经过计算的就可以了
- 最终代码
- 遍历方式一：先遍历物品再遍历背包
public class BagProblem2 { public static void main(String[] args) { int[] weight = {1,3,4}; int[] value = {15,20,30}; int bagSize = 4; testWeightBagProblem(weight,value,bagSize); } /** * 动态规划获得结果 * @param weight 物品的重量 * @param value 物品的价值 * @param bagSize 背包的容量 */ public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){ // 创建dp数组 int[] dp = new int[bagSize + 1]; // 初始化dp数组 // 将dp[]数组初始化为0，默认就是，不用操作 // 遍历填充dp数组 // 外层循环代表几个物品，循环几次 // 内层循环更换最大值 for (int i = 0; i < weight.length; i++){ // 遍历物品 for (int j = weight[i]; j <= bagSize; j++){ // 遍历背包容量 dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); } // 打印dp数组 for (int num : dp) { System.out.print(num + "\t"); } System.out.print("\n"); } } }
- 遍历方式二：先遍历背包，再遍历物品
public class BagProblem2 { public static void main(String[] args) { int[] weight = {1,3,4}; int[] value = {15,20,30}; int bagSize = 4; testWeightBagProblem(weight,value,bagSize); } /** * 动态规划获得结果 * @param weight 物品的重量 * @param value 物品的价值 * @param bagSize 背包的容量 */ public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){ // 创建dp数组 int[] dp = new int[bagSize + 1]; // 初始化dp数组 // 将dp[]数组初始化为0，默认就是，不用操作 // 遍历填充dp数组 // 外层循环代表背包容量 // 内层循环代表物品 for (int j = 1; j <= bagSize ; j++ ) { // 背包 for (int i = 0; i < weight.length; i++) { // 物品 if ( j - weight[i] >= 0) { dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); } } // 打印dp数组 for (int num : dp) { System.out.print(num + "\t"); } System.out.print("\n"); } } }
