第一类背包问题#

在动态规划中，常见的问题形态大致可以划分为两类：一类是 子序列类型问题 ，另一类是 子数组类型问题 。二者的核心差异在于选取结构的不同。子数组问题强调的是 连续性约束 ，所选择的元素必须在原序列中连续出现，其状态往往围绕区间端点展开；而子序列问题则强调的是 选择与不选择的组合结构 ，元素之间不要求连续，只需满足给定约束条件即可。

从这一角度出发可以看到，背包问题本质上属于子序列类型问题 。在背包模型中，我们面对的是若干独立的物品，每件物品要么被选取，要么不被选取。最终得到的解，实质上就是所有物品集合的一个子集，或者更抽象地说，是原物品序列的一个子序列。问题的关键并不在于物品的相对位置关系，而在于每件物品是否被纳入解集中，以及这些选择在容量约束下是否可行。

从更抽象的层面看，背包问题可以理解为在 “物品维度” 上进行决策，在 “容量维度” 上进行约束控制。决策的本质是对子序列的构造，而容量只是一个全局约束变量。这种结构决定了背包问题天然适合采用逐物品推进的动态规划框架，并体现出典型的子序列型 DP 的特征。

完全背包问题#

对于完全背包而言，由于同一种物品可以被选择任意多次，其状态转移在形式上与 01 背包有所不同，但从问题结构的角度分析，它仍然属于典型的子序列类型问题。

在 01 背包中，每种物品至多出现一次，因此构造的是一个 不含重复元素的子序列 ；而在完全背包中，每种物品可以被重复选取，本质上是在构造一个 允许重复元素的子序列 。换言之，问题依然是在所有物品构成的序列上进行选择，只是允许对某个位置进行多次取用。

在状态设计上，仍定义 $dp[i][j]$ 表示在前 $i$ 种物品中，容量不超过 $j$ 时的最大价值。此时转移方程为：

dp[i][j] = \max \big( dp[i-1][j], \, dp[i][j - v_i] + w_i \big)

与 01 背包的区别在于，第二项使用的是 $dp[i][\cdot]$ 而非 $dp[i-1][\cdot]$ 。这意味着在处理第 $i$ 种物品时，可以在当前层继续使用该物品，从而实现 “无限次选取” 的效果。

多重背包问题#

多重背包处于 01 背包与完全背包之间，是对两者在选取次数约束上的折中形式。相较于 01 背包中 “每种物品至多选一次” 的严格限制，以及完全背包中 “每种物品可以无限选取” 的放宽条件，多重背包为每种物品设定了一个 有限的可选次数上界 。因此在建模与转移过程中，既不能简单地按一次性决策处理，也不能直接允许无限叠加，而必须显式刻画并控制选取次数的范围。

设第 $i$ 种物品体积为 $v_i$ ，价值为 $w_i$ ，最多可选 $s_i$ 次。仍定义二维状态 $dp[i][j]$ 表示在前 $i$ 种物品中，容量不超过 $j$ 时的最大价值。此时转移方程为：

dp[i][j] = \max_{0 \leq k \leq s_i} \big( dp[i-1][j - k v_i] + k w_i \big)

这个转移方程清晰地刻画了多重背包的结构：在子序列型 DP 的基础上，进一步枚举选取的次数。可以看到，当 $s_i = 1$ 时退化为 01 背包；当 $s_i \to \infty$ 时转化为完全背包。因此，多重背包是对前两类问题的自然推广。

然而，若直接对 $k$ 进行枚举，时间复杂度将达到 $O(n V s_i)$ ，在 $s_i$ 较大时难以接受。为了优化这一枚举过程，可以从转移结构入手进行重组。将容量按模 $v_i$ 的余数进行分组：

j \equiv r \pmod{v_i}

在同一余数组内，容量可以表示为：

j = r + t v_i

在该表示下，原转移式可重新整理为关于 $t$ 的滑动窗口形式，从而将问题转化为在一个线性序列上求带长度限制的最大值问题。整理后可以发现，其本质正是一个 滑动窗口最大值问题 。因此，可以使用单调队列维护窗口内的最优候选值，在每个容量位置实现 $O(1)$ 转移，从而将整体复杂度优化到 $O(nV)$ 。

多重背包单调队列优化的详细讲解可以看下面这个视频

多重背包更加常用的优化方法是二进制分组优化（或称二进制拆分）。其核心思想在于对 “选取次数上界” 进行结构化重组，将原本需要显式处理的次数限制转化为若干个更简单的决策单位，从而避免在状态转移中直接枚举选取次数。这种方法并不改变问题本质，而是通过对物品结构的等价变换，使问题重新回归到更成熟、实现更稳定的动态规划框架中，因此在实际应用中往往更加常见且易于实现。

