切杆问题和01背包问题的比较（动态规划）（C++）
一、问题介绍
切杆问题（Rod Cutting Problem）
问题描述
你有一根长度为 的原木，和一个长度 的价格表 。你的目标是将这根原木切割成若干段，使得切割后的价格总和最大。可以多次选择相同的分段长度，切割的长度总和必须等于 。
• 输入：
• 原木的长度N 。
• 价格表P_L ，表示每段长度L 的价格。
• 输出：
• 长度为 的原木的最大收益。
例子
输入：
• N = 8
• 价格表 P = [1, 5, 8, 9, 10, 17, 17, 20, 23, 28]
• 价格表
输出：
• 最优收益：22 （切割成2+6 ，价格为 5+17=22）
动态规划的核心思路
1. 定义状态：
dp[i]：长度为 i 的原木可以获得的最大收益。
2. 状态转移方程：
对于长度 ，我们可以尝试切割任意一段长度 ：
3. 初始条件：
dp[0] = 0（长度为 0 的原木收益为 0）。
4. 复杂度：
时间复杂度为 O(N^2) ，外层循环遍历原木长度 N ，内层循环尝试所有可能的切割长度。
01背包问题（0/1 Knapsack Problem）
问题描述
你有 个物品，每个物品有一个重量 和价值 。现在有一个容量为 的背包，问如何选择物品使得总价值最大，每个物品只能选择 0 次或 1 次（不可拆分）。
• 输入：
• n：物品个数。
•w[i]：第 个物品的重量。
•v[i]：第 个物品的价值。
•W：背包的总容量。
• 输出：
• 背包能装入的物品的最大价值。
例子
输入：
• w = [2, 3, 4, 5]
• v = [3, 4, 5, 6]
• 背包容量 W = 5
输出：
最大价值：7（选择物品 1 和物品 2，重量为 2+3=5，价值为 3+4=7）
动态规划的核心思路
1. 定义状态：
dp[i][w]：前 i 个物品在容量为 w 的背包中可以获得的最大价值。
2. 状态转移方程：
dp[i][w] =
\\begin{cases}
dp[i-1][w] & \\text{如果不选第 } i \\text{ 个物品} \\\\
\\max(dp[i-1][w], dp[i-1][w-w[i]] + v[i]) & \\text{如果选第 } i \\text{ 个物品且 } w[i] \\leq w
\\end{cases}
3. 初始条件：
• dp[0][w] = 0（没有物品时，最大价值为 0）。
• dp[i][0] = 0（背包容量为 0 时，最大价值为 0）。
4. 复杂度：
时间复杂度为O(n \\cdot W) ，外层遍历物品，内层遍历背包容量。
二、C++ 代码实现
切杆问题的 C++ 实现
#include #include #include // for max functionusing namespace std;// 切杆问题的动态规划实现int rodCutting(vector& prices, int n) { vector dp(n + 1, 0); // dp[i] 表示长度为 i 的最大收益 // 遍历原木的总长度 for (int i = 1; i <= n; ++i) { // 尝试切割每一种可能的长度 for (int j = 1; j <= prices.size(); ++j) { if (j <= i) { // 如果当前切割长度 j 可以切割 dp[i] = max(dp[i], prices[j - 1] + dp[i - j]); // 状态转移 } } } return dp[n]; // 返回长度为 n 的最大收益}int main() { vector prices = {1, 5, 8, 9, 10, 17, 17, 20, 23, 28}; // 每段长度的价格 int n = 8; // 原木总长度 cout << \"Maximum revenue for rod of length \" << n << \": \" << rodCutting(prices, n) << endl; return 0;}01背包问题的 C++ 实现
#include #include #include // for max functionusing namespace std;// 01背包问题的动态规划实现int knapsack(vector& weights, vector& values, int capacity) { int n = weights.size(); vector<vector> dp(n + 1, vector(capacity + 1, 0)); // dp[i][w] 表示前 i 个物品在容量为 w 时的最大价值 // 遍历所有物品 for (int i = 1; i <= n; ++i) { for (int w = 1; w <= capacity; ++w) { if (weights[i - 1] <= w) { // 当前物品可以放入背包 dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]); // 状态转移 } else { dp[i][w] = dp[i - 1][w]; // 如果物品无法放入背包 } } } return dp[n][capacity]; // 返回背包容量为 capacity 的最大价值}int main() { vector weights = {2, 3, 4, 5}; // 每个物品的重量 vector values = {3, 4, 5, 6}; // 每个物品的价值 int capacity = 5; // 背包的总容量 cout << \"Maximum value in knapsack of capacity \" << capacity << \": \" << knapsack(weights, values, capacity) << endl; return 0;}三、两者的相同点与区别
相同点
1. 问题本质：
• 两者都在尝试最大化某种收益（切杆收益或背包价值）。
2. 动态规划思想：
• 都基于递归问题分解。
• 都利用 DP 数组存储中间状态。
3. 时间复杂度：
• 两者都需要两层循环，复杂度为 O(N^2)（切杆）或 O(n \\cdot W)（背包）。
区别
比较点 切杆问题 01 背包问题
是否可重复使用 可以多次使用同一段长度 每个物品只能选择一次
状态转移方程
限制条件 切割总长度需等于 背包重量不能超过
输出示例
运行以上代码：
切杆问题：
Maximum revenue for rod of length 8: 22
01 背包问题：
Maximum value in knapsack of capacity 5: 7
