搞了一个早上，才确切明白了这个道理
问题：有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
重新定义问题：
1.有承重分别为1-10的背包10个 2.编号分别为a,b,c,d,e的物品各一个 
3. 从e物品开始依次放入1-10个背包，分别得到最大的价值总和 4. 把d物品放入依次放入存在e物品的1-10个背包，如果价值更高，替换掉e（） 5. c,b,a同理。。。 
思路： 1. 01背包的状态转换方程 f[i,j] = Max{f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }
f[i,j]：在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。 Pi表示第i件物品的价值。 决策：为了背包中物品总价值最大化，第 i件物品应该放入背包中吗 ？ 2. 以a8（行为a，列为的8的单元格）举例 f[i,j] = a8 = 15 f[i-1,j] = b8 = 9 f[i-1,j-Wi] 表示我有一个承重为6的背包（等于当前背包承重减去物品a的重量），当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值 f[i-1,j-Wi] +Pi =b(8 - 2) + 6 = b6 + 6 = 15
public class test3 { public static void main(String[] args) { int m = 10;//最大限重 int n = 3;//总量的个数 int w[] = { 3, 4, 5 };//每个的数量 int p[] = { 4, 5, 6 }; int c[][] = BackPack_Solution(m, n, w, p); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { System.out.PRint(c[i][j] + "/t"); if (j == m) { System.out.println(); } } } } public static int[][] BackPack_Solution(int m, int n, int[] w, int[] p) { // c[i][v]表示前i件物品恰放入一个重量为m的背包可以获得的最大价值 int c[][] = new int[n + 1][m + 1]; for (int i = 0; i < n + 1; i++) c[i][0] = 0; for (int j = 0; j < m + 1; j++) c[0][j] = 0; for (int i = 1; i < n + 1; i++) { for (int j = 1; j < m + 1; j++) { // 当物品为i件重量为j时，如果第i件的重量(w[i-1])小于重量j时，c[i][j]为下列两种情况之一： // (1)物品i不放入背包中，所以c[i][j]为c[i-1][j]的值 // (2)物品i放入背包中，则背包剩余重量为j-w[i-1],所以c[i][j]为c[i-1][j-w[i-1]]的值加上当前物品i的价值 if (w[i - 1] <= j) { if (c[i - 1][j] < (c[i - 1][j - w[i - 1]] + p[i - 1])) c[i][j] = c[i - 1][j - w[i - 1]] + p[i - 1]; else c[i][j] = c[i - 1][j]; } else c[i][j] = c[i - 1][j]; } } return c; }}新闻热点
疑难解答
