0-1 背包问题

15 Dec 2024

1. 问题描述

0/1 背包问题中，有 n 件物品和一个容量为 m 的背包。第 i 件物品的体积为 volume[i]，价值为 value[i]。每件物品只有“选”或“不选”两种情况，最多只能选一次；目标是在总体积不超过背包容量的前提下，让总价值最大。

直接枚举每件物品选或不选会有 2ⁿ 种可能。动态规划把这些选择过程中重复出现的子问题保存下来，从而避免重复计算。

2. 状态与转移

定义 f[j] 为“当前已经考虑过的物品中，背包容量不超过 j 时能得到的最大价值”。处理一件体积为 v、价值为 w 的物品时，有两种选择：

不选它，f[j] 保持原来的值。
选择它，前面只能使用容量 j - v，得到的价值是 f[j - v] + w。

因此，当 j >= v 时，转移为：

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

容量 j 必须从大到小枚举。这样计算 f[j] 时，f[j - v] 仍然是“还没有使用当前物品”的旧状态，当前物品最多只会被选一次。若从小到大枚举，同一件物品可能在同一轮被重复使用，那就变成了完全背包问题。

3. 例子：最大价值

下面的程序读入背包容量、物品数量，以及每件物品的体积和价值，输出可获得的最大价值。输入格式与洛谷 P1048 采药相同：先输入容量和物品数。

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;
int f[N];

int main() {
    int capacity, n;
    cin >> capacity >> n;

    for (int i = 1; i <= n; i++) {
        int volume, value;
        cin >> volume >> value;

        for (int j = capacity; j >= volume; j--) {
            f[j] = max(f[j], f[j - volume] + value);
        }
    }

    cout << f[capacity];
    return 0;
}

例如，背包容量为 4，有三件物品：(2, 3)、(1, 2)、(3, 4)，其中每对数依次表示体积和价值。选择第二件和第三件物品时，总体积为 4、总价值为 6，因此答案是 6。

这个一维写法的时间复杂度是 O(nm)，空间复杂度是 O(m)。0/1 背包的关键是先明确 f[j] 表示什么，再根据“选”与“不选”写出转移；最后记住容量要倒序遍历，才能保证每件物品只使用一次。

0-1 背包问题

Related Posts