01背包

01 背包

一、问题描述

有 $n$ 件物品和一个容量为 $V$ 的背包。第 $i$ 件物品的体积为 $v[i]$ ，价值为 $w[i]$ 。

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

“01”表示每件物品只有两种选择：不选，或者选一次。

例如，背包容量为 $V=5$ ，有以下三件物品：

物品编号	体积	价值
1		2
2	3	4
3	4	5

选择物品 1 和物品 3，总体积为 $1+4=5$ ，总价值为 $2+5=7$ ，这是最优方案。

本节中，体积均为正整数，价值为非负整数，允许背包没有装满，也允许一件物品都不选。

下面依次讨论三种写法：二维数组 dp[i][j]、用 g[] 备份上一轮状态、只用一个数组并倒序枚举容量。

二、二维 DP：`dp[i][j]`

1. 状态定义

需要同时记录两个信息：已经考虑了哪些物品，以及背包容量是多少。

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

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

这里的 $j$ 是容量上限，所选物品的总体积可以小于 $j$ 。

例如， $dp[2][5]$ 表示只考虑物品 1、2，容量上限为 $5$ 时的最大价值。选中这两件物品，总体积为 $4$ ，总价值为 $6$ ，所以 $dp[2][5]=6$ 。

2. 状态转移

考虑第 $i$ 件物品，按“选不选它”分成两种情况。

情况一：不选第 $i$ 件物品。

只能从前 $i-1$ 件物品中选择，容量上限仍为 $j$ ，最大价值为：

dp[i-1][j].

情况二：选择第 $i$ 件物品。

首先要求 $j\ge v[i]$ ，否则放不下这件物品。

选入它后，剩余容量为 $j-v[i]$ 。其余物品只能从前 $i-1$ 件中选择，最大价值为：

dp[i-1][j-v[i]]+w[i].

两种情况取最大值，得到：

$$dp[i][j]= \begin{cases} dp[i-1][j], & j<v[i],\\ \max\bigl(dp[i-1][j],\ dp[i-1][j-v[i]]+w[i]\bigr), & j\ge v[i]. \end{cases}$$

两个来源都在第 $i-1$ 行。 特别是选择第 $i$ 件物品时，其余方案还没有考虑过这件物品，所以它最多只会被选一次。

3. 初始化与答案

没有物品时，无论容量是多少，最大价值都是 $0$ ：

dp[0][j]=0,\qquad 0\le j\le V.

容量为 $0$ 时，由于物品体积均为正数，不能选择任何物品：

dp[i][0]=0,\qquad 0\le i\le n.

按物品编号从小到大计算，每一行都只依赖上一行。最终答案为 $dp[n][V]$ 。

4. 示例

对于前面的三件物品，状态表如下：

已考虑的物品 / 容量 $j$	0	1	3	4	5
无物品： $dp[0][j]$	0	0
前 1 件： $dp[1][j]$		2	2
前 2 件： $dp[2][j]$			4	6	6
前 3 件： $dp[3][j]$			4	6	7

例如计算 $dp[3][5]$ ：

不选物品 3： $dp[2][5]=6$ 。
选择物品 3： $dp[2][1]+5=2+5=7$ 。

所以 $dp[3][5]=7$ 。

注意， $dp[3][4]=6$ ，对应选择物品 1、2。虽然物品 3 也能放进容量为 $4$ 的背包，但只选它的价值为 $5$ ，因此保留原来的方案。

5. 参考代码

三份代码使用相同的输入输出格式：第一行输入 $n,V$ ，接下来 $n$ 行，每行输入一件物品的体积和价值。输出最大总价值。

代码约定 $1\le n\le1000$ 、 $0\le V\le1000$ 、 $1\le v[i]\le1000$ 、 $0\le w[i]\le10^6$ 。所有数组均为全局数组，初始值为 $0$ 。

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

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

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

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

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= V; ++j) {
            // 不选第 i 件物品
            dp[i][j] = dp[i - 1][j];

            // 选择第 i 件物品
            if (j >= v[i]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
            }
        }
    }

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

时间复杂度为 $O(nV)$ ，空间复杂度为 $O(nV)$ 。

三、备份数组优化：用 `g[]` 保存上一轮状态

1. 为什么可以只保留上一行？

计算第 $i$ 行时，只会用到第 $i-1$ 行。因此，更早的行可以不保存。

用一维数组 dp[j] 保存状态。处理每件物品之前，先用 memcpy 把容量 $0$ 到 $V$ 的状态复制到 g[]：

memcpy(g, dp, (V + 1) * sizeof(dp[0]));

使用 memcpy 需要包含头文件 <cstring>。它的三个参数依次为目标地址、源地址和复制的字节数。这里共有 $V+1$ 个状态，每个状态占 sizeof(dp[0]) 字节。

在处理第 $i$ 件物品的这一轮中：

g[j] 始终保存二维写法中的 $dp[i-1][j]$ ，本轮不修改。
dp[j] 用来计算二维写法中的 $dp[i][j]$ 。

2. 转移写法