完全平方数构造#

题目链接

题目要点解析#

构造目标正整数#

题目链接

题目要点解析#

二进制与字符串#

题目链接

Problem Statement#

给定一个字符串数组 strs ，其中每个字符串只包含 '0' 和 '1' 。同时给定两个整数 m 和 n 。

要求从 strs 中选出最多 多少个字符串 ，使得选出的字符串中 '0' 的总数不超过 m ，'1' 的总数不超过 n 。每个字符串最多只能使用一次。

Constraints#

$1 \leq strs.length \leq 600$
$1 \leq strs[i].length \leq 100$
$strs[i]$ 仅包含 '0' 和 '1'
$1 \leq m, n \leq 100$

Input#

输入包含两行：

第一行包含三个整数 $N$ 、 $m$ 和 $n$ 。
第二行包含 $N$ 个只包含 '0' 和 '1' 的字符串。

$N \quad m \quad n$

$strs_1 \quad strs_2 \quad \ldots \quad strs_N$

Output#

输出一个整数，表示在满足 '0' 数量不超过 $m$ 且 '1' 数量不超过 $n$ 的前提下，最多能选出的字符串数量。

Sample Input 1#

5 5 3
10 0001 111001 1 0

Sample Output 1#

Sample Input 2#

3 1 1
10 0 1

Sample Output 2#

题目要点解析#

罪犯的盈利计划#

题目链接

Problem Statement#

给定一个整数 n 表示成员总数，以及两个整数数组 group 和 profit 。数组中第 $i$ 个元素表示第 $i$ 种犯罪所需要的成员数和能带来的利润。若一个成员参与了一种犯罪，则该成员不能再参与其它犯罪。

我们称一个犯罪计划为 盈利计划 ，当且仅当该计划中涉及的犯罪总利润不小于 minProfit ，并且参与犯罪的成员总数不超过 n 。请统计 盈利计划的总数 。由于结果可能很大，请返回答案对 $10^9 + 7$ 取模的值。

Constraints#

$1 \leq n \leq 100$
$0 \leq minProfit \leq 100$
$1 \leq group.length \leq 100$
$1 \leq group[i] \leq 100$
$profit.length == group.length$
$0 \leq profit[i] \leq 100$

Input#

输入包含三行：

第一行包含三个整数 $N$ 、 $minProfit$ 和 $n$ 。
第二行包含 $N$ 个整数，表示数组 $group$ 中每种犯罪所需的成员数。
第三行包含 $N$ 个整数，表示数组 $profit$ 中每种犯罪能带来的利润。

$N \quad n \quad minProfit$

$group_1 \quad group_2 \quad \ldots \quad group_N$

$profit_1 \quad profit_2 \quad \ldots \quad profit_N$

Output#

输出一个整数，表示所有满足条件的盈利计划的数量，对 $10^9 + 7$ 取模后的结果。

Sample Input 1#

2 5 3
2 2
2 3

Sample Output 1#

Sample Input 2#

3 10 5
2 3 5
6 7 8

Sample Output 2#

题目要点解析#

买干草最小花销#

题目链接

Problem Statement#

约翰的干草库存已经告罄，他打算为奶牛们采购干草。现在已知有 $N$ 个干草公司，编号从 $1$ 到 $N$ 。第 $i$ 家公司卖的干草包重量为 $P_i$ 磅，需要开销 $C_i$ 美元，并且每家公司都有 充足货源 ，可以卖出 无限多包干草 。

约翰希望至少采购到 $H$ 磅干草，请帮助他找到满足这一需求的 最低总开销 。也就是说，在购买总重量达到或超过 $H$ 的前提下，求最小的花费总和。

Constraints#

$1 \leq N \leq 100$
$1 \leq H \leq 50000$
$1 \leq P_i \leq 5000$
$1 \leq C_i \leq 5000$

Input#

输入包含多行：

第一行包含两个整数 $N$ 和 $H$ ，分别表示干草公司数量和至少需要采购的干草磅数。
接下来 $N$ 行，每行包含两个整数 $P_i$ 和 $C_i$ ，分别表示第 $i$ 家公司的干草包重量和价格。

$N \quad H$

$P_1 \quad C_1$

$\ldots$

$P_N \quad C_N$

Output#

输出一个整数，表示采购到至少 $H$ 磅干草所需的最少花费。

