← 首页 / 背包问题九讲 · 动态规划的思考艺术 待审核 10 页

背包问题九讲 · 动态规划的思考艺术

一类被反复讲解近二十年的 dynamic programming 入门题——把若干带「费用 C」和「价值 W」的物品放入容量 V 的背包,求最大价值。九讲从最朴素的 01 背包(每件至多选一次)出发,逐步增加约束、变换问法:无限选、有上限、多类混合、双重费用、分组互斥、物品依赖……最后抽象成「物品即函数 h(v)」与「换聚合算子即换问法」两条主线。

每页都可调整容量 / 物品参数、单步执行,观察 DP 表逐格填出、读取的父节点与正在写入的格子高亮、代码逐行点亮,最后回溯出究竟选了哪几件落入背包。脉络一条线:状态 → 转移方程 → 循环方向 → 组合 / 求和 → 回溯。

基础三讲:状态、方程、循环方向

Ⅰ · 01 背包 · F[i][v] · v 逆序

01 背包：每件至多选一次

全系列的地基。状态 F[i][v] =「前 i 件、容量 v 内的最大价值」，每件物品只有「选 / 不选」两个分支取 max。单步看二维表逐格填出、回溯把选中的物品落进背包；再看一维压缩为何要 v 逆序。

 Ⅱ · 完全背包 · F[v] · v 顺序

完全背包：每种可无限次选

和 01 背包只差一个循环方向：把一维的 v 从逆序改成顺序，读到的 F[v-C] 就已经含「本物品已选过」的结果，于是允许反复选。左右并排同步单步，看同一格在两种方向下读到的源值差在哪。

 Ⅲ · 多重背包 · O(V·log M)

多重背包：每种限选 M 件

介于 01 与完全之间——每种有件数上限 M。核心技巧是二进制拆分：把 M 件拆成 1, 2, 4, … 若干个「打包件」，任意 0..M 件都能由它们的子集唯一组合而成，于是退化成 01 背包，复杂度从 O(VM) 降到 O(V·log M)。

进阶四讲:混搭、升维、分组、依赖

Ⅳ · 混合背包 · dispatch 分发

混合背包：三类物品同台

01、完全、多重三种物品一起出现，却不需要任何新算法。state 与 F[v] 的语义都不变——变的只是转移过程：主循环按物品 type 分发到 ZeroOnePack / CompletePack / MultiplePack。这正是「抽象与组合」的方法论价值。

 Ⅴ · 二维费用 · F[v][u]

二维费用：同时占两种资源

每件物品同时消耗两种费用（如重量 + 体积），容量也有两个上限 V、U。状态从 F[v] 升一维成 F[v][u]，转移方程、边界、空间压缩的全套技术原样迁移——「升维即可」，体现状态设计的可扩展性。

 Ⅵ · 分组背包 · k · v · item

分组背包：每组至多选一件

物品分成若干组，每组至多选一件。互斥既不靠加维也不靠分发，而靠三层循环的嵌套顺序：外层组 k、中层容量 v 逆序、内层组内物品 j。若将内外层写反便会同组多选——本页正确 / 错误两版并排单步，直观对比差异。

 Ⅶ · 依赖背包 · 两步化归

依赖背包：附件依附主件

物品间有依赖（附件只有在选了主件时才能选）。求解是两步化归：先对每个主件的附件集做 01 背包预处理(Stage A)，把「主件 + 一组附件」打包成分组背包里的候选，再跑分组背包(Stage B)。一般情形即树形 DP。

收束两讲:统一抽象与问法变化

Ⅷ · 泛化物品 · h ⊕ g = f

泛化物品：物品即函数 h(v)

把「物品」抽象成函数 h(v) =「分配费用 v 时能贡献的最大价值」。01 是单峰、完全是等距阶梯、多重是截断阶梯……前七讲全是它的特例。背包问题归结为对所有 h 做一种「求和」f(v) = max{h(k)+g(v−k)}，在 f(V) 读答案。

 Ⅸ · 问法变化 · max → min / sum / OR

问法变化：换聚合算子即换问法

同一组数据、同一状态骨架，可以提出「最大价值 / 最少件数 / 方案数 / 可行性」等诸多问题。关键在于：状态不变，只换聚合算子——max 换成 min / sum / OR，再配上对应的初值。一个 tab 切换四种问法，观察 F 数组随之变化。

动手体验 · 应用 demo

demo · 优惠券最优组合

优惠券最优组合 · 背包算法演示

一个独立的应用小程序：给定一组订单与若干满减券，用背包算法实时算出「如何组合最省」。把九讲的 01 / 完全 / 多重 背包落实到真实的电商凑单场景中——与系列各讲里的「优惠券」应用案例同源，这里是可直接操作的完整版。

它真实跑在哪里

资源分配 / 预算优化:有限预算下挑选投资组合、云配额下排布任务、广告预算下选择投放位——都是「容量 + 费用 + 价值」的背包骨架。 电商优惠叠加:满减券 / 折扣券 / 限领券如何组合最省?多张门槛累加占用额度、减免即价值,正是 01 / 完全 / 多重 / 分组背包(本系列的应用案例都取自这里)。 切割与装箱:钢材 / 木板下料、货物装箱(bin packing 的近亲)、虚拟机装宿主机,本质都在做带容量约束的价值最大化。 竞赛与面试:OI / ACM、LeetCode 高频题(零钱兑换、分割等和子集、目标和……)几乎都能归到九讲里的某一讲。

原版出处