背包dp之01背包

前景引入

有 \(N\) 件物品和一个容量为 \(V\) 的背包。放入第 \(i\) 件物品耗费的费用是 \(C_i\)，得到的价值是 \(W_i\)。求解将哪些物品装入背包可使价值总和最大。

在上述例题中，由于每个物体只有两种可能的状态（选与不选），对应二进制中的 0 和 1，这类问题便被称为 「0-1 背包问题」。

基本思路

例题中已知条件有第 \(i\) 个物品的费用时 \(C_{i}\)，价值 \(W_{i}\)，以及背包的总容量 \(V\)。

设 \(DP\) 状态 \(dp[i][j]\) 为在只能放前 \(i\) 个物品的情况下，容量为 \(j\) 的背包所能达到的最大总价值。

假设当前已经处理好了前 \(i-1\) 个物品的所有状态，那么对于第 \(i\) 个物品 - 当不选时，前 \(i − 1\) 件物品放入容量为 \(j\) 的背包中，故这种情况的最大价值为 \(dp[i-1][j]\)； - 当选时，因为第 \(i\) 件物品的费用是 \(C_i\)，前 \(i − 1\) 件物品放入剩下的容量为 \(j − C_i\) 的背包中 加上 \(W_i\)， 故这种情况的最大价值为 \(dp[i-1][j-C[i]]+W_{i}\)。

由此可以得出状态转移方程：

样例

第一行：物品个数 \(N\) 和背包大小 \(V\)。

第二行至第 \(N+1\)行： 第 \(i\) 个物品的费用 \(C_i\) 和 价值 \(W_i\)

4 6        
1 4
2 6
3 12
2 7

1

2

3

4

普通版写法

• 空间复杂度为 \(O(NV)\)
• 时间复杂度为 \(O(NV)\)

  for (int i=1; i<=N; i++){
      for (int j=1; j<=V; j++){
          if (j < C[i]){     
              dp[i][j] = dp[i-1][j]; // 当前物品比背包容量还要大时， 只能不选
          } else {
              dp[i][j] = max(dp[i-1][j], dp[i-1][j-C[i]] + W[i]);  // 选 和 不选 取一个最大价值
          }
      }
  }
  
  cout << dp[N][V];
  

优化空间复杂度

滚动数组写法

已知\(dp[i][j]\) 是由\(dp[i-1][j]\)、\(dp[i-1][j-\)C_i\(]\) 两个子问题递推而来，那么做一个两行的滚动数组，是一个可行性方案

• 空间复杂度 \(O(2V)\)

int p = 0;
for (int i=1; i<=N; i++){
    p ^= 1;
    for (int j=1; j<=V; j++){
        if (j < W[i]){
            dp[p][j] = dp[p^1][j];
        } else {
            dp[p][j] = max(dp[p^1][j], dp[p^1][j-C[i]] + W[i]);
        }
    }
}

cout << dp[p][V];

关于 p变量？

位运算中的 ^ (异或)操作，代表相同为0，不同为1； 那么操作p ^= 1 就可以实现 0、1、0、1、0...的开关，从而操作滚动数组。

一维数组写法

已知滚动数组方案是可行的， 那么都在一个数组存储和计算呢， 答案是可行的。

假设 \(dp\)数组 存储的是前\(i-1\)的物品的最大价值，同时在这个数组里更新第\(i\)物品； 需要注意的是\(V\)容量需要逆序递减计算，防止 \(dp[j-C_i]\) 在使用之前被修改

for (int i=1; i<=N; i++){
    for (int j=V; j>=C[i]; j--){
        dp[j] = max(dp[j], dp[j-C[i]] + W[i]);
    }
}
cout << dp[V];

DP数组初始化问题

关于求解背包问题时， 一般有两种不太相同的问法 - 求 “恰好装满背包” 的最大总价值 : 必须刚好用尽容量 V，否则不算合法解 - 求 “在容量不超过 \(V\) 的前提下” 的最大总价值: 可以没装满，只要不超过容量即可

为什么第一种要用\(-\infty\)初始化

\(dp[0]\) 可以理解为恰好装满，且合法解是 0，所以可以初始化为 0；但是其他位置的均是没有恰好装满的状态，因此都没有合法解，故填写 \(-\infty\)

第二种问什么可以

因为“什么都不选”也是合法方案，价值为 0，只要不超过容量都可以接受

#include <bits/stdc++.h>

using namespace std;
int C[3410], W[3410];
int dp[12889];

int n, m;
int main() {
        cin >> n >> m;

        for (int i=1; i<=n; i++) cin >> C[i] >> W[i];


        for (int i=1; i<=n; i++){
                for (int j=m; j>=C[i]; j--){
                        dp[j] = max(dp[j], dp[j-C[i]] + W[i]);
                }
        }

        cout  << dp[m];
}

练习

• P2871 [USACO07DEC] Charm Bracelet S
• P1048 [NOIP 2005 普及组] 采药
• P1049 [NOIP 2001 普及组] 装箱问题
• P2722 [USACO3.1] 总分 Score Inflation
• P2639 [USACO09OCT] Bessie's Weight Problem G
• P2430 严酷的训练
• P1060 [NOIP 2006 普及组] 开心的金明
• P1358 扑克牌