算法与数据结构 / 背包问题九讲 · 动态规划的思考艺术 待审核 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 件

件数上限废掉了完全背包的本层递推特权。二进制拆分把件数约束编码进约 log M 件一次性物品，退化为 01 背包求解。

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

Ⅳ · 混合背包 · dispatch 分发

混合背包：三类物品同台

同一份物品清单里三种类型混杂时，按类型分发到各自的 Pack 过程即可，不必也不该写一个统一的 Pack 函数。

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

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

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

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

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

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

 Ⅶ · 依赖背包 · 两步化归

依赖背包：附件依附主件

附件只有在选了主件时才能选。两步化归：先对每个主件的附件集做 01 背包，把「主件 + 一组附件」打包成分组背包的候选，再跑分组背包。一般情形即树形 DP。

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

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

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

把物品抽象成函数 h(v)，即分配费用 v 时能贡献的最大价值。背包问题归结为对所有 h 做一次取 max 的卷积，前七讲全是它的特例。

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

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

状态骨架不动，变的只是聚合算子与初始化语义：最大价值、最少件数、方案数与可行性四种问法在同一框架下统一。

动手体验 · 应用 demo

demo · 优惠券最优组合

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

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

它真实跑在哪里

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

原版出处