作业详情 - tarjanoj

0 - 1 背包

题意概要：有 $n$ 个物品和一个容量为 $W$ 的背包，每个物品有重量 $w_{i}$ 和价值 $v_{i}$ 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

设 DP 状态 $f_{i,j}$ 为在只能放前 $i$ 个物品的情况下，容量 不超过 $j$ 的情况下所能达到的最大总价值。

考虑转移。假设当前已经处理好了前 $i-1$ 个物品的所有状态，那么对于第 $i$ 个物品:

当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 $f_{i-1,j}$
当其放入背包时，背包的剩余容量会减小 $w_{i}$ ，背包中物品的总价值会增大 $v_{i}$ ，故这种情况的最大价值为 $f_{i-1,j-w_{i}}+v_{i}$

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

f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_{i}}+v_{i})

for (int i = 1; i <= n; i++)
{
    for (int j = 0; j <= W; j++)
    {
        f[i][j] = f[i - 1][j];
        if (j >= w[i]) 
            f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]); 
    }
}

时间复杂度和空间复杂度均为 $O(nW)$ 。

动态规划问题的空间优化

滚动数组优化

回顾 $0-1$ 背包问题的转移方程

f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_i}+v_i)

当计算前 $i$ 个物品在不同容量下的信息只需要知道前 $i-1$ 个物品在不同容量下的信息。

根本无需知道之前计算好的 $i-2,i-3,\dots$ 的信息，因此这些信息是多余的，完全可以省去。

故而第一维的数组大小只需要开到 $2$ 即可，在计算新的状态时只需要用上一次循环计算的状态来计算，下一次就重新覆盖掉不停的更新迭代。

常见的写法就是分奇数偶数交替，通过位运算 $\&\ 1$ 来完成。即

for (int i = 1; i <= n; i++)
{
    for (int j = 0; j <= W; j++)
    {
        f[i & 1][j] = f[i - 1 & 1][j];
        if (j >= w[i]) 
            f[i & 1][j] = max(f[i & 1][j], f[i - 1 & 1][j - w[i]] + v[i]); 
    }
}
cout << f[n & 1][W];

降维优化

降维优化的意思是可以直接去掉第一维，当一个 DP 问题的转移只跟上一层有关时，是可以这么去做的。

即将状态转移方程修改为如下内容：

f_j=\max \left(f_j,f_{j-w_i}+v_i\right)

需要注意的是接下来的循环顺序问题

错误写法如下所示

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

例如有 $1$ 个物品，价值和体积分别为 $[1,2]$ ，背包的容量为 $4$ 。

当 $i=1$ 的时候：根据我们上述代码，易得 $f_0=0,f_1=0,f_2=f_0+1=1,f_3=f_1+1=1,f_4=f_2+1=2$ 。
注意到 $f_4$ 的结果是 $2$ ，但是只有 $1$ 个物品，怎么可能价值为 $2$ ？
因为物品 $1$ 使用了 $2$ 次，我们 $f_4$ 是在 $f_2$ 的基础上再加入了一次物品 $1$ 得来的，而 $f_2$ 的计算已经使用过一次物品 $1$ 了。

这显然违反了每个物品只能使用一次的原则，因此当每个物品只能 选取一次 的时候，需要注意一定要用 未更新的状态 来更新 现有的，故而需要将第二层循环倒序枚举。

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

如此一来，针对上述例子，先计算 $f_4=f_2+1=0+1=1$ ，随后再去计算 $f_3,f_2,f_1,f_0$ 这样才可以保证每个物品选取 $1$ 次。

时间复杂度： $O(nW)$ ，空间复杂度： $O(W)$ 。

完全背包

注意：每个物品可以选取无限次，这是和 [0 - 1] 背包的区别所在。

状态设计

$f_{i,j}$ 只能放前 $i$ 个物品的情况下，容量 不超过 $j$ 的情况下所能达到的最大总价值。

状态转移

朴素的转移思路是由于每个物品有无限种选择（实际是有限的，毕竟容量有限），所以枚举每个物品选了几次。从所有的情况取 $\max$

首先选 $0$ 个，就是不选，所以就是 $f_{i-1,j}$
选 $1$ 个，就是 $f_{i-1,j-w_i}+v_i$
选 $2$ 个，就是 $f_{i-1,j-2 * w_i}+v_i * 2$
$\cdots$
选 $s$ 个，就是 $f_{i-1,j-s * w_i}+v_i * s$ ，其中 $s=\lfloor \frac{W}{w_i} \rfloor$

$$f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_i}+v_i,f_{i-1,j-2 * w_i}+v_i * 2,\cdots,f_{i-1,j-s * w_i}+v_i * s) $$

这样一来显然转移的复杂度不再是 $O(1)$ ，因此尝试进行优化。这里的优化可以从另一个状态 $f_{i,j-w_i}$ 看出端倪。

研究一下状态 $f_{i,j-w_i}$ 的求解。

