整数0-1背包问题练习题

? 小偷有一个容量为W的背包，有n件物品，第i个物品价值vi，且重wi。
? 目标: 找到xi使得对于所有的xi = {0, 1}，sum(wi*xi) <= W, 并且 sum(xi*vi)最大。

常规思路

public class BackPack { static int [] w = new int[] {3, 4, 5, 7, 6}; // 每件物品的重量 static int[] v = new int[] {4, 5, 2, 8, 9}; // 每件物品的价值 static int N = w.length; // 物品的个数 final int W = 15; // 背包的总重量 /** * @param idx 当前遍历的是第几个物品 * @param S 当前物品的总重量 * @return 最大的价值 */ int search(int idx, int S) { // 当前物品的总重量和大于背包的重量 if (S > W) { return 0; } // 遍历到最后一个物品了 if (idx >= N) { return 0; } return Math.max(search(idx+1, S + w[idx]) + v[idx], search(idx+1, S)); } }

代码里冗余太多（有多种方法都可以使得当前物品的总重量达到S，每一种构成方式都会去算一遍），对于
【整数0-1背包问题】当前的状态而言，我们只关心的使用的多少，如何使用的并不关心。

改进后：

int[][] f = new int[N][W]; // 定义f(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值；// 初始化块 { for (int i=0; i W) { return 0; } // 遍历到最后一个物品了 if (idx >= N) { return 0; } // 如果计算过 if (f[idx][S] >= 0) { // F(i, W)表示前i件物品体积为w，最大价值 return f[idx][S]; } f[idx][S] =Math.max(search2(idx+1, S + w[idx]) + v[idx], search2(idx+1, S)); return f[idx][S]; }

迭代法：自底向上求解

int search() { dp[0][0] = 0; // 赋初始值 for (int i=0; i<=W; ++i) { dp[0][i] = (int) Double.NEGATIVE_INFINITY; // 表示负无穷 }for (int i=1; i<=N; ++i) { dp[i][0] = 0; // (先要把已知的条件填好) for (int j=1; j<=W; ++j) // 背包的容量的范围 { dp[i][j] = dp[i-1][j]; // 表示还没选第idx件物品 if (j >= w[i]) // 表示背包中能放进去 // 注意这里在计算的时候要利用之前已经计算出来的状态 dp[i][j] =Math.max(dp[i-1][j - w[i]] + v[i], dp[i-1][j]); } } return dp[N][W]; }