完全背包

一、问题描述

有 $n$ 种物品和一个容量为 $V$ 的背包。第 $i$ 种物品的体积为 $w[i]$，价值为 $v[i]$，每种物品都有无限件，可以重复选择。

在所选物品总体积不超过 $V$ 的前提下，求能够得到的最大总价值。

与 01 背包相比，变化在于每种物品可以选择的数量：

• 01 背包：只能选 $0$ 件或 $1$ 件。
• 完全背包：可以选 $0,1,2,\ldots$ 件，直到容量不足。

为便于对比 $dp[i][j]$ 和 $dp[i][j-w[i]]$，本节用 w[i] 表示体积，v[i] 表示价值，与前一篇讲义的符号约定不同。

例如，背包容量为 $7$，有两种物品：

物品种类	体积 $w[i]$	价值 $v[i]$
1	2	3
2	3	5

选择两件第 1 种物品和一件第 2 种物品，总体积为 $2+2+3=7$，总价值为 $3+3+5=11$，这是最优方案。

本节允许背包没有装满，也允许一件物品都不选。约定 $1\le n\le5000$、$0\le V\le5000$、$1\le w[i]\le5000$、$0\le v[i]\le10^6$。

由于每件物品的体积至少为 $1$，最多能放 $5000$ 件物品，最大总价值可能达到 $5\times10^9$，需要用 long long 保存 DP 状态。

二、朴素做法：枚举第 i 种物品装几件

1. 状态定义

设 $dp[i][j]$ 表示：

只从前 $i$ 种物品中选择，总体积不超过 $j$ 时，能够得到的最大总价值。

这里的 $i$ 表示已经考虑了前多少种物品，同一种物品可以选多件。

没有物品时只能得到价值 $0$，容量为 $0$ 时不能放入任何物品，因此：

$$dp[0][j]=0,\qquad dp[i][0]=0.$$

最终答案为 $dp[n][V]$。

2. 枚举选择的件数

考虑第 $i$ 种物品，假设选择 $k$ 件：

• 占用体积 $k\cdot w[i]$。
• 获得价值 $k\cdot v[i]$。
• 其余物品只能从前 $i-1$ 种中选择，容量上限为 $j-k\cdot w[i]$。

因此，选择 $k$ 件时能获得的最大价值为：

$$dp[i-1][j-k\cdot w[i]]+k\cdot v[i].$$

需要满足 $k\cdot w[i]\le j$。枚举所有合法的 $k$，取最大值：

$$\boxed{ dp[i][j]=\max_{0\le k\le\lfloor j/w[i]\rfloor} \bigl(dp[i-1][j-k\cdot w[i]]+k\cdot v[i]\bigr). }$$

这里包含 $k=0$，对应不选择第 $i$ 种物品。

3. 朴素代码

输入第一行为 $n,V$，接下来 $n$ 行，每行输入一种物品的体积和价值。输出最大总价值。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 5005;
int n, V;
int w[N], v[N];
long long dp[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> V;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i] >> v[i];
    }

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

    cout << dp[n][V] << '\n';
    return 0;
}

数组定义在全局，初始值均为 $0$。1LL * k * v[i] 让价值的乘法使用 64 位整数，避免乘积溢出。

最坏情况下，物品体积均为 $1$。对于每个 $i,j$，需要枚举 $j+1$ 个件数，因此时间复杂度为 $O(nV^2)$，空间复杂度为 $O(nV)$。

这份代码适合小规模演示，在 $n,V$ 都达到 $5000$ 时需要进一步优化。

三、对比 dp[i][j] 和 dp[i][j-w[i]]

1. 展开 dp[i][j]

固定第 $i$ 种物品，设 $j\ge w[i]$，令 $m=\lfloor j/w[i]\rfloor$，表示当前最多能选 $m$ 件。

将朴素转移按照选择的件数展开：

$$\begin{aligned} dp[i][j]=\max\bigl(&dp[i-1][j],\\ &dp[i-1][j-w[i]]+v[i],\\ &dp[i-1][j-2w[i]]+2v[i],\\ &\ldots,\\ &dp[i-1][j-mw[i]]+mv[i]\bigr). \end{aligned}$$

这些候选依次对应第 $i$ 种物品选 $0,1,2,\ldots,m$ 件。

2. 展开 dp[i][j-w[i]]

容量减少了一个 $w[i]$，最多只能选 $m-1$ 件第 $i$ 种物品。套用同一个朴素转移式：

$$dp[i][j-w[i]]= \max_{0\le k\le m-1} \bigl(dp[i-1][j-(k+1)w[i]]+kv[i]\bigr).$$

给每个候选都加上一个 $v[i]$：

$$\begin{aligned} dp[i][j-w[i]]+v[i] &=\max_{0\le k\le m-1} \bigl(dp[i-1][j-(k+1)w[i]]+(k+1)v[i]\bigr)\\ &=\max_{1\le t\le m} \bigl(dp[i-1][j-tw[i]]+tv[i]\bigr). \end{aligned}$$

第二步把 $k+1$ 换成 $t$。这样就能看出：dp[i][j-w[i]] + v[i] 已经包含了原转移中选择 $1$ 件、$2$ 件、一直到 $m$ 件的全部候选。

两组候选可以直接对照：

