【动态规划】0 - 1背包问题（通俗易懂, 万能统一代码）_资讯

【动态规划】0 - 1背包问题（通俗易懂, 万能统一代码）

创始人

2024-06-02 14:32:26

0次

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];
}