把二维转移中的上一行全部换成备份数组 g[]：

for (int j = 0; j <= V; ++j) {
    dp[j] = g[j];  // 不选当前物品
    if (j >= v[i]) {
        dp[j] = max(dp[j], g[j - v[i]] + w[i]);
    }
}

先完整备份，再开始转移。 这样每次读取 g[j-v[i]]，拿到的都是处理当前物品之前的状态。

例如处理物品 3 前，备份为：

容量 j： 0  1  2  3  4  5
g[j]：  0  2  2  4  6  6

计算容量 $5$ 时，读取 g[5] 和 g[1]，得到 $\max(6,2+5)=7$ 。

由于 g[] 在整轮中保持不变，容量可以正序枚举，也可以倒序枚举。

3. 参考代码

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

const int N = 1005;
int n, V;
int v[N], w[N];
int dp[N], g[N];

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

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

    for (int i = 1; i <= n; ++i) {
        // 保存上一轮的全部状态
        memcpy(g, dp, (V + 1) * sizeof(dp[0]));

        // 从 g 读取上一轮状态，向 dp 写入本轮状态
        for (int j = 0; j <= V; ++j) {
            dp[j] = g[j];
            if (j >= v[i]) {
                dp[j] = max(dp[j], g[j - v[i]] + w[i]);
            }
        }
    }

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

每件物品需要一次备份和一次转移，总时间复杂度仍为 $O(nV)$ 。只保存两个长度为 $V+1$ 的状态数组，DP 的空间复杂度降为 $O(V)$ 。

四、容量倒序枚举：只用一个 `dp[]`

1. 去掉 `g[]` 后的问题

如果直接去掉备份数组，把转移写成：

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

就必须保证右边读取的仍是上一轮状态。否则，dp[j-v[i]] 可能已经在本轮加入了第 $i$ 件物品，再加一次 w[i] 就会重复选择它。

2. 正序更新的反例

假设只有一件物品，体积为 $2$ ，价值为 $3$ ，背包容量为 $4$ 。

开始时 dp[] 全为 $0$ 。如果按 $j=2,3,4$ 的顺序更新：

更新容量	执行的计算	更新结果
$j=2$	`dp[2] = max(0, dp[0] + 3)`	`dp[2] = 3`
$j=3$	`dp[3] = max(0, dp[1] + 3)`	`dp[3] = 3`
$j=4$	`dp[4] = max(0, dp[2] + 3)`	`dp[4] = 6`

计算 dp[4] 时，读到了本轮刚更新的 dp[2]=3。这个状态已经选过当前物品，再加 $3$ 就相当于把同一件物品选了两次。

正确答案应为 $3$ ，正序更新却得到 $6$ 。

3. 倒序为什么正确？

因为物品体积为正数，所以 $j-v[i]<j$ 。

容量从大到小枚举时，较小的容量还没有在本轮更新，因此 dp[j-v[i]] 仍是上一轮状态。 当前的 dp[j] 也还未更新，恰好保留“不选当前物品”的结果。

仍看上面的例子，按 $j=4,3,2$ 的顺序更新：

更新容量	读取的上一轮状态	更新结果
$j=4$	`dp[2] = 0`	`dp[4] = 3`
$j=3$	`dp[1] = 0`	`dp[3] = 3`
$j=2$	`dp[0] = 0`	`dp[2] = 3`

这样就保证了每件物品最多选择一次。

对于 $j<v[i]$ ，当前物品放不下，状态应保持原值。因此只需枚举 $j=V,V-1,\ldots,v[i]$ 。

4. 参考代码

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

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

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

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

    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]);
        }
    }

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

时间复杂度为 $O(nV)$ ，DP 的空间复杂度为 $O(V)$ 。两种一维代码都保存了物品数组，因此代码的总空间复杂度为 $O(n+V)$ ；若读入一件物品后立即处理，就可以将总空间降为 $O(V)$ 。

五、三种写法的联系

写法	上一轮状态保存在哪里	容量枚举顺序	DP 空间复杂度
二维数组 `dp[i][j]`	第 $i-1$ 行	正序、倒序均可	$O(nV)$
`dp[]` 加备份数组 `g[]`	固定不变的 `g[]`	正序、倒序均可	$O(V)$
只用 `dp[]`	数组中本轮尚未更新的位置	倒序	$O(V)$

三种写法实现的是同一个转移，关键都在于：选择当前物品时，必须从还没有考虑当前物品的状态转移。

注意本节的状态表示“总体积不超过容量”。如果题目要求恰好装满，初始化需要另外讨论，不能直接照搬全 $0$ 的初始化。

六、恰好装满的 01 背包

1. 问题描述

仍然有 $n$ 件物品，第 $i$ 件物品的体积为 $v[i]$ ，价值为 $w[i]$ ，每件物品最多选择一次。

这次要求所选物品的总体积恰好等于 $V$ ，在满足这一条件的方案中，求最大总价值。如果不存在这样的方案，需要报告无法恰好装满。

例如，背包容量为 $3$ ，有两件物品：