首先选 $0$ 个，就是不选，所以就是 $f_{i-1,j-w_i}$
选 $1$ 个，就是 $f_{i-1,j-2*w_i}+v_i$
选 $2$ 个，就是 $f_{i-1,j-3 * w_i}+v_i * 2$
$\cdots$
选 $s$ 个，就是 $f_{i-1,j-s * w_i}+v_i * (s-1)$ ，其中 $s=\lfloor \frac{W}{w_i} \rfloor$

$$f_{i,j-w_i}=\max(f_{i-1,j-w_i},f_{i-1,j-2*w_i}+v_i,f_{i-1,j-3 * w_i}+v_i * 2,\cdots,f_{i-1,j-s * w_i}+v_i * (s-1)) $$

对比一下这两个不同的状态转移：

$$\begin{aligned} f_{i,j}&=\max(f_{i-1,j},\underbrace{f_{i-1,j-w_i}+v_i,f_{i-1,j-2 * w_i}+v_i * 2,\cdots,f_{i-1,j-s * w_i}+v_i * s})\\ f_{i,j-w_i}&=\max(\underbrace{f_{i-1,j-w_i},f_{i-1,j-2*w_i}+v_i,f_{i-1,j-3 * w_i}+v_i * 2,\cdots,f_{i-1,j-s * w_i}+v_i * (s-1)}) \end{aligned}$$

对比之后可以发现， $f_{i,j}$ 括起来的部分实际就是 $f_{i,j-w_i}$ 的基础上多加一个 $v_i$ ，因此我们可以将 $f_{i,j}$ 的转移方程化简为：

这样可以 $O(1)$ 转移。

f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i)

朴素写法

for (int i = 1; i <= n; i++)
{
    for (int j = 0; j <= W; j++)
    {
        f[i][j] = f[i - 1][j];
        if (j >= w[i]) f[i][j] = max(f[i][j], f[i][j - w[i]] + v[i]); 
    }
}

滚动数组写法

for (int i = 1; i <= n; i++)
{
    for (int j = 0; j <= W; j++)
    {
        f[i & 1][j] = f[i - 1 & 1][j];
        if (j >= w[i]) 
            f[i & 1][j] = max(f[i & 1][j], f[i & 1][j - w[i]] + v[i]); 
    }
}

降维写法

小技巧：只有完全背包正序枚举容量。

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

多重背包

题意概述：多重背包就是在 [0 - 1] 背包的基础上，添加了每个物品可以选择 $k_i$ 次的设定。

每个物品可以选择 $0,1,2,\dots,k_i$ 个，这里的 $k_i$ 不一定和 $\lfloor \frac{W}{v_i} \rfloor$ 相同，因此不能按照完全背包的方式实现 $O(1)$ 的转移。

状态设计依然都是背包问题统一的状态设计，即 $f_{i,j}$ 为前 $i$ 个物品背包容量不超过 $j$ 的最大价值。

转移自然需要枚举每个物品用了多少个：

若用了 $0$ 个，转移到 $f_{i-1,j}$
若用了 $1$ 个，转移到 $f_{i-1,j-w_i}+v_i$
若用了 $2$ 个，转移到 $f_{i-1,j-2*w_i}+2*v_i$
$\cdots$
若用了 $k_i$ 个，转移到 $f_{i-1,j-k_i*w_i}+k_i*v_i,j\geq k_i*v_i$

$$f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_i}+v_i,f_{i-1,j-w * v_i}+v_i * 2,\dots,f_{i-1,j-k_i * w_i}+k_i * v_i) $$

举例说明多重背包不能沿用完全背包的优化思路。

$$f_{i,j}=\max(f_{i-1,j},\underbrace{f_{i-1,j-v_i}+w_i,f_{i-1,j-2 * v_i}+w_i * 2,\dots,f_{i-1,j-k_i * v_i}+k_i * w_i}) $$$$f_{i,j-v_i}=\max(\underbrace{f_{i-1,j-v_i},f_{i-1,j-2*v_i}+w_i,\cdots,f_{i-1,j-k_i*v_i}+(k_i-1)*w_i},f_{i-1,j-(k_i+1)*v_i}+k_i*w_i) $$

由于这里 $k_i$ 不一定是把背包塞满的，那么 $f_{i,j-v_i}$ 的转移就会多出了一项，此时是没法像完全背包一样直接替换的。

写法一

先枚举状态，然后第三维枚举转移选择几个物品。

for (int i = 1; i <= n; i++)
{
    int v, w, m;
    cin >> v >> w >> m;
    // 价值 v，体积 w，数量 m
    for (int j = W; j >= 0; j--)
    {
        for (int k = 1; k <= m; k++)
        {
            if (j >= k * w)
            {
                f[j] = max(f[j], f[j - k * w] + k * v);
            }
        }
    }
}

写法二

先枚举选择几个，然后枚举容量，注意二者写法区别。

for (int i = 1; i <= n; i++)
{
    int v, w, m;
    cin >> v >> w >> m;
    // 价值 v，体积 w，数量 m
    for (int k = 1; k <= m; k++)
    {
        for (int j = W; j >= 0; j--)
        {
            if (j >= w)
            {
                f[j] = max(f[j], f[j - w] + v);
            }
        }
    }
}

