Day 26 · 0/1 背包：为什么要倒序枚举容量

题意：有 T 的时间可以采药，山洞里有 M 株草药，采第 i 株要花 w_i 的时间、得到 v_i 的价值。每株最多采一次（采完就没了），问在 T 时间内能获得的最大总价值。

思路

这是 0/1 背包的教科书模板题，把题目里的词一一对应过去就行：

四步法：① dp[j] = 用时不超过 j 能采到的最大价值；② dp[j] = max(dp[j], dp[j-w[i]] + v[i])； ③ dp 全 0（不超过时间，闲着也行）；④ 答案 dp[T]。内层容量倒序。

70 3
71 100
69 1
1 2

3

第一株要 71 的时间，超过了 70，采不了；剩下两株 69 + 1 = 70 正好用完时间，价值 1 + 2 = 3。

完整代码

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

int w[105], v[105];      // w[i] 采药时间，v[i] 价值
int dp[1005];            // dp[j]：容量（时间）为 j 时的最大价值

int main(){
    int T, M;
    cin >> T >> M;
    for(int i = 1; i <= M; i++)
        cin >> w[i] >> v[i];

    for(int i = 1; i <= M; i++)
        for(int j = T; j >= w[i]; j--)                   // ★ 容量必须倒序枚举
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

    cout << dp[T] << endl;
    return 0;
}

易错点

• 输入读反：第一个数是时间 T，第二个才是草药数 M。
• 内层写成正序 for(j = w[i]; j <= T; j++)：那就变成完全背包（每株能采无限次），样例就过不去。
• dp 数组开太小：值域是时间 T（最大 1000），不是草药数 M（最大 100）。按 M 开 105 会越界。
• 写成"按性价比贪心"：本题物品不可分割，贪心是错的（本文第 1 节给了反例实测）。

题意：箱子容量为 V，有 n 个物品，每个物品有一个体积。从中任取若干个装进箱子（也可以一个都不取），使箱子剩余空间最小，输出这个最小值。

思路

题目要「剩余空间最小」，也就是「装进去的总体积尽量大」。所以我们干脆把物品的体积当成价值：

重量 = v[i]，价值 = v[i]　→　跑一遍 0/1 背包 →　答案 = V − dp[V]

这样 dp[V] 就是"容量不超过 V 时能装进去的最大体积"，再用总容量一减就是剩余空间。

换个角度理解：这题本质是子集和问题——问"哪些体积 s 能被某些物品凑出来"，然后找 ≤ V 的最大 s。背包的 dp 数组其实就顺手把这件事做了。

24
6
8
3
12
7
9
7

0

六个物品体积 8、3、12、7、9、7。选 8 + 9 + 7 = 24，正好把箱子装满，所以剩余 0。

完整代码

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

int v[35];
int dp[20005];           // dp[j]：容量为 j 时能装进去的最大体积

int main(){
    int V, n;
    cin >> V >> n;
    for(int i = 1; i <= n; i++)
        cin >> v[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]] + v[i]);     // 价值 = 体积

    cout << V - dp[V] << endl;                           // 剩余空间 = 容量 - 装进去的
    return 0;
}

易错点

• 输出写成 dp[V]：题目问的是剩余空间，答案是 V - dp[V]，别把最大装入体积直接交上去。
• 数组按 n 开：值域是容量 V（20000），int dp[35] 会越界。这题要开 dp[20005]。
• 用 2^n 枚举硬搜：n = 30 时是 10 亿种取法，必超时，要老老实实用 DP。
• 物品体积可能比 V 还大，此时 j >= v[i] 直接不成立，自动跳过，不用特判。

题意：妈妈给 N 元钱买 m 件物品，第 j 件价格 v_j、重要度 p_j。在不超支的前提下，让 「价格 × 重要度」的总和最大，输出这个最大值。

思路

标准 0/1 背包，一一对应：

也就是说「价值」不是直接给的，而是算出来的：v * p。这是很多背包题的常见花样—— 先想清楚「谁是重量、谁是价值」，题目就变成模板了。

1000 5
800 2
400 5
300 5
400 3
200 2

3900

1000 元的最优买法：400（重要度 5）+ 300（重要度 5）+ 200（重要度 2），共 900 元， 价值 = 400×5 + 300×5 + 200×2 = 2000 + 1500 + 400 = 3900。

完整代码

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

int dp[30005];           // dp[j]：花 j 元钱能得到的最大「价格 x 重要度」总和

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int v, p;
        cin >> v >> p;
        for(int j = n; j >= v; j--)                      // ★ 倒序，物品只能买一次
            dp[j] = max(dp[j], dp[j - v] + v * p);       // 价值 = 价格 x 重要度
    }

    cout << dp[n] << endl;
    return 0;
}

易错点

• 数组按 m 开（dp[30]）：本题值域是钱数 n（最大 3 万），必须开 30005 以上。
• 把价值写成 p 而不是 v × p：题目要最大化的就是「价格 × 重要度」的总和。
• 输入顺序搞反：第一行是 n m（钱数、物品数），之后每行是 v p（价格、重要度）。
• 内层还是倒序。这题每件物品只有一件，属于 0/1 背包。

题意：uim 身上有 M 元钱，餐馆有 N 种菜，第 i 种卖 a_i 元，每种菜只有一份。 小 A 必须刚好把 M 元花完，问一共有多少种点菜方法。

思路

把昨天的「转移方程」从"求最值"换成"数方案"：

为什么转移是加法？因为「刚好花 j 元的方案」= 「不点第 i 种菜的方案」+「点了第 i 种菜的方案」， 两类方案互不重叠、合起来就是全部，所以直接相加，不需要取 max。

为什么 dp[0] = 1？因为"花 0 元"只有一种做法：什么都不点。这是所有方案的起点，设成 0 的话答案会全变 0。

内层仍然要倒序——每种菜只有一份，不能重复点。

4 4
1 1 2 2

3

菜品价格是 1、1、2、2（两种 1 元菜、两种 2 元菜）。刚好花 4 元的三种点法：
· 两份 2 元菜（第 3 + 第 4 种）　· 两份 1 元菜 + 第 3 种（1+1+2）　· 两份 1 元菜 + 第 4 种（1+1+2）
最后两种看起来一样，但点的是不同的菜，所以算两种方案。

完整代码

#include <iostream>
using namespace std;

int a[105];
int dp[10005];           // dp[j]：刚好花掉 j 元的点菜方案数

int main(){
    int N, M;
    cin >> N >> M;
    for(int i = 1; i <= N; i++)
        cin >> a[i];

    dp[0] = 1;                                       // ★ 花 0 元 = 什么都不点，算 1 种方案
    for(int i = 1; i <= N; i++)
        for(int j = M; j >= a[i]; j--)               // ★ 倒序，每道菜只点一次
            dp[j] += dp[j - a[i]];                   // 计数用加法

    cout << dp[M] << endl;
    return 0;
}

易错点

• 忘了 dp[0] = 1：这是本题第一大坑。设成 0 的话所有答案都是 0，样例就会输出 0。
• 转移写成 max：本题是数方案，要用 +=。看到"有多少种"就该条件反射地想加法。
• 内层写成正序：那每道菜就能重复点，方案数会暴涨。
• 数组按 N 开：值域是钱数 M（最大 10000），要开 10005。
• 同价菜去重：价格相同的菜是不同的菜，不能合并，否则方案数会少算。
• 用 long long 反而要小心：题目保证答案在 int 范围内，用 int 就好；如果用 long long 也完全没问题。