23 01背包问题：动态规划的经典入门案例-云帆数科

一、问题引入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背包问题是动态规划的基础掌握它可以帮助我们理解更复杂的动态规划问题。点赞收藏关注获取更多算法入门内容

企业数字化 ERP 产品动态

相关推荐

DeepOpen三大决策原语完全指南：choice、score、noul如何覆盖企业90%的AI决策场景

DeepOpen三大决策原语完全指南：choice、score、noul如何覆盖企业90%的AI决策场景【免费下载链接】deepopen 非自回归System 1决策引擎，专为结构化类型决策场景设计 DeepOpen Multilingual, non-autoregressive System 1 decision engine. 项目地址: … · 2026/9/27 11:18:06

基于Springboot的二手车交易网站的设计与实现（源码+讲解视频+LW）

温馨提示：本人主页置顶文章(点我)开头有 CSDN 平台官方提供的学长联系方式的名片！ 温馨提示：本人主页置顶文章(点我)开头有 CSDN 平台官方提供的学长联系方式的名片！ 温馨提示：本人主页置顶文章(点我)开头有 CSDN 平台… · 2026/9/27 11:18:06

网站开发用什么字体：5个关键决策与最佳实践

网站开发用什么字体：5个关键决策与最佳实践很多福建的甲方朋友在找建站团队时，一开口就问：“你们服务器搞不懂，域名备案也麻烦，字体能不能随便选？”这话虽糙，但道出了核心痛点。在 Web 开发圈，字体… · 2026/9/27 11:18:06

STM32F103 窗口看门狗 WWDG 实战：窗口期计算、喂狗时机与复位周期实测

文章目录摘要前言WWDG 工作原理：一个带"时间笼子"的看门狗窗口期数学推导：先把时间算明白方案决策：为什么是 WWDG 而不是 IWDG硬件准备与测试环境CubeMX 配置与寄存器级解释容易遗漏的步骤：调试冻结与中断使能核心代码实… · 2026/9/27 11:57:54

小米开源编程助手 MIMO Code 上手：VS Code 配置 TaoToken 与简单使用测试

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 11:57:47

图解步骤拆解响应式网站的意义：告别域名服务器搞不懂的坑

图解步骤拆解响应式网站的意义：告别域名服务器搞不懂的坑域名服务器配置报错，后台代码看不懂，这种“域名服务器搞不懂”的焦虑，是90%中小企业老板在接触网站建设时的第一道坎。别急着找外包公司，先看懂这套图解步骤，你就能明白为什么… · 2026/9/27 11:57:47

运行 Appium + Python Client + 夜神模拟器：TaoToken 统一 Key 接入与 adb 配置实战

科来流量分析结合MCP自动化：用Codex与cmdl.exe打通TaoToken配置链路

手机发一条消息，Cursor 就在你电脑上帮你写好代码了：TaoToken 统一 Key 接入 Cursor CLI 配置实战

MATLAB雷达信号脉冲压缩仿真：LFM线性调频、匹配滤波与距离分辨率实现

简介：这套Matlab仿真工具完整呈现雷达信号脉冲压缩过程，从线性调频（LFM）信号生成、目标回波仿真到匹配滤波压缩处理均有可运行代码支撑，面向电子信息工程、计算机、数学等专业学生，适用于课程设计、期末大作… · 2026/9/27 0:00:01

汕头网站建设制作厂家避坑指南：5大注意事项救急

汕头网站建设制作厂家避坑指南：5大注意事项救急改个需求建站公司拖一周，这种憋屈事我见得太多了。很多汕头老板找本地建站团队，签合同前看着方案挺美，一上线就变脸。今天不聊虚的，直接拆解找汕头网站建设制作厂家时的5个核心注意事项… · 2026/9/27 0:00:01

多模态虚假新闻检测实战：BERT+ResNet双塔与对比学习

简介：基于PyTorch的多模态虚假新闻检测项目完整代码包，面向自然语言处理与计算机视觉交叉方向的开发者、科研人员及毕业设计选题者，解决社交媒体中文本与图像联合识别虚假新闻的问题。系统以BERT预训练模型提取文本语义特征，以Res… · 2026/9/27 0:00:01

MATLAB雷达信号脉冲压缩仿真：LFM线性调频、匹配滤波与距离分辨率实现

汕头网站建设制作厂家避坑指南：5大注意事项救急

多模态虚假新闻检测实战：BERT+ResNet双塔与对比学习

23 01背包问题：动态规划的经典入门案例

相关推荐

了解更多？预约专属演示