A背包 DP

01 背包

取或不取·一维逆推·恰好装满

本课摘要

01 背包课程回答“每件物品只能取一次时，为什么容量必须逆序更新”。内容以取或不取·一维逆推·恰好装满为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。

  • 判断01 背包的适用条件与状态边界
  • 围绕“取或不取·一维逆推·恰好装满”推导转移与计算顺序
  • 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节

正在整理目录…

从「整件取舍」说起

先看一个具体场景：有 3 件物品，一个容量 m=8m=8 的背包。每件物品有自己的重量 ww 和价值 vv， 而且要么整件装入、要么留下，没有「装半件」这回事（这就是「01」的含义：每件取 0 次或 1 次）。目标：在不超重的前提下，让装入的总价值最大。

物品 1w=2v=3物品 2w=3v=4物品 3w=4v=5背包容量 m=8
3 件物品（重量 w、价值 v）与容量 m=8 的背包，该带走哪些？

第一反应也许是贪心：按「性价比」v/wv/w 从高到低装。这里三件的性价比是 1.5, 1.33, 1.251.5,\ 1.33,\ 1.25， 于是先装物品 1（w=2w=2），再装物品 2（w=3w=3，累计 5），想装物品 3 时 5+4=9>85+4=9>8 塞不下，贪心只拿到 3+4=73+4=7。

可最优其实是物品 2 + 物品 3：重量 3+4=7≤83+4=7\le 8，价值 4+5=94+5=9。贪心输了 2。「整件取舍」的最优，贪心按不住，因为此刻的最优选择，依赖后面还剩多少空间，是一个牵一发动全身的全局问题。

那把 nn 件物品「取 / 不取」的所有组合都枚举一遍？那是 2n2^n 种，n=100n=100 就已是天文数字。 DP 的思路，是把这 2n2^n 的爆炸，压成一张逐格填写的表。

状态与转移：取，还是不取

定状态。设 f[i][j]f[i][j] 表示：只在前 ii 件物品里挑选、且总重量不超过 jj 时，能得到的最大价值。 把「逐件考虑」当作阶段，第 ii 阶段只决断一件事，第 ii 件，取还是不取？

第 i 件 · 容量 jf[i][j] = ?不取取（需 j ≥ w）第 i 件没参与= f[i−1][j]腾出 w，补上价值 v= f[i−1][j−w] + v取较大者 = max(两者)
每一格 f[i][j] 只有两条路：不取继承上一行，取则腾出 w 再补上 v，最后取较大者。

不取第 ii 件：它没参与，前 ii 件的最优就等于前 i−1i-1 件在同容量 jj 下的最优，即 f[i−1][j]f[i-1][j]。

取第 ii 件（前提装得下 j≥wij\ge w_i）：先腾出 wiw_i 的空间给它，剩下的 j−wij-w_i 容量留给前 i−1i-1 件去最优，再加上它自己的价值 viv_i，即 f[i−1][j−wi]+vif[i-1][j-w_i]+v_i。

两条路要价值最大，取较大者，就得到转移方程：

f[i][j]=max⁡( f[i−1][j], f[i−1][j−wi]+vi )f[i][j]=\max\big(\,f[i-1][j],\ f[i-1][j-w_i]+v_i\,\big)

边界：f[0][j]=0f[0][j]=0（一件都不考虑，价值为 0）。答案：f[n][m]f[n][m]。

本质

这一步把「2n2^n 种组合」拆成了「每件物品在参与 / 不参与两种局面下的最优」，用 O(nm)O(nm) 张表格格子，装下了指数级的搜索。

跟着算一遍

用刚才的例子（物品 (w,v)=(2,3),(3,4),(4,5)(w,v)=(2,3),(3,4),(4,5)，容量 8）走几步，把方程「跑起来」：