物品编号	体积	价值
1	2	100
2	3	1

如果允许没有装满，选择物品 1 可以得到价值 $100$ ；要求恰好装满时，只能选择物品 2，答案为 $1$ 。

本节继续约定物品体积为正整数，价值为非负整数，数据范围与前面相同。

2. 状态含义

二维状态改为：

$dp[i][j]$ 表示只从前 $i$ 件物品中选择，总体积恰好等于 $j$ 时，能够得到的最大总价值。

如果没有任何方案的总体积恰好为 $j$ ，就把这个状态标记为不可达。

压缩成一维后，dp[j] 表示已经考虑过的物品中，总体积恰好为 $j$ 时的最大价值。

3. 为什么不能全部初始化为 0？

在尚未选择任何物品时：

总体积为 $0$ ：可以通过一件物品都不选实现，价值为 $0$ 。
总体积大于 $0$ ：没有方案能够实现，应该标记为不可达。

如果全部初始化为 $0$ ，就等于认为每个体积都已经存在价值为 $0$ 的合法方案。后续转移会从这些不存在的方案出发，产生错误答案。

例如，只有一件体积为 $2$ 、价值为 $3$ 的物品，要求装满容量 $3$ 。若初始 dp[1]=0，就会算出 dp[3]=dp[1]+3=3，但实际上根本无法装满。

因此，初始状态应为：

dp[0]=0,\qquad dp[j]=-\infty\quad(1\le j\le V).

程序中用一个足够小的负数表示不可达，按下面的方式初始化：

memset(dp, 0x80, sizeof(dp));
dp[0] = 0;

memset 需要包含头文件 <cstring>。它按字节填充内存，这里把数组的每一个字节都设为 0x80。在常见的 32 位补码 int 环境下，每个元素的位模式为 0x80808080，对应 $-2139062144$ ，可以作为本题的不可达标记。

注意，这并不是把每个元素设为十进制的 $128$ 。代码中先将整个数组设为很小的负数，再单独把 dp[0] 设为 $0$ 。

4. 状态转移

仍然按照当前物品选或不选进行转移：

dp[j]=\max\bigl(dp[j],\ dp[j-v[i]]+w[i]\bigr).

其中，dp[j] 原来的值表示不选第 $i$ 件物品；dp[j-v[i]]+w[i] 表示在总体积恰好为 $j-v[i]$ 的方案中加入当前物品，使总体积恰好为 $j$ 。

只有来源状态可达时，才能选择当前物品进行转移。 本节价值均为非负数，因此可达状态的最大价值一定不小于 $0$ ，可以这样判断：

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

容量仍然倒序枚举，保证每件物品最多选择一次。如果来源不可达，就不进行这次转移，保留 dp[j] 的原值。

例如，容量为 $5$ ，两件物品分别为“体积 $2$ 、价值 $3$ ”和“体积 $3$ 、价值 $4$ ”，状态变化如下：

已考虑的物品 / 恰好使用的体积 $j$	0	1	2	3	4	5
无物品	0	$-\infty$	$-\infty$	$-\infty$	$-\infty$	$-\infty$
前 1 件			3	$-\infty$		$-\infty$
前 2 件			3	4		7

这里的 $-\infty$ 表示不可达。处理物品 2、计算体积 $5$ 时，从 dp[2]=3 转移，得到 dp[5]=7。体积 $4$ 则始终无法恰好凑出。

5. 答案判断

处理完所有物品后，只检查 dp[V]：

dp[V] >= 0：存在恰好装满的方案，答案为 dp[V]。
dp[V] < 0：无法恰好装满。

不能用 dp[V] == 0 判断无解，因为恰好装满的方案也可能价值为 $0$ 。当 $V=0$ 时，空集就是合法方案，答案也为 $0$ 。

6. 参考代码

输入格式与前面相同。这里约定无法恰好装满时输出 -1，否则输出最大价值。

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

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

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

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

    memset(dp, 0x80, sizeof(dp));
    dp[0] = 0;

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

    if (dp[V] < 0) {
        cout << -1 << '\n';
    } else {
        cout << dp[V] << '\n';
    }
    return 0;
}

时间复杂度为 $O(nV)$ ，DP 的空间复杂度为 $O(V)$ 。代码还保存了所有物品，总空间复杂度为 $O(n+V)$ 。

7. 与“不超过容量”的写法对照

比较内容	总体积不超过 $j$	总体积恰好等于 $j$
初始 `dp[0]`	$0$	$0$
初始 `dp[j]`， $j>0$	$0$	$-\infty$ ，表示不可达
转移来源	所有容量状态初始都可达	只能从可达状态转移
容量枚举顺序	倒序
最终答案	`dp[V]`	先判断 `dp[V]` 是否可达

两种问题使用相同的选与不选转移。初始化决定了初始时哪些状态合法，从而保证后续转移符合各自的状态定义。

上面的 >= 0 和 < 0 判断依赖价值非负的约定。如果允许负价值，就需要另用不可达标记或可达性数组进行判断。