01背包

有 $N$ 件物品和一个最多能背重量为 $W$ 的背包。第 $i$ 件物品的重量是 $weight[i]$，得到的价值是$value[i]$。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

利用动规五部曲进行求解：

1. 确定dp数组以及下标的含义
   使用二维数组 $dp[i][j]$ 表示从下标[0-i]的物品里任意取，放进容量为 j 的背包中的最大价值总和。

2. 确定递推公式
   动态规划的思想是从上一状态推出当前状态，从 $dp[i-1][j]$ 状态来推 $dp[i][j]$，即在 $dp[i-1][j] $状态下考虑物品$i$ 的取舍：

   1. 不取物品$i$：$dp[i][j]=dp[i-1][j]$；
   2. 取物品$i$：此时背包要留出物品i的重量，所以要找到 从下标$[0-(i-1)]$的物品中任意取，放进容量$(j-weight[i])$的背包中的最大价值总和，然后再将物品$i$放入背包，$dp[i][j]=dp[i-1][j-weight[i]]+value[i]$。
      最终结果是这两种情况下的最大价值：
      d p [ i ] [ j ] = max ⁡ { d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w e i g h t [ i ] ] + v a l u e [ i ] } dp[i][j] = \max{\{dp[i-1][j], dp[i-1][j-weight[i]] + value[i] \}} dp[i][j]=max{dp[i−1][j],dp[i−1][j−weight[i]]+value[i]}

3. dp数组初始化

   从定义出发，当背包的重量为0时，无法选取任何物品，即对于 $dp[i][0]$来说全部等于0；
   当仅考虑物品0时，只有当背包的重量大于$weight[0]$时才能选取物品0，即对于$dp[0][j]$来说，当$j<weight[0]$时，$dp[0][j]=0$；当$j\ge weight[0]$时，$dp[0][j]=value[0]$。

   //声明dp数组，并初始化所有元素=0
   vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1, 0));
   
   //初始化do[0][j]
   for (int i = weight[0]; i <= bagWeight; i++) {
     dp[0][i] = value[0];
   }
   1
   2
   3
   4
   5
   6
   7

4. 确定遍历顺序

   由递推公式来看，先遍历物品和先遍历背包均可以，但是先遍历物品更好理解。

5. 举例推导

int bag01() {
  vector<int> weight = { 1, 3, 4 };
  vector<int> value = { 15, 20, 30 };
  int bagWeight = 4;

  int wsize = weight.size();
  int vSize = value.size();

  vector<vector<int>> dp(wsize + 1, vector<int>(bagWeight + 1, 0));

  //初始化
  for (int i = weight[0]; i <= bagWeight; i++) {
    dp[0][i] = value[0];
  }
  //遍历
  for (int i = 1; i < wsize; i++) {
    for (int j = 0; j <= bagWeight; j++) {
      if (j < weight[i]) dp[i][j] = dp[i - 1][j];
      else
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
  }
  cout << dp[wsize - 1][bagWeight] << endl;
  return 0;
}
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