0
初始化第 0 行。 一件物品都不考虑时，任何容量下价值都是 0：f[0][0..8]=0f[0][0..8]=0。这是整张表的地基。
1
放入物品 1（w=2,v=3w=2,v=3）。容量 j<2j<2 装不下 → 仍是 0；j≥2j\ge2 时 f[1][j]=max⁡(0, 0+3)=3f[1][j]=\max(0,\ 0+3)=3。于是第 1 行变成 0,0,3,3,3,3,3,3,30,0,3,3,3,3,3,3,3。
2
放入物品 2（w=3,v=4w=3,v=4）。看容量 5：不取 = f[1][5]=3f[1][5]=3；取 = f[1][5−3]+4=f[1][2]+4=3+4=7f[1][5-3]+4=f[1][2]+4=3+4=7。取较大 → f[2][5]=7f[2][5]=7。
3
放入物品 3（w=4,v=5w=4,v=5），看容量 8：取 = f[2][8−4]+5=f[2][4]+5=4+5=9f[2][8-4]+5=f[2][4]+5=4+5=9，大于不取的 f[2][8]=7f[2][8]=7。 于是 f[3][8]=9f[3][8]=9，正是最优解，和我们手算的「物品 2+3」吻合。
下面的演示会把整张表逐格填满，并高亮每一格的两个来源。试着改物品或容量，看表格实时重算。

看它一格一格长出来

自主设计数值
01 背包每件物品至多取一次 · 可对照二维与一维顺序
物品（直接输入重量 / 价值，最多 8 件）
1
重量 w
价值 v
2
重量 w
价值 v
3
重量 w
价值 v
背包容量（直接输入 1–60）
m
0
1
2
3
4
5
6
7
8
∅
1
2
3
0
0
0
0
0
0
0
0
0
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
当前计算 依赖来源 被选转移 已确定
f[0][j]=0f[0][j] = 0
第 0 行：一件物品都不考虑时，任何容量下最大价值都是 0（初始化）。
已暂停，第 1 步，共 29 步，1 倍速

卷成一维：滚动数组与逆推

注意转移只用到上一行 f[i−1][⋅]f[i-1][\cdot]。既然如此，何必保留所有行？用一维 f[j]f[j] 就地更新即可，空间从 O(nm)O(nm) 压到 O(m)O(m)：

f[j]=max⁡(f[j], f[j−wi]+vi)f[j]=\max\big(f[j],\ f[j-w_i]+v_i\big)

但方向必须逆推（jj 从 mm 到 wiw_i）：算 f[j]f[j] 要用「上一件」留下的 f[j−wi]f[j-w_i]，逆推时它还没被本件动过，是干净的旧值。方向反过来会怎样？这不是小瑕疵，而是会让答案彻底跑偏，下一节把它摊开看。

为什么不能正推：一件物品被反复装入

把内层循环从逆推改成正推（jj 从 wiw_i 到 mm），代码只差一个方向，结果却会错得离谱。病根就一句话：正推时，你用来更新 f[j]f[j] 的 f[j−wi]f[j-w_i]，可能在本轮已经被同一件物品改过了。

用最干净的例子看，只有一件物品 (w,v)=(2,3)(w,v)=(2,3)，容量 6：

j=0j=2j=4j=6逆推 ✓正推 ✗03330369+3+3+3
同一件物品：逆推每格都取「装它之前」的旧值，恒为 3（只装 1 件）；正推却让 f[0]→f[2]→f[4]→f[6] 链式 +3，一路滚到 9，同一件被装了 3 次。
✓
逆推（j:6→4→2j:6\to 4\to 2）：算 f[6]f[6] 用 f[4]f[4] 的旧值 0 → 3；算 f[4]f[4] 用 f[2]f[2] 旧值 0 → 3；算 f[2]f[2] 用 f[0]=0f[0]=0 → 3。每格都落在「这件还没进过」的旧值上，只加一次 → f[6]=3，装 1 件。
✗
正推（j:2→4→6j:2\to 4\to 6）：f[2]=f[0]+3=3f[2]=f[0]+3=3；到 f[4]f[4] 时 f[2]f[2] 已经含这件了，f[4]=f[2]+3=6f[4]=f[2]+3=6（2 件）；f[6]=f[4]+3=9f[6]=f[4]+3=9（3 件）。一件 w=2w=2 的物品被当成「无限件」反复塞了进去。

记死：01 逆推、完全顺推

01 背包每件至多取一次，必须逆推，让 f[j−wi]f[j-w_i] 保持「上一件」留下的干净旧值；而这个「正推会重复取」的 bug，到 完全背包 里恰好翻身成想要的特性（每种无限件）。同一段转移，循环方向决定物种。

下面把两个方向并排跑给你看，改物品的 w,vw,v 或容量：左边逆推恒等于一件的价值，右边正推随容量成倍上涨。

