一、问题引入01背包是动态规划中最经典的问题之一题目描述如下有一个容量为20的背包你有10件物品每件物品只能选一次每件物品都有对应的体积和价值请问如何选择物品才能让背包中物品的总价值最大二、问题简化与贪心算法的局限为了更清晰地理解问题我们先将背包容量简化为6物品简化为4件物品体积价值书12衣服23电视35桌子46贪心算法的尝试如果使用贪心算法优先选择单位体积价值最高的物品桌子单位体积价值为6/41.5优先选择占用体积4剩余体积2剩余体积2选择衣服占用体积2总价值为639但正确的最优解是选择书、衣服、电视总价值为23510占用体积1236刚好装满背包。这说明贪心算法无法得到最优解需要使用动态规划。三、动态规划解法1. 状态定义定义dp[i][w]表示前i件物品放入容量为w的背包中能获得的最大价值。2. 状态转移方程对于第i件物品有两种选择不选第i件物品dp[i][w] dp[i-1][w]选第i件物品dp[i][w] dp[i-1][w - wt[i]] val[i]其中wt[i]是第i件物品的体积val[i]是第i件物品的价值因此状态转移方程为dp[i][w] max(dp[i-1][w], dp[i-1][w - wt[i]] val[i])3. 空间优化我们可以将二维数组优化为一维数组因为每次计算只需要上一行的结果。优化后的状态转移方程为dp[w] max(dp[w], dp[w - wt[i]] val[i])。注意需要从背包容量从大到小遍历避免重复选择同一件物品。4. 解题过程我们以简化后的问题为例逐步计算初始化dp数组为[0, 0, 0, 0, 0, 0, 0]对应容量0到6处理第一件物品书体积1价值2容量0为0容量1-6为2dp数组变为[0, 2, 2, 2, 2, 2, 2]处理第二件物品衣服体积2价值3容量0-1不变容量2为max(2, dp[0]3)3容量3-6为max(2, dp[1]3)5dp数组变为[0, 2, 3, 5, 5, 5, 5]处理第三件物品电视体积3价值5容量0-2不变容量3为max(5, dp[0]5)5容量4为max(5, dp[1]5)7容量5为max(5, dp[2]5)8容量6为max(5, dp[3]5)10dp数组变为[0, 2, 3, 5, 7, 8, 10]处理第四件物品桌子体积4价值6容量0-3不变容量4为max(7, dp[0]6)7容量5为max(8, dp[1]6)8容量6为max(10, dp[2]6)10dp数组保持[0, 2, 3, 5, 7, 8, 10]最终容量为6的背包能获得的最大价值为10与正确答案一致。四、代码实现1. C语言实现#include stdio.h #define MAX(a, b) ((a) (b) ? (a) : (b)) int main() { // 物品数量、背包容量 int n 4, C 6; // 物品体积和价值 int wt[] {1, 2, 3, 4}; int val[] {2, 3, 5, 6}; // 初始化dp数组 int dp[7] {0}; for (int i 0; i lt; n; i) { // 从大到小遍历背包容量 for (int w C; w gt; wt[i]; w--) { dp[w] MAX(dp[w], dp[w - wt[i]] val[i]); } } printf(容量为%d的背包能获得的最大价值%d\n, C, dp[C]); return 0; }2. Python实现def knapsack_01(n, C, wt, val): dp [0] * (C 1) for i in range(n): for w in range(C, wt[i] - 1, -1): dp[w] max(dp[w], dp[w - wt[i]] val[i]) return dp[C] 测试简化后的问题 n 4 C 6 wt [1, 2, 3, 4] val [2, 3, 5, 6] print(容量为%d的背包能获得的最大价值%d % (C, knapsack_01(n, C, wt, val))) 测试原问题容量2010件物品 n 10 C 20 wt [3, 4, 2, 5, 3, 6, 4, 2, 7, 5] val [5, 6, 3, 8, 4, 9, 7, 4, 11, 7] print(容量为%d的背包能获得的最大价值%d % (C, knapsack_01(n, C, wt, val)))五、总结01背包问题的核心是动态规划通过记录子问题的解来避免重复计算。状态转移方程为dp[w] max(dp[w], dp[w - wt[i]] val[i])需要从大到小遍历背包容量。贪心算法无法得到最优解因为它只考虑了当前的最优选择而没有考虑全局最优。01背包问题是动态规划的基础掌握它可以帮助我们理解更复杂的动态规划问题。 点赞 收藏 关注获取更多算法入门内容