难 · 动态规划

0/1 背包

这张表你见过：best[c] = 容量 c 下的最优答案。凑硬币正着填，因为每种硬币无限供应；这里每件物品只有一个，正是这个事实把内层循环从正序翻成倒序。一个循环方向，就是「租」和「拥有」的差别。

一句话答案<code>best[c] = 容量 c 下的最大价值</code>；对每件物品，c 从 W <em>倒着</em>到 w：<code>best[c] = max(best[c], best[c-w] + v)</code>。倒序 = 每件一次。

题目

输入: 第一行是 n 和 W（1 ≤ n ≤ 20，1 ≤ W ≤ 1000）。接下来 n 行：w v，物品的重量（1 ≤ w ≤ 1000）和价值（1 ≤ v ≤ 1000）。

输出: 在总重量 ≤ W 的前提下能取得的最大总价值，每件物品至多拿一次。

样例:

输入输出
1 6
3 5		5
3 5
2 3
3 4
4 5		7

第一个样例就是复用探测器：一件重 3、价值 5 的物品，背包容量 6。拿两次会得 10 —— 正确答案是 5，而只有倒序循环能答对。

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 为什么倒序,一句话

best[c-w] + v 必须表示「不含本物品时的最优」。倒着扫 c 时，你读到的每个 best[c-w] 还是上一件物品那一行的旧值 —— 没被动过，所以本件不可能被算两次。正着扫时，best[c-w] 已经被本轮更新过：物品悄悄溜进来两次，第一个样例（答 10 而不是 5）专抓这个。

提示 2 — 表格自己清零

best 是全局数组，而本引擎不会自动清零（矩阵乘法 那课）。一个循环：for (c = 0; c <= W; c++) best[c] = 0;。空容量合法地持有价值 0 —— 整张表都从这个边界长出来。

提示 3 — 装不下的物品

比 W 还重的物品是合法输入，直接跳过即可 —— 从 W 倒到 w[i] 的循环天然做到这点，因为 w[i] > W 时循环体一次都不会执行。别急着过滤输入；循环边界本身就是过滤器。

题解（先自己试试！） 
#include <iostream>
using namespace std;

int best[1005];

int main() {
    int n, W;
    cin >> n >> W;
    int w[20], v[20];
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];

    for (int c = 0; c <= W; c++) best[c] = 0;

    for (int i = 0; i < n; i++) {
        for (int c = W; c >= w[i]; c--) {
            if (best[c - w[i]] + v[i] > best[c]) {
                best[c] = best[c - w[i]] + v[i];
            }
        }
    }

    cout << best[W] << endl;
    return 0;
}

把内层循环翻成正序，就得到 凑硬币 —— 无限供应，同一行代码换了套约定。这幅对称就是背包家族的族谱：这里 0/1，那里完全背包，再加一个维度（每件限购件数）就是多重背包。当 W 大到天文数字而 n 很小时，枚举子集 里的 2^n 暴力是备胎。

深度解析

为什么这样做对

best[c] = 用已处理物品、容量 c 下的最优价值。物品循环一次处理一件;容量循环必须倒序,这样读到的每个 best[c-w] 仍属于上一行 —— 「不含本物品」。倒序成就了 0/1;正序会让物品和自己配对,那正是完全背包(凑硬币)。

代价

时间 O(n × W) —— 20 × 1000 = 两万次转移 —— 空间 O(W)。按物品子集建表的替代方案要 2^20 张表;一维滚动技巧正是把物品维度压掉的那一步。

常见错法

  • 容量正序循环会复用物品:第一个样例(一件物品、答案 10 而不是 5)就是为抓这个造的。
  • 信任全局自动清零:本引擎不清零数组,best[c] = 0 必须显式写。
  • 输入或转移里 w、v 互换:best[c-w] 用重量,加上的项用价值 —— 一个符号换错,题目无声反转。

下一步

循环翻成正序就是 凑硬币 —— 无限供应的兄弟。倒序是 0/1;介于两者之间的每件限额版是多重背包。W 巨大而 n 很小时,枚举子集 的暴力兜底。

记住这两句

  • 容量倒序 = 每件一次;正序 = 无限。
  • 滚动表显式清零;INF/0 哨兵是 DP 的承重墙。
🐞 这段是错的 —— 点开,亲手让它挂一次

容量循环是正序 —— 每件物品都和自己配了对

#include <iostream>
using namespace std;

int best[1005];

int main() {
    int n, W;
    cin >> n >> W;
    int w[20], v[20];
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
    for (int c = 0; c <= W; c++) best[c] = 0;
    for (int i = 0; i < n; i++) {
        for (int c = w[i]; c <= W; c++) {   // bug: forward loop reuses items
            if (best[c - w[i]] + v[i] > best[c]) {
                best[c] = best[c - w[i]] + v[i];
            }
        }
    }
    cout << best[W] << endl;
    return 0;
}