一件物品（可改重量 / 价值）
重量 w
2
价值 v
3
背包容量
m
6
逆推 f[6] = 3（只装 1 件） · 正推 f[6] = 9（同一件被装了 3 次！）
逆推 · 正确（每件至多一次）
0
1
2
3
4
5
6
f
0
0
0
0
0
0
0
当前计算 依赖来源 被选转移 已确定
f[j]=0f[j]=0
初始：容量 0…W 的最大价值都是 0（空背包）。
已暂停，第 1 步，共 7 步，1 倍速
正推 · 错误（同一件被重复计入）
0
1
2
3
4
5
6
f
0
0
0
0
0
0
0
当前计算 依赖来源 被选转移 已确定
f[j]=0f[j]=0
初始：容量 0…W 的最大价值都是 0（空背包）。
已暂停，第 1 步，共 7 步，1 倍速
想更直观？到 A 部分页的「装包大师」亲手挑物品，再点「看 DP 最优」，体验一次贪心为何会输给 DP。

例题

P1048采药NOIP2005 普及组普及-
题意
给定总时间 TT 与 MM 株草药，每株耗时 tit_i、价值 viv_i，每株至多采一次。求 TT 时间内最大总价值。
对应关系
「时间」= 重量 ww，「价值」= vv，「总时间 TT」= 容量 mm。标准 01 背包。
转移 · 复杂度
f[j]=max⁡(f[j],f[j−ti]+vi)f[j]=\max(f[j],f[j-t_i]+v_i)，一维逆推；时间 O(TM)O(TM)。
参考代码（一维逆推）
C++
在洛谷打开 P1048 
#include <iostream>
#include <algorithm>
using namespace std;

int t[105], v[105];
int f[1005];                 // f[j]：用时不超过 j 的最大价值

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

    for (int i = 1; i <= M; i++)        // 逐株草药
        for (int j = T; j >= t[i]; j--) // ★逆推：从大容量往小推
            f[j] = max(f[j], f[j - t[i]] + v[i]);

    cout << f[T] << endl;
    return 0;
}
P2871[USACO07DEC] Charm Bracelet SUSACO 2007普及/提高-
题意
NN 个饰品，每个重量 WiW_i、魅力 DiD_i，背包承重 MM，求最大魅力和。
为什么选它
N≤3402, M≤12880N\le 3402,\ M\le 12880，二维表 N×MN\times M 直接 MLE，逼你写一维滚动数组。是讲「为何必须一维、为何倒序」的最佳载体。
参考代码
C++
在洛谷打开 P2871 
#include <iostream>
#include <algorithm>
using namespace std;

int w[3405], d[3405];
int f[12885];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> d[i];

    for (int i = 1; i <= n; i++)        // N 大，二维会 MLE，必须一维
        for (int j = m; j >= w[i]; j--)
            f[j] = max(f[j], f[j - w[i]] + d[i]);

    cout << f[m] << endl;
    return 0;
}
P1164小 A 点菜洛谷原生普及-
题意
nn 道菜价格已知，手上恰好 mm 元，求恰好花完的点菜方案数。
关键变形
把「求最优」换成「求方案数」：转移里的 max⁡\max 换成累加 ++，初值 f[0]=1f[0]=1（花 0 元有 1 种方案）。这是从「最优 DP」跨到「计数 DP」最平滑的一题。
参考代码
C++
在洛谷打开 P1164 
#include <iostream>
using namespace std;

int a[105];
int f[10005];                // f[j]：恰好花 j 元的方案数

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

    f[0] = 1;                           // 花 0 元有 1 种方案（什么都不点）
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= a[i]; j--)
            f[j] += f[j - a[i]];        // 计数：max 换成累加

    cout << f[m] << endl;
    return 0;
}

练习

P1049[NOIP2001 普及组] 装箱问题布尔可行性：让 f[j] 表示容量 j 能否恰好装满，求最小剩余空间 = m − 最大可装。在洛谷打开
P1417烹调方案01 背包 + 邻项交换排序：先按系数 b 决定处理顺序，再做背包。在洛谷打开
P1466[USACO2.2] 集合 Subset Sums求方案数：能否把 1..n 分成两个和相等的子集，f[j] 计数。在洛谷打开

已进入 01 背包 · 背包 DP · DP大师