第 $i$ 种物品选择的总件数	dp[i][j] 的候选	dp[i][j-w[i]] + v[i] 的候选
$0$	$dp[i-1][j]$	不包含
$1$	$dp[i-1][j-w[i]]+v[i]$	相同，来自较小容量下选 $0$ 件的情况
$2$	$dp[i-1][j-2w[i]]+2v[i]$	相同，来自较小容量下选 $1$ 件的情况
$t$，$1\le t\le m$	$dp[i-1][j-tw[i]]+tv[i]$	相同，来自较小容量下选 $t-1$ 件的情况

因此，除了“不选第 $i$ 种物品”的第一项，其他所有项的最大值已经由较小容量的同一行状态算出，无需重新枚举件数。

3. 得到优化后的转移

单独保留选择 $0$ 件的情况，其余情况合并，得到：

$$\boxed{ dp[i][j]=\max\bigl(dp[i-1][j],\ dp[i][j-w[i]]+v[i]\bigr), \qquad j\ge w[i]. }$$

如果 $j<w[i]$，连一件当前物品都放不下，只有不选这一种物品：

$$dp[i][j]=dp[i-1][j].$$

原来一个状态需要枚举多种件数，现在只需要比较两个值。时间复杂度由 $O(nV^2)$ 降为 $O(nV)$。

4. 为什么第二项使用第 i 行？

dp[i][j-w[i]] 可以从前 $i$ 种物品中选择，因此它的方案里可能已经包含第 $i$ 种物品。在这个方案上再放入一件当前物品，就能实现重复选择。

也可以从方案理解这个转移：

• 没有选择第 $i$ 种物品，最大价值为 dp[i-1][j]。
• 至少选择了一件第 $i$ 种物品，拿走其中一件后，剩余方案仍能从前 $i$ 种物品中选择，容量上限为 $j-w[i]$，对应 dp[i][j-w[i]]。

所以，第二种情况的最大价值为 dp[i][j-w[i]] + v[i]。

例如，对于前面的两种物品，在容量 $6$ 时，选择两件第 2 种物品可以得到价值 $10$。使用同一行的状态：

$$dp[2][6]=\max(dp[1][6],\ dp[2][3]+5)=\max(9,5+5)=10.$$

其中 dp[2][3] 已经选了一件第 2 种物品。如果错用上一行的 dp[1][3]，只能得到 $\max(9,3+5)=9$，就漏掉了重复选择第 2 种物品的方案。

注意，dp[i][j] 与 dp[i][j-w[i]] 的最优方案不一定恰好相差一件物品。上面的推导比较的是候选方案集合，只有原问题中“至少选一件当前物品”的部分，才与较小容量下的全部方案加上一件当前物品对应。

四、优化后的二维代码

转移使用了同一行、较小容量的状态，所以容量必须从小到大计算，保证 dp[i][j-w[i]] 已经求出。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 5005;
int n, V;
int w[N], v[N];
long long dp[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> V;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i] >> v[i];
    }

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

    cout << dp[n][V] << '\n';
    return 0;
}

时间复杂度为 $O(nV)$，空间复杂度为 $O(nV)$。上面两个二维版本中的 dp 数组约占 $191$ MiB，下面继续将其压缩成一维。

五、一维优化：容量正序枚举

1. 正序更新为什么正确？

将二维转移压缩成一维形式：

dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

处理第 $i$ 种物品时，从小到大枚举容量：

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

更新 dp[j] 时：

• dp[j] 还没有在本轮更新，保存上一行 dp[i-1][j]，对应不选当前物品。
• 如果 j-w[i] >= w[i]，dp[j-w[i]] 已经在本轮更新，保存当前行 dp[i][j-w[i]]，可以包含当前物品。
• 如果 j-w[i] < w[i]，这个容量放不下当前物品，上一行和当前行的答案相同，因此无需更新也能直接使用。

这样正好实现刚才推导出的二维转移。

2. 正序更新示例

只有一种物品，体积为 $2$、价值为 $3$，背包容量为 $6$。初始 dp[] 全为 $0$。

更新容量	转移	更新结果
$j=2$	dp[2] = max(0, dp[0] + 3)	$3$，选一件
$j=3$	dp[3] = max(0, dp[1] + 3)
$j=4$	dp[4] = max(0, dp[2] + 3)	$6$，选两件
$j=5$	dp[5] = max(0, dp[3] + 3)
$j=6$	dp[6] = max(0, dp[4] + 3)	$9$，选三件

后面的大容量状态使用本轮已经算出的较小容量状态，因此可以不断加入同一种物品。

3. 参考代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 5005;
int n, V;
int w[N], v[N];
long long dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> V;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i] >> v[i];
    }

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

    cout << dp[V] << '\n';
    return 0;
}

时间复杂度为 $O(nV)$，DP 的空间复杂度为 $O(V)$。由于代码还保存了物品数组，总空间复杂度为 $O(n+V)$；也可以每读入一种物品就立即处理，使总空间复杂度降为 $O(V)$。

六、与 01 背包对照

下面统一用 w[i] 表示体积，v[i] 表示价值：

比较内容	01 背包	完全背包
每种物品允许选几件	$0$ 或 $1$	$0,1,2,\ldots$
二维转移中“选一件”的来源	dp[i-1][j-w[i]]	dp[i][j-w[i]]
来源能否包含当前物品	不能	可以
一维写法的容量枚举顺序	倒序	正序

完全背包的优化利用了重复计算：dp[i][j-w[i]] + v[i] 已经覆盖选择当前物品至少一件的全部情况，因而可以省去枚举件数的第三重循环。