如何快速掌握Leetcode中一维和二维数组版本的01背包与完全背包问题？

本文共计937个文字，预计阅读时间需要4分钟。

使用01背包问题求解二维数组，无需遍历顺序，要求优先遍历物品，重量的重置，也可以先重置重量再重置物品；但先物品后重量更容易理解。代码示例：

javapublic static void getValue(int W, int[] weight, int[] value) { int N=value.length; int[] dp=new int[W + 1]; // 初始化dp数组}

01背包二维数组

• 无遍历顺序要求
• 可先遍历物品再重量，也可先重量再物品；但先物品较好理解

//二维数组的01背包 public static void getValue(int W,int[] weight,int[]value) { int N=value.length; int dp[][]= new int[N+1][W+1];//dp[i][j]意思是：背包容量为j时，在前i件物品中取小于等于i件物品，此时取得的物品的价值最大 //注意下标问题 for(int i=1;i<=N;i++) { for(int j=0;j<=W;j++) { if(weight[i-1]>j) {//太重了，拿不了 dp[i][j]=dp[i-1][j]; }else {//拿：dp[i-1][j-weight[i]]+value[i] 不拿： dp[i-1][j] dp[i][j]=Math.max(dp[i-1][j-weight[i-1]]+value[i-1], dp[i-1][j]); } } } System.out.println(dp[N][W]); } @Test public void test1(){ int W=20;//背包容量为20 int[] weight = {2, 3, 4, 5, 9};//重量 2 3 4 5 9 int[] value = {3, 4, 5, 8, 10};//价值3 4 5 8 10 getValue(W,weight,value);//26 }

01背包一维数组版

• 一定要先遍历物品再遍历背包容量，且背包容量为倒序
• 因为如果背包容量为正序就代表可以多次拿同一物品，所以倒序限制每次只拿一个
• 正因为限制每次只拿一个所以不能将其放在外层循环，因此一定要先遍历物品

//一维数组（滚动数组）01背包 //注意01背包一维版遍历一定要先遍历物品再遍历背包容量，且背包容量为倒序 public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){ int wLen = weight.length; //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值 int[] dp = new int[bagWeight + 1]; //遍历顺序：先遍历物品，再遍历背包容量 for (int i = 0; i < wLen; i++){ for (int j = bagWeight; j >= weight[i]; j--){//且为倒序 dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); } } System.out.println(dp[bagWeight]); } @Test public void test2() { int[] weight = {2, 3, 4, 5, 9};//重量 2 3 4 5 9 int[] value = {3, 4, 5, 8, 10};//价值3 4 5 8 10 int bagWight = 20; testWeightBagProblem(weight, value, bagWight); }

完全背包一维数组版

• 每件物品都有无限个（也就是可以放入背包多次）
• 可以先物品后重量，也可以先重要后物品；但注意遍历重要要正序（和01区分）

//完全背包一维版-先遍历物品再遍历背包 public static void testWeightBagProblem3(int[] weight, int[] value, int bagWeight){ int wLen = weight.length; //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值 int[] dp = new int[bagWeight + 1]; //遍历顺序：先遍历物品，再遍历背包容量 for (int i = 0; i < wLen; i++){ for (int j = weight[i]; j <=bagWeight; j++){//且为倒序 dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); } } System.out.println(dp[bagWeight]); } @Test public void test3() { int[] weight = {2, 3, 4, 5, 9};//重量 2 3 4 5 9 int[] value = {3, 4, 5, 8, 10};//价值3 4 5 8 10 int bagWight = 20; testWeightBagProblem3(weight, value, bagWight);//32 }

//完全背包一维版--先遍历背包再遍历物品 @Test public void testCompletePackAnotherWay(){ int[] weight = {2, 3, 4, 5, 9}; int[] value = {3, 4, 5, 8, 10}; int bagWeight = 20; int[] dp = new int[bagWeight + 1]; for (int i = 1; i <= bagWeight; i++){ // 遍历背包容量 for (int j = 0; j < weight.length; j++){ // 遍历物品 if (i - weight[j] >= 0){ dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]); } } } for (int maxValue : dp){ System.out.println(maxValue + " "); } }