背包 DP：0/1 与完全背包｜算法讲义

问题#

有容量为 $C$ 的背包，第 $i$ 类物品重量为 $w_i>0$ 、价值为 $v_i$ 。在总重量不超过 $C$ 的前提下最大化总价值：

0/1 背包：每件物品最多选择一次；
完全背包：每类物品可以选择任意多次；
多重背包（延伸阅读，非课程主线）：第 $i$ 类物品最多选择 $c_i$ 次。

三种模型可以使用同一个一维状态：

dp[j]=\text{当前已经处理过的物品中，容量不超过 }j\text{ 时的最大价值}.

这里求的是“不超过容量”的最优值，所以 dp 可以全部初始化为 0。

核心思想与不变量#

0/1 背包：容量逆序#

二维转移为：

dp[i][j]=\max\bigl(dp[i-1][j],\ dp[i-1][j-w_i]+v_i\bigr).

压缩到一维后，容量必须从大到小枚举：

for each item i:
    for j = C ... w[i]:
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])

逆序保证读取的 dp[j-w[i]] 仍属于“处理第 $i$ 件物品之前”的上一层，因此当前物品不会被重复使用。不变量是：完成第 $i$ 轮后，dp[j] 是只使用前 $i$ 件物品的最优值。

完全背包：容量正序#

完全背包允许再次选择当前物品：

dp[i][j]=\max\bigl(dp[i-1][j],\ dp[i][j-w_i]+v_i\bigr).

一维数组中让容量从小到大枚举，读取的 dp[j-w[i]] 已经可能使用了当前物品，于是可以继续追加一件。

延伸阅读（非课程主线）：多重背包的二进制拆分#

若某类物品最多有 $c$ 件，把数量拆成 $1,2,4,\ldots$ 和最后的余数。比如 $13=1+2+4+6$ ，可变成四件重量、价值分别放大对应倍数的 0/1 物品。

任意 $0\le x\le c$ 都能由这些组选择得到，因此有限数量约束被转换为 0/1 背包；一类物品只产生 $O(\log(c+1))$ 个组。

复杂度#

设物品种类数为 $n$ 、容量为 $C$ ：

0/1 背包：时间 $O(nC)$ ，空间 $O(C)$ ；
完全背包：时间 $O(nC)$ ，空间 $O(C)$ ；
延伸阅读中的二进制拆分多重背包：时间 $O(C\sum_i\log(c_i+1))$ ，空间 $O(C)$ 。

这些复杂度是伪多项式：它们关于容量数值 $C$ 是线性的，并非关于 $C$ 的二进制位数是线性的。

C++17 模板#

#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <vector>

using namespace std;

struct Item {
    int weight;
    long long value;
};

struct BoundedItem {
    int weight;
    long long value;
    int count;
};

void validate(int capacity, const vector<Item>& items) {
    if (capacity < 0) throw invalid_argument("capacity must be non-negative");
    for (const Item& item : items) {
        if (item.weight <= 0) throw invalid_argument("weight must be positive");
    }
}

long long zero_one_knapsack(int capacity, const vector<Item>& items) {
    validate(capacity, items);
    vector<long long> dp(capacity + 1, 0);
    for (const Item& item : items) {
        for (int current = capacity; current >= item.weight; --current) {
            dp[current] = max(dp[current], dp[current - item.weight] + item.value);
        }
    }
    return dp[capacity];
}

long long complete_knapsack(int capacity, const vector<Item>& items) {
    validate(capacity, items);
    vector<long long> dp(capacity + 1, 0);
    for (const Item& item : items) {
        for (int current = item.weight; current <= capacity; ++current) {
            dp[current] = max(dp[current], dp[current - item.weight] + item.value);
        }
    }
    return dp[capacity];
}

long long multiple_knapsack(int capacity, const vector<BoundedItem>& items) {
    // 延伸阅读（非课程主线）：把有限数量拆成若干 0/1 物品组。
    vector<Item> groups;
    for (const BoundedItem& item : items) {
        if (item.weight <= 0 || item.count < 0) {
            throw invalid_argument("weight must be positive and count non-negative");
        }

        int remaining = item.count;
        for (int bundle = 1; remaining > 0; bundle *= 2) {
            int take = min(bundle, remaining);
            groups.push_back({item.weight * take, item.value * take});
            remaining -= take;
            if (bundle > remaining) bundle = remaining; // 防止下一次翻倍溢出
        }
    }
    return zero_one_knapsack(capacity, groups);
}

int main() {
    const int capacity = 6;
    vector<Item> items = {{2, 3}, {3, 4}, {4, 5}};
    cout << "0/1 = " << zero_one_knapsack(capacity, items) << '\n';
    cout << "complete = " << complete_knapsack(capacity, items) << '\n';

    // 延伸阅读（非课程主线）演示。
    vector<BoundedItem> bounded = {{2, 3, 1}, {3, 4, 2}, {4, 5, 1}};
    cout << "multiple (extension) = "
         << multiple_knapsack(capacity, bounded) << '\n';
    return 0;
}

示例#

模板输出：

0/1 = 8
complete = 9
multiple (extension) = 8

0/1 背包选择重量 $2$ 和 $4$ 的物品，价值为 $3+5=8$ ；
完全背包选择三件重量 $2$ 的物品，价值为 $9$ ；
延伸示例中的多重背包受数量限制，最优值回到 $8$ 。

易错点#

最常见错误就是循环方向写反：0/1 逆序、完全正序。先从二维转移判断读取的是上一层还是本层，再决定方向。
dp[j] 表示“容量至多为 $j$ ”时可以全初始化为 0；若要求“恰好装满”，除 dp[0]=0 外应初始化为负无穷。
价值和可能超过 int，状态使用 long long。
重量为 0 时，完全背包可能出现无限价值；常规模板要求重量严格为正。
多重背包拆分的是数量，组的重量和价值都必须同时乘以 take。
不能在遍历物品之前枚举容量并随意交换两层循环；这会改变组合计数或物品使用次数的含义。

问题#