其他背包问题常见模型总结

状态定义： $f_j$ 为前 $i$ 个物品容量对应为 $j$ 的最大价值。常见的对容量有三种限制分别如下：

不超过背包容量限制

初始化：求解最大值全部初始化为 $0$ ，求解最小值全初始化无穷小， $f_0$ 需要初始化为 $0$

转移：求解时保证 $j\geq v$ 方可求解 $f_j$ ，即

f_j=\max(f_j,f_{j-w_i}+v_i)

恰好装满背包

初始化：只有 $f_0=0$ 其余若求最大值初始负无穷，求最小值初始化正无穷。

转移：求解时保证 $j\geq w_i$ 方可求解 $f_j$ ，即

f_j=\max(f_j,f_{j-w_i}+v_i)

体积至少是的情况

初始化：只有 $f_0=0$ 其余若求最大值初始负无穷，求最小值初始化正无穷。

转移：转移的时候可以从 $j< w_i$ 的转移，即 $f_{\max(0,j-w_i)}$ 这样转移。

即

f_j=\max(f_j,f_{\max(0,j-w_i)}+v_i)

多重背包的二进制优化

引入：至少需要几枚什么数值的硬币，即可表示出 $0\sim 100$ 所有面值？

答案是 $7$ $7$ 枚，只需要 $1,2,4,8,16,32,37$ $1, 2, 4, 8, 16, 32, 37$ 这 $7$ $7$ 枚即可。它们互相组合即可表示出 $0\sim 100$ $0 \sim 100$ 的所有结果。
- $6=1+2+3$
- $8=1+2+4+1$
- $18=1+2+4+8+3$
- 这种优化方式称为二进制优化。

注意：并不是把一个十进制数字的所有二进制位全部存储进去，这样有可能会造成物品多选的情况。

例如 $2$ 的二进制为 $10$ ，二进制拆分是拆成 $2$ 个 $1$ 的物品，这样可以凑出 $0,1,2$ 三种情况。

而不是拆成 $1$ 和 $2$ 这样虽然也可以凑出 $0,1,2$ 但是还可以凑出 $1+2=3$ 等于多选了一次。

具体做法是将物品个数二进制拆分以后重新保存起来，例如 $6$ 个物品拆分成 $1,2,3$ 以后那么它们对应的价值和体积分别是 $v,2v,3v$ 和 $w,2w,3w$ 。

对这些物品重新去做 $0-1$ 背包即可。这样做的时间复杂度为 $O(n\cdot \log{m}\cdot W)$ ，其中 $m$ 为物品使个数上限。

写法一：把每个物品真正创建出来

for (int i = 1; i <= n; i++)
{
    int v, w, m;
    cin >> v >> w >> m;
    int s = 1;
    while (m - s > 0)
    {
        a[++cnt] = s * w, b[cnt] = s * v;
        m -= s;
        s *= 2; 
    } 
    if (m)
    {
        a[++cnt] = m * w, b[cnt] = m * v;
    } 
}

写法二：直接循环去做

for (int i = 1; i <= n; i++)
  {
      int v, w, m;
      cin >> v >> w >> m;
      for (int k = 1; k <= m; k *= 2)
      {
          for (int j = t; j >= k * w; j--)
          {
              f[j] = max(f[j], f[j - k * w] + k * v);
          }
          m -= k;
      }
      if (m) // 有剩余
      {
          for (int j = t; j >= m * w; j--)
          {
              f[j] = max(f[j], f[j - m * w] + m * v);
          }
      }
  }

其余例题选讲

[USACO08NOV] Buying Hay S

完全背包至少是模型

A+B Problem（再升级）

01背包求方案数模型

[USACO03FALL] Cow Exhibition G

状态设计： $f_j$ 为前 $i$ 头牛智商恰好为 $j$ 情商最大为多少。
状态转移： $f_j=\max(f_j,f_{j-s}+f)$
答案：枚举智商 $j$ ，若 $f_j\geq 0$ ，则说明智商和情商均非负就保证了，然后对总和求 $\max$ 。
注意智商和情商的范围是 $-40000\sim 40000$ $- 40000 \sim 40000$ 。下标有负数。
- DP 数组用 map
- 容量统一偏移增加 $40000$ 。
若 $s$ 为负，需要正序枚举容量保证每个物品只选一次。

[ABC364E] Maximum Glutton

状态设计： $f_{j,k}$ 为前 $i$ 道菜，吃了 $j$ 道，甜度恰好为 $k$ 对应下的咸度最小是多少。
状态转移： $f_{j,k}=\min(f_{j,k},f_{j-1,k-a_i}+b_i)$
答案：枚举 $j,k$ 求解答案即可。
注意求 $\min$ 的初始化问题。

[NOIP2012 普及组] 摆花

多重背包的方案数问题

状态设计： $f_{i,j}$ 为前 $i$ 种花，摆了 $j$ 盆的方案数。

认领作业后才可以查看作业内容。

状态: 正在进行…
题目: 14
开始时间: 2025-8-19 0:00
截止时间: 2026-8-11 23:59
可延期: 24 小时

作业介绍