Sample Input#

2 15
3 2
5 3

Sample Output#

题目要点解析#

“至少、恰好、不超过” 三种尝试方法，分析它们之间的优劣

夏季游戏大特惠#

题目链接

Problem Statement#

某公司游戏平台的夏季特惠开始了，你决定入手一些游戏。现在你一共有一个预算 X 元，平台上有 n 个游戏，每个游戏都有原价和现价，并且购买该游戏可以获得一定的快乐值。

对于编号为 i 的游戏，原价为 a_i 元，现价只要 b_i 元，那么购买该游戏能优惠 a_i - b_i 元，并带来快乐值 w_i 。由于优惠的存在，你可能会出现 “冲动消费” 使得总支出超过预算，只要你的 总优惠金额不小于超过预算的金额 ，心理上就不会觉得吃亏。

你的目标是在这种 “心理上不吃亏” 的前提下，选择一些游戏使得 总快乐值最大 。每个游戏最多只能购买一次。

Constraints#

$1 \leq n \leq 500$
$1 \leq a_i, b_i \leq 10^5$
$0 \leq w_i \leq 10^5$
总预算 $X$ 是整数

Input#

输入包含四行：

第一行包含两个整数 $n$ 和 $X$ ，分别表示游戏数量和预算。
第二行包含 $n$ 个整数，分别表示每个游戏的原价数组 $a$ 。
第三行包含 $n$ 个整数，分别表示每个游戏的现价数组 $b$ 。
第四行包含 $n$ 个整数，分别表示每个游戏的快乐值数组 $w$ 。

$n \quad X$

$a_1 \quad a_2 \quad \ldots \quad a_n$

$b_1 \quad b_2 \quad \ldots \quad b_n$

$w_1 \quad w_2 \quad \ldots \quad w_n$

Output#

输出一个整数，表示在满足总优惠金额不小于超过预算金额的前提下，你能获得的最大快乐值。

Sample Input 1#

Sample Output 1#

Sample Input 2#

Sample Output 2#

题目要点解析#

构造目标和问题#

题目链接

Problem Statement#

给定一个整数数组 nums 和一个整数 target 。你可以对数组中的每个元素选择 加号（+）或减号（−） ，从而构造一个表达式。例如：对于数组 [1, 1, 1, 1, 1] ，可以有如下表达式：

-1 + 1 + 1 + 1 + 1 = 3

请找出并返回可以使最终表达式等于 target 的 所有不同表达式的方案数 。

Constraints#

$1 \leq nums.length \leq 20$
$0 \leq nums[i] \leq 1000$
$-1000 \leq target \leq 1000$

Input#

输入包含两行：

第一行包含两个个整数 $N$ 和 $target$ ， $N$ 表示数组 $nums$ 的长度， $target$ 表示目标和。
第二行包含 $N$ 个整数，表示数组 $nums$ 的各个元素。

$N \quad target$

$nums_1 \quad nums_2 \quad \ldots \quad nums_N$

Output#

输出一个整数，表示所有能使表达式结果等于 $target$ 的不同方案数。

Sample Input 1#

5 3
1 1 1 1 1

Sample Output 1#

Sample Input 2#

1 1
1

Sample Output 2#

题目要点解析#

最后的石头重量#

题目链接

Problem Statement#

有一堆石头，每块石头的重量都是正整数。每一回合，从中选出 两块石头 ，然后将它们一起碰撞：

设这两块石头的重量分别为 x 和 y ，且 x <= y ；
碰撞后，如果 x == y ，则两块石头都会 完全粉碎 丢弃；
如果 x != y ，则那块较轻的石头 x 会完全粉碎，而较重的那块石头会剩下重量为 y - x 的碎石重新放回石头堆中。

最终最多只会剩下一块石头。请返回 剩下那块石头的最小可能重量（如果没有剩下则为 0 ）。

Constraints#

$1 \leq stones.length \leq 30$
$1 \leq stones[i] \leq 100$
石头重量都是正整数

Input#

输入包含两行：

第一行包含一个整数 $N$ ，表示石头数量。
第二行包含 $N$ 个整数，表示数组 $stones$ 中每块石头的重量。

$N$

$stones_1 \quad stones_2 \quad \ldots \quad stones_N$

Output#

输出一个整数，表示最后剩下的石头的最小可能重量（若没有石头剩下则输出 0 ）。

Sample Input 1#

6
2 7 4 1 8 1

Sample Output 1#

Sample Input 2#

5
31 26 33 21 40

Sample Output 2#

