首页 > 代码库 > 0-1背包问题的动态规划实现
0-1背包问题的动态规划实现
一，问题描述
给定一个背包，已知背包的最大承重为packageWeight，再给出若干件(numbers件)物品，已经每件物品的重量和对应的价值。
物品的重量存储在weight[]数组中，物品的价值存储在value[]数组中。
现在要求：应该挑选哪几件物品，使得背包装下最大的价值（注意：装的物品的重量不能超过背包的承重）
（本文在最后打印出了装入了哪几件物品）
二，问题分析
这是一个典型的动态规划求解。对于每件物品而言，只有两种选择，要么选中它装入背包；要么不选它。因此，这是一个0-1背包问题，而不是部分背包问题（只选这件物品的一部分）
关于部分背包问题，可参考：部分背包问题的贪心算法正确性证明
对于DP而言，关键是列出它的状态方程，0-1背包问题的状态方程与“硬币找零”问题的状态方程非常相似。关于硬币找零，可参考：硬币找零问题的动态规划实现
这里再重新分析一个0-1背包问题的状态方程：
设 dp[i][j] 表示：在背包最大承重为 j 时，可选的物品件数有 i 件 的情况下，背包装下的物品的最大价值。
dp[i-1][j-weight[i-1]]+value[i-1] 表示：当将第 i 件物品装入背包时，背包还能承受的重量变成: j-weight[i-1] (weight[]数组下标0存储第一件物品的重量)
由于第 i 件物品已经考虑了(将之装入到背包了)，故现在可装入的物品 只有 i-1 件了。
dp[i-1][j]表示：不将第 i 件物品装入背包。此时，本次选择对背包的承重没有影响，故 j 不变。由于第 i 件物品已经考虑了(不把它装入背包)，故现在可装入的物品只有 i-1 件了。
由于我们要找能装入背包的最大价值，在上面两种情形下，哪种选择的导致的价值最大，就选谁。从而状态方程如下：--取二者中较大的那个。
dp[i][j]=max{dp[i-1][j-weight[i-1]]+value[i-1]， dp[i-1][j]}
三，代码分析：
假设第一行输入两个数： 背包的最大承重和物品的件数----packageWeight numbers
第二行输入物品的重量，第三行输入对应的物品的价值，格式如下：
10 5
2 2 6 5 4
6 3 5 4 6
1 String packInfo = null; 2 String weights = null; 3 String values = null; 4 while(scanner.hasNextLine()){ 5 packInfo = scanner.nextLine(); 6 int packageWeight = Integer.valueOf(packInfo.split(" ")[0]); 7 int numbers = Integer.valueOf(packInfo.split(" ")[1]); 8 9 weights = scanner.nextLine();10 values = scanner.nextLine();11 String[] weis = weights.split(" ");12 String[] vals = values.split(" ");13 //weight[]数组是从下标0开始存储，索引0存储第一件物品的重量14 int[] weight = new int[numbers];15 int[] value = http://www.mamicode.com/new int[numbers];16 17 for(int i = 0; i < numbers; i++)18 {19 weight[i] = Integer.valueOf(weis[i]);20 value[i] = Integer.valueOf(vals[i]);21 }
以上代码解析输入的情况。
1 int[][] dp = new int[numbers + 1][packageWeight + 1];2 3 //init4 for(int i = 0; i <= numbers; i++)5 dp[i][0] = 0;6 for(int i = 0; i <= packageWeight; i++)7 dp[0][i] = 0;
这段代码对背包问题进行初始化。dp[i][0]=0 表示：背包最大承重为0，故不能装物品，故装入的物品最大价值也就是0了。
dp[0][j]=0 表示：可选的物品种类为0，背包的最大承重为 j 。都没有物品可选，怎么装？没有物品装啊。故最大价值也为0。
1 //dp[i][j] = max{dp[i-1][j], dp[i-1][j-weight[i-1]]+value[i-1]} 2 for(int i = 1; i <= numbers; i++) 3 { 4 for(int j = 1; j <= packageWeight; j++) 5 { 6 if(weight[i-1] > j)// 第i件物品的重量大于背包的承重 7 8 { 9 dp[i][j] = dp[i-1][j];10 continue;11 }12 //dp[i][j] = max{dp[i-1][j], dp[i-1][j-weight[i-1]]+value[i-1]}13 if(dp[i-1][j] < dp[i-1][j-weight[i-1]] + value[i-1])14 dp[i][j] = dp[i-1][j-weight[i-1]] + value[i-1];15 else16 dp[i][j] = dp[i-1][j];17 }18 }
这段代码，本质上就是状态方程的实现。它以自底向上(从下标1开始求啊...)的方式求解DP问题。
既然，找出了能够装入的最大价值，那能不能知道装入了哪些物品？？？
当然也是可以知道的。
1 //反向找出 选中的物品(哪些物品装入到背包中了?)2 int j= packageWeight; 3 for(int i = numbers;i>0;i--){4 if(dp[i][j]>dp[i-1][j]){5 System.out.print(i+" ");//输出选中的物品的编号6 j=j-weight[i-1];7 if(j<0) break;8 }
第四行if语句成立时，说明将第 i 件物品装入到背包中了，结果导致价值增大。第五行打印出装入了哪几件物品。
四，完整代码实现
import java.util.Scanner; public class Main { public static void zeroOnePack(){ Scanner scanner = new Scanner(System.in); String packInfo = null; String weights = null; String values = null; while(scanner.hasNextLine()){ packInfo = scanner.nextLine(); int packageWeight = Integer.valueOf(packInfo.split(" ")[0]); int numbers = Integer.valueOf(packInfo.split(" ")[1]); weights = scanner.nextLine(); values = scanner.nextLine(); String[] weis = weights.split(" "); String[] vals = values.split(" "); //weight[]数组是从下标0开始存储，索引0存储第一件物品的重量 int[] weight = new int[numbers]; int[] value = http://www.mamicode.com/new int[numbers]; for(int i = 0; i < numbers; i++) { weight[i] = Integer.valueOf(weis[i]); value[i] = Integer.valueOf(vals[i]); } int[][] dp = new int[numbers + 1][packageWeight + 1]; //init for(int i = 0; i <= numbers; i++) dp[i][0] = 0; for(int i = 0; i <= packageWeight; i++) dp[0][i] = 0; //dp[i][j] = max{dp[i-1][j], dp[i-1][j-weight[i-1]]+value[i-1]} for(int i = 1; i <= numbers; i++) { for(int j = 1; j <= packageWeight; j++) { if(weight[i-1] > j)// 第i件物品的重量大于背包的承重 { dp[i][j] = dp[i-1][j]; continue; } //dp[i][j] = max{dp[i-1][j], dp[i-1][j-weight[i-1]]+value[i-1]} if(dp[i-1][j] < dp[i-1][j-weight[i-1]] + value[i-1]) dp[i][j] = dp[i-1][j-weight[i-1]] + value[i-1]; else dp[i][j] = dp[i-1][j]; } } System.out.println(dp[numbers][packageWeight]);//输出背包能够装的最大价值 //反向找出 选中的物品(哪些物品装入到背包中了?) int j= packageWeight; for(int i = numbers;i>0;i--){ if(dp[i][j]>dp[i-1][j]){ System.out.print(i+" ");//输出选中的物品的编号 j=j-weight[i-1]; if(j<0) break; } }//end while } scanner.close();} //hapjin‘s test case //10 5 //2 2 6 5 4 //6 3 5 4 6 public static void main(String[] args) { zeroOnePack(); }}
五，参考资料
某种 找换硬币问题的贪心算法的正确性证明
硬币找零问题的动态规划实现
部分背包问题的贪心算法正确性证明
从 活动选择问题 看动态规划和贪心算法的区别与联系
原文：http://www.cnblogs.com/hapjin/p/5818418.html
0-1背包问题的动态规划实现