本文主要是写题时遇到的动态规划问题的整理

动态规划

1.背包问题

背包问题是一种组合优化的 NP 完全问题：

​ 有 N 个物品和容量为 W 的背包，每个物品都有 自己的体积w和价值v，求拿哪些物品可以使得背包所装下物品的总价值最大。

如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题；如果不限定每种物品的数量，则问题称为无界背包问题或完全背包问题。

0-1背包

​ 以0-1背包问题为例。我们可以定义一个二维数组dp 存储最大价值，其中dp[i] [j]示前i件物品体积不超过j的情况下能达到的最大价值。在我们遍 历到第i件物品时，在当前背包总容量为j的情况下，如果我们不将物品i放入背包，那么
$$
dp[i][j] =dp[i-1][j]
$$
，即前 i 个物品的最大价值等于只取前 i-1 个物品时的最大价值；如果我们将物品 i 放 入背包，假设第i件物品体积为w，价值为v，那么我们得到dp[i] [j]=dp[i-1] [j-w]+v。我们只需 在遍历过程中对这两种情况取最大值即可，总时间复杂度和空间复杂度都为O(NW)。

int knapsack(vector<int> weights, vector<int> values, int N, int W) 
{ vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0)); 
  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] = 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(ma(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]，在程序实现时需要按倒序来循环求解。

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

完全背包

在完全背包问题中，一个物品可以拿多次。

假设我们遍历到物品 i = 2， 且其体积为w=2，价值为v=3；对于背包容量j=5，最多只能装下2个该物品。那么我们的状 态转移方程就变成了
$$
dp[2][5]=max(dp[1][5],dp[1][3]+3,dp[1][1]+6)
$$
如果采用这种方法，假设背包容量无穷大而物体的体积无穷小，我们这里的比较次数也会趋近于无穷大，远超 O(NW)的时间复杂度。 怎么解决这个问题呢？我们发现在 dp[2] [3] 的时候我们其实已经考虑了 dp[1] [3] 和 dp[2] [1] 的情况，而在时 dp[2] [1]也已经考虑了 dp[1] [1] 的情况。因此，如图下半部分所示，对于拿多个物品的情况，我们只需考虑 dp[2] [3] 即可，即
$$
dp[2] [5] = max(dp[1] [5], dp[2] [3] + 3)
$$
这样，我们 就得到了完全背包问题的状态转移方程：dp[i] [j]=max(dp[i-1] [j],dp[i] [j-w]+v)，其与0-1背包问题的差别仅仅是把状态转移方程中的第二个i-1变成了i。

int knapsack(vector<int> weights, vector<int> values, int N, int W) 
{ 
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0)); 
    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] = max(dp[i-1][j], dp[i][j-w] + v); 
            } 
            else 
            { 
                dp[i][j] = dp[i-1][j]; 
            } 
        } 
    } 
    return dp[N][W]; 
} 

空间优化

同样的，我们也可以利用空间压缩将时间复杂度降低为 O(W)。这里要注意我们在遍历每一行的时候必须正向遍历，因为我们需要利用当前物品在第j-w列的信息。

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