题目要点解析#

第二类背包问题#

分组背包是一类具有组内互斥结构的特殊背包问题，本质上可以理解为一种 按组进行决策的背包模型 。与普通背包中 “每件物品彼此独立” 不同，分组背包会先将所有候选物品划分为若干组。在同一组内，各个选项之间是 互斥关系 ，而不同组之间则可以同时选择，但所有选择共同受到一个 统一的容量约束 。

在状态设计上，仍可定义二维状态 $dp[i][j]$ 表示在前 $i$ 组中进行选择且容量不超过 $j$ 时所能获得的最大价值。设第 $i$ 组共有若干个物品，第 $k$ 个物品的体积为 $v_{i,k}$ ，价值为 $w_{i,k}$ 。则转移方程为：

dp[i][j] = \max \Big( dp[i-1][j], \, \max_k \{ dp[i-1][j - v_{i,k}] + w_{i,k} \} \Big)

其中第一项表示 “第 $i$ 组不选任何物品” ，第二项表示 “第 $i$ 组选择某一个物品” 。可以看到，状态始终从 $i-1$ 组转移而来，正是为了保证同一组内不会选取多个物品，从而满足组内互斥的约束。

除了普通背包与分组背包之外，还有一类称为 依赖背包问题 的重要模型。所谓的依赖背包，是指物品之间存在 选择前提关系 。不同于普通背包中各物品的彼此独立，在依赖背包中，某些物品只有在其前置物品被选取的前提下才能被选择。这类关系通常可以抽象为一棵有根树结构：若选择某个节点，则必须同时选择其所有祖先节点；若父节点未被选取，则其子节点必然不可选。换言之，依赖背包的本质在于引入了一种 自上而下的结构性约束 。

依赖条件打破了普通 01 背包中 物品独立决策 的基本假设，使得简单的逐物品转移不再适用。某一物品是否可以参与状态更新，不仅取决于当前剩余容量，还取决于其父节点是否已经被纳入当前方案。因此，问题的核心不再只是容量分配，而是 如何在满足结构约束的前提下完成合法选择 。

从理论角度看，这类问题也可以借助分组思想进行刻画。若将依赖关系组织为一棵依赖树，则可以枚举该树中所有满足依赖约束的合法选取子结构，并将每一种合法结构视为一个组内候选项，从而转化为分组背包模型。然而，这种方法本质上是在对整棵依赖树进行 状态展开 ，其合法组合数量通常会随着树规模迅速增长，时间复杂度难以控制。因此，这种转化方式仅在 依赖规模极小 的情况下才具有可行性。

具体的实现过程可以看下面这个视频

当依赖树规模较大时，更为自然且高效的处理方式是直接在树结构上进行动态规划，即采用树形动态规划的方法。通过在每个节点处维护 “在其子树内选取若干体积时的最优价值” ，并自底向上逐步合并子树状态，可以在不显式枚举所有合法组合的前提下完成整体决策。

二进制分组优化#

在多重背包问题中，更为常见且实用的优化方式是 二进制分组优化 。其核心思想是：将 “某种物品最多可选 $s_i$ 次” 的数量限制，通过二进制拆分转化为若干个 “至多选一次” 的新物品，从而把多重背包等价地转化为一个 01 背包问题。具体来说，对于某种物品，若其最多可选 $s_i$ 次，可以将 $s_i$ 按二进制形式拆分为若干块，例如：

s_i = 1 + 2 + 4 + \cdots + 2^k + r

据此，可以将原物品拆分为若干个体积与价值按倍数放大的新物品：

体积为 $1 \cdot v_i$ ，价值为 $1 \cdot w_i$
体积为 $2 \cdot v_i$ ，价值为 $2 \cdot w_i$
体积为 $4 \cdot v_i$ ，价值为 $4 \cdot w_i$
$\ldots$
体积为 $r \cdot v_i$ ，价值为 $r \cdot w_i$

每个拆分后的物品都只能选取一次。由于任意一个不超过 $s_i$ 的整数，都可以由这些二进制块唯一表示，因此这种拆分在可行性与最优性上与原问题完全等价。

从更本质的角度看，我们之所以这样拆分，是为了用 二进制编码覆盖从 $0$ 到 $s_i$ 的所有取值 。任何一个选取次数 $k \le s_i$ ，都可以表示为若干个二进制位之和，而二进制表示的关键特性在于：各个二进制位彼此独立，每一位只有 “取或不取” 两种状态。在二进制视角下，一个次数 $k$ 的形成，其实只是若干个二进制块被选中的结果。因此，我们无需在外层枚举完整的二进制数，而是把每一位是否为 $1$ 的决策，直接融入到背包的状态转移之中。动态规划在进行 $01$ 决策时，会自动完成这些块的组合，从而自然枚举出所有合法次数。

