动态规划（四）算法设计与分析 国科大

0-1背包问题

• 输入：给定物品集合，每个物品 i 对应重量和价值；同时给定背包的总重量限制 W。
• 输出：选择物品的一个子集，满足 “子集总重量不超过 W” 的约束，同时最大化子集的总价值。

这是一个二元决策问题，简单来说，需要在一个有限容量的背包中放入尽可能高价值的物品，对于每个可选物品，只有放入\不放入两种状态。

相较于分数背包问题（即非二元决策，如某个物品可以选择放入一半），0-1背包问题无法通过贪心的思想来解决，比如下例：

背包的重量限制为 15kg，待选物品的属性（价值、重量、单位价值）如下：

如果按照贪心的思路，即选择单位价值更高的物品，步骤如下：

1. 优先选单位价值最高的物品 1（9kg，10$），背包剩余重量：15-9=6kg；
2. 物品 2（12kg）超过剩余重量，不选；
3. 选次高单位价值的物品 3（2kg，1$），背包剩余重量：6-2=4kg；
4. 物品 4（7kg）、物品 5（5kg）均超过剩余重量，不选；

最终选择 “物品 1 + 物品 3”，总价值 11$，总重量 11kg。但若选择 “物品 1 + 物品 5”，总重量为9+5=14kg（不超过限制），总价值为10+2=12美元，明显高于贪心方法得到的 11 美元。这一缺陷的根源是：0-1 背包的 “物品不可拆分” 约束，使得贪心算法无法灵活调整物品组合，因此必须通过动态规划等方法，枚举所有合法组合的价值，才能得到真正的最优解。

寻找最优子结构

我们可以将 0-1 背包的求解过程转化为每个物品是否选择的多阶段决策：每个决策阶段对应一个物品（例如第i阶段决定 “是否选择物品i”），所有阶段的决策组合（选 / 不选的集合），对应最终的物品子集。

以 “是否选择最后一个物品n” 作为首个决策（假设物品按顺序排列，从后往前分析），该决策包含两种互斥选项，每种选项对应一个子问题：

• 选项 1：选择物品n约束变为 “背包剩余重量为”，需从物品中选择子集，最大化总价值（此时总价值需加上物品n的价值）。
• 选项 2：不选择物品n约束保持 “背包重量限制为W”，需从物品中选择子集，最大化总价值。

因此，原问题（物品、重量限制）的最优解，可通过 “是否选择物品n” 的决策，转化为两个子问题的最优解的最大值：

下面以物品信息：；；；背包重量限制展示一下算法过程：

• 目标：设置 “无物品（i=0）” 时的所有子问题解。
• 逻辑：当没有物品可选时，任何重量限制下的总价值都是 0，因此OPT[0, w] = 0（w从 0 到 6）。

• 目标：计算 “前 1 个物品、重量限制的最大价值。
• 逻辑：第 1 个物品重量，仅当时可选择：取最大值 2，填充OPT[1,2]为 2。

• 目标：计算 “前 2 个物品、重量限制的最大价值。
• 逻辑：第 2 个物品重量，需基于前 1 个物品的解计算：取最大值 4，填充OPT[2,4]为 4。

• 目标：计算 “前 3 个物品、重量限制的最大价值。
• 逻辑：第 3 个物品重量，需基于前 2 个物品的解计算：取最大值 3，填充OPT[3,3]为 3。

最终可通过OPT[3,6]得到原问题的最优价值。

算法总结如下

用二维数组OPT[i, w]简化表示子问题OPT({1,2,...,i}, w)，即前i个物品在重量限制w下的最大价值。之后按状态转移方程来进行即可。

回溯

步骤 1：回溯原问题 OPT[3,6]（前 3 个物品、重量 6）

• 计算逻辑：OPT[3,6] = max(OPT[2,6]=4, OPT[2, 6-3] + v_3=OPT[2,3]+3=2+3=5)，最终值为 5。
• 决策：因OPT[3,6] = OPT[2,3] + v_3，说明选择了物品 3，后续回溯到OPT[2,3]（前 2 个物品、重量6-3=3）。

步骤 2：回溯子问题 OPT[2,3]（前 2 个物品、重量 3）

• 计算逻辑：OPT[2,3] = max(OPT[1,3]=2, OPT[1, 3-2] + v_2=OPT[1,1]+2=0+2=2)，最终值为 2。
• 决策：因OPT[2,3] = OPT[1,1] + v_2，说明选择了物品 2，后续回溯到OPT[1,1]（前 1 个物品、重量3-2=1）。

步骤 3：回溯子问题 OPT[1,1]（前 1 个物品、重量 1）

• 因物品 1 的重量w_1=2 > 1，无法选择，故OPT[1,1]=0，说明未选择物品 1。

洛谷上对应的题目

对应代码如下：

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int t, m; cin >> t >> m; vector<int> time(m+1), val(m+1); // 草药1~m for (int i=1; i<=m; i++) { cin >> time[i] >> val[i]; } // 定义opt[前i个物品][时间j]，初始化为0 vector<vector<int>> opt(m+1, vector<int>(t+1, 0)); for (int i=1; i<=m; i++) { // 处理前i个物品 for (int j=1; j<=t; j++) { // 处理时间j if (j < time[i]) { opt[i][j] = opt[i-1][j]; // 装不下，不选 } else { // 选/不选的最大值 opt[i][j] = max(opt[i-1][j], opt[i-1][j-time[i]] + val[i]); } } } cout << opt[m][t]; // 前m个物品、时间t的最大价值 return 0; }