0 - 1背包问题详解

什么是背包问题？

最常见的背包问题有0-1背包，完全背包，多重背包，分组背包这四种。什么是背包问题？

• 简单来说就是：一个小偷背了一个背包潜进了金店，包就那么大，他如果保证他背出来所有物品加起来的价值最大。
• 规范描述就是：有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。

解题思路：

定义一个二维数组 dp 存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。

设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：

• 第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，dp[i][j] = dp[i-1][j]。
• 第 i 件物品添加到背包中，dp[i][j] = dp[i-1][j-w] + v。

第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：
dp[i][j]=max⁡(dp[i−1][j],dp[i−1][j−w]+v)d p[i][j]=\max (d p[i-1][j], d p[i-1][j-w]+v)dp[i][j]=max(dp[i−1][j],dp[i−1][j−w]+v)

代码：(java)

// W 为背包总体积
// N 为物品数量
// weights 数组存储 N 个物品的重量
// values 数组存储 N 个物品的价值
public int knapsack(int W, int N, int[] weights, int[] values) {int[][] dp = new int[N + 1][W + 1];for (int i = 1; i <= N; i++) {int w = weights[i - 1], v = values[i - 1];for (int j = 1; j <= W; j++) {if (j >= w) {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);} else {dp[i][j] = dp[i - 1][j];}}}return dp[N][W];
}

空间优化

在程序实现时可以对 0-1 背包做优化。观察状态转移方程可以知道，前 i 件物品的状态仅与前 i-1 件物品的状态有关，因此可以将 dp 定义为一维数组，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。此时，
dp[j]=max⁡(dp[j],dp[j−w]+v)d p[j]=\max (d p[j], d p[j-w]+v)dp[j]=max(dp[j],dp[j−w]+v)

因为 dp[j-w] 表示 dp[i-1][j-w]，因此不能先求 dp[i][j-w]，防止将 dp[i-1][j-w] 覆盖。也就是说要先计算 dp[i][j] 再计算 dp[i][j-w]，在程序实现时需要按倒序来循环求解。

public int knapsack(int W, int N, int[] weights, int[] values) {int[] dp = new int[W + 1];for (int i = 1; i <= N; i++) {int w = weights[i - 1], v = values[i - 1];for (int j = W; j >= 1; j--) {if (j >= w) {dp[j] = Math.max(dp[j], dp[j - w] + v);}}}return dp[W];
}

无法使用贪心算法的解释

0-1 背包问题无法使用贪心算法来求解，也就是说不能按照先添加性价比最高的物品来达到最优，这是因为这种方式可能造成背包空间的浪费，从而无法达到最优。

考虑下面的物品和一个容量为 5 的背包，如果先添加物品 0 再添加物品 1，那么只能存放的价值为 16，浪费了大小为 2 的空间。最优的方式是存放物品 1 和物品 2，价值为 22.

变种

• 完全背包：物品数量为无限个

• 多重背包：物品数量有限制

• 多维费用背包：物品不仅有重量，还有体积，同时考虑这两种限制

• 其它：物品之间相互约束或者依赖

注：仅供学习参考!