也正因为 二进制位之间相互独立 ，而背包问题本身又具有 “选或不选” 的结构，两者在形式上天然对应，才能通过这种结构重组，把原本对次数的显式枚举，转化为若干次简单的 $01$ 决策。经过拆分后，原问题转化为一个规模略有扩展的 $01$ 背包问题，物品总数由 $n$ 增加到约 $n \log s_i$ 的数量级。这样，原本需要显式枚举次数、时间复杂度为 $O(n V s_i)$ 的做法，就可以优化为 $O\left(n V \log s_i\right)$ 。相比单调队列优化，二进制分组的思路更加直观，代码结构也更贴近标准 01 背包模板，因此在竞赛与实际应用中更加常见。

硬币最大面值和#

题目链接

Problem Statement#

给你一个 piles 数组，其中 piles[i] 是一个整数数组，表示第 i 堆硬币从上到下排列的硬币价值。

每次行动，你可以从任意一堆中 移除最上面的硬币 并拾取它的价值。你总共可以执行 最多 k 次操作 。

请返回在最优策略下你能得到的 最大硬币总价值 。

Constraints#

$1 \leq piles.length \leq 1000$
$1 \leq piles[i].length \leq 2000$
$1 \leq k \leq 2000$
每个硬币的价值都是非负整数

Input#

输入包含多行：

第一行包含两个整数 $N$ 和 $k$ ，分别表示堆数和最多可取的硬币数量。
接下来 $N$ 行，每行以一个整数 $len_i$ 开头表示硬币的数量，后接 $len_i$ 个整数表示这堆硬币的价值。

$N \quad k$

$len_1 \quad piles[1][0] \quad piles[1][1] \quad \ldots \quad piles[1][len_1-1]$

$len_2 \quad piles[2][0] \quad piles[2][1] \quad \ldots \quad piles[2][len_2-1]$

$\ldots$

$len_N \quad piles[N][0] \quad piles[N][1] \quad \ldots \quad piles[N][len_N-1]$

Output#

输出一个整数，表示在最多取出 k 个硬币的前提下，你能获得的最大总价值。

Sample Input 1#

2 2
3 1 100 3
3 7 8 9

Sample Output 1#

Sample Input 2#

7 7
1 100
1 100
1 100
1 100
1 100
1 100
7 1 1 1 1 1 1 700

Sample Output 2#

题目要点解析#

樱花的美学价值#

题目链接

Problem Statement#

爱与愁大神后院里种了 $n$ 棵樱花树，每棵树都有一个美学值 $C_i$ 。每天上学前，他都会到后院赏花。每棵樱花树都有一个看花所需的时间 $T_i$ ，看一次可以获得 $C_i$ 的美学值。对于第 $i$ 棵树：

如果 $P_i = 0$ ，表示可以 无限次 观看该树；
如果 $P_i > 0$ ，表示最多可以观看该树 $P_i$ 次。

爱与愁大神离开去上学前的时间为 $T_s$ ，上学开始的时间为 $T_e$ 。如果他在赏花过程中花费的总时间不超过 $T_e - T_s$ 分钟，就可以按时或提前上学。请你帮助他选择应观看的樱花树组合，使得 总美学值最大 。

Constraints#

$1 \leq n \leq 10000$
$T_e - T_s \leq 1000$
$1 \leq T_i \leq 100$
$0 \leq C_i \leq 200$
$0 \leq P_i \leq 100$

Input#

输入包含多行：

第一行包含两个时间点 $T_s$ 和 $T_e$ 以及整数 $n$ ，其中时间格式为 hh:mm ，保证在同一天内且 $T_e \ge T_s$ 。
接下来 $n$ 行，每行包含三个整数 $T_i$ 、 $C_i$ 和 $P_i$ ，分别表示樱花树的赏花时间、美学值以及最多观看次数。

$T_s \quad T_e \quad n$

$T_1 \quad C_1 \quad P_1$

$\ldots$

$T_n \quad C_n \quad P_n$

Output#

输出一个整数，表示在不超过允许时间的情况下所能获得的最大美学值。

Sample Input#

6:50 7:00 3
2 1 0
3 3 1
4 5 4

Sample Output#

题目要点解析#

参考文献列表#

【崔添翼】背包动态规划九讲