Skip to content

背包dp

0/1背包

给定一组物品，每种物品有重量 \(w_i\) 和价值 \(v_i\)，在限定的总容量 \(W\) 内，如何选择物品使得总价值最大。

0/1之意在于每个物品只有一个，状态包括选或不选。

进行递归时需要考虑的问题
  1. 如果当前物品个数越界（超过物品总数），返回0：if (n > num)return 0
  2. 如果当前物品与剩余容积已被计算过，返回记录值：if (rem[n][vol])return rem[n][vol]
  3. 如果当前物品体积超过背包剩余容积，跳过当前物品，继续遍历：dfs(n+1,vol)
  4. 如果当前物品体积小于或等于背包剩余体积，返回不选当前物品和选当前物品分别继续遍历后的最大值：max(dfs（n+1，vol）,dfs(n+1,vol-v[n])+w[n]）

注意：情况3和4都应该记录sum值，并存入记忆容器。

定义状态数组\(dp[i][j]\) 表示前 \(i\) 件物品放入容量为 \(j\) 的背包能获得的最大价值，状态转移方程如下：

\[dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])\]

其中，dp[i-1][j]表示不选第 \(i\) 件，dp[i-1][j-w[i]] + v[i]表示选第 \(i\) 件（前提是剩余空间够放）。

由状态转移公式dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])易得：每次进行递归时，\(dp[i][j]\)只与\(dp[i-1][x]\)（x为占位符）相关，因此可使用两个数组f[N]和g[N]进行回滚以优化内存占用。

实现

带一维优化的实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const int N = 1005;

int num = 0, vols = 0;
int v[N] = { 0 }, w[N] = { 0 };
int f[N] = { 0 }, g[N] = { 0 };

int main()
{
    cin >> num >> vols;
    for (int i = 1;i <= num;i++) {
        cin >> v[i] >> w[i];
    }

    for (int i = 1;i <= num;i++) {
        for (int j = 0;j <= vols;j++) {
            if (j < v[i])f[j] = g[j];
            else
            {
                f[j] = max(g[j], g[j-v[i]] + w[i]);     //注意状态转移公式中的两项都和i-1相关，因此都要使用i-1数据所在的数组g[N]
            }
        }
        copy(f, f+N+1, g);          //回滚，在本轮遍历后令i成为i-1，一定要在外层循环
    }

    cout << f[vols];

    return 0;
}