DP总结(一，背包DP)

别问我为什么先写背包

0.状态定义 & 基础方程#

定义 $dp _ {i,j}$ 为考虑前 $i$ 个物品，在体积小于等于 $j$ 的情况下，可以得到的最大价值。对于每个物品，有取和不取两种选法，同时可以从 $[v _ i,V]$ 中任意一个值转移而来。于是，有 DP 方程：

注意到，对于 $dp _ {i,j}$，我们只关注 $dp _ {i - 1,j}$，所以我们可以用滚动数组把第一维滚掉。则有

1. 0-1背包#

如上，答案为 $dp _ {n,V}$。

但是，答案需要 $\textcolor{red}{\textbf{倒序枚举}}$。

因为滚动数组滚掉了第一维，如果正序，就可能一个物品多次取，导致答案错误。

详细讲解

1
2
3
4
5
6
7

for(int i = 1;i <= n;i++)
{
    for(int j = V;j >= v[i];j--)
        dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
}

ans = dp[n][V];

2. 完全背包#

刚刚的错误做法就是这里的正确做法，因为本来就可以多次取。

1
2
3
4
5
6
7

for(int i = 1;i <= n;i++)
{
    for(int j = v[i];j <= V;j++)
        dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
}

ans = dp[n][V];

3. 多重背包#

就是一个物品可以取 $k _ i$ 次，并非无限次。

此问题等价于有 $k _ i$ 个价值 $w _ i$ 体积 $v _ i$ 的物品，然后跑一遍0-1背包。

但是，时间复杂度是 $\Omicron(n \sum _ {i = 1} ^ n k _ i)$ ，数据大点 T 飞。

优化 ：二进制分组优化#

注意到，$\forall x \in \N$，有 $x = \sum 2 ^ i \times b _ i$，其中 $b _ i \in \{0,1\}$。所以，选 $2 ^ j$ 个 $A _ i$ 物品，等价于选一个由 $2 ^ j$ 个 $A _ i$ 物品组成的物品，然后跑0-1背包就不会爆炸了。

还可以单调栈/单调队列优化，但我不想写，都 log 了就没必要了吧

4.多维费用#

0-1背包优化前状态改为 $dp _ {i,j,k}$，然后就没了

1
2
3
4
5
6
7
8
9

for(int i = 1;i <= n;i++)
{
    for(int j = V;j >= v[i];j--)
    {
        for(int k = C;j >= c[i];k--)
            dp[j][k] = max(dp[j][k],dp[j - v[i]][k - c[i]] + w[i]);
    }
}
ans = dp[V][C];

5.分组背包#

每一组跑一遍 0-1 背包，然后统计答案和。

注意循环顺序

1
2
3
4
5
6
7

for (int k = 1; k <= ts; k++)          // 循环每一组
  for (int i = m; i >= 0; i--)         // 循环背包容量
    for (int j = 1; j <= cnt[k]; j++)  // 循环该组的每一个物品
      if (i >= w[t[k][j]])             // 背包容量充足
        dp[i] = max(dp[i],
                    dp[i - w[t[k][j]]] + c[t[k][j]]);//像0-1背包一样状态转移

6.有依赖的背包#

树形 DP 那里再填坑吧

插个传送锚点

7.结语#

背包类牢记基础方程（内容+推导）

然后就差不多了，其他DP后面填坑。