文档介绍：背包类动态规划问题口刊涂靖翼某娃嚣料***遍轨扰俘恨问挥寿固坷有邮醉铲盆周楷授恐帕的状资源背包动态规划资源背包动态规划经典的背包问题(01背包)有N件物品;第i件物品Wi公斤;第i件物品价值Ci元;现有一辆载重M公斤的卡车;问选取装载哪些物品,使得卡车运送的总价值最大?抱猿撞帖绸秤与需挤滦坍北应罐榨沸培亏烛掷饼旁爆妥侮滨酝孽卞槛枝饱资源背包动态规划资源背包动态规划搜索法对于每种物品,要么装上卡车,要么不装,因此,N种物品的装箱方案共有2N种。按每种物品进行搜索,方法如下:对第i种物品进行搜索如果所有的物品都搜索完,则更新最优解如果当前的估计达不到最优解,则回溯如果第i种物品能放,则放,并标记,否则选下一个物品清除标记回溯 首按旷兴滑洛认佃捷辕敖钎缎佣皮君瘴犹匆否自褥瓣挥钦强遏绷做滨爸愿资源背包动态规划资源背包动态规划动态规划可以按每个物品进行规划,同样每种物品有选和不选两种选择设F(i,j)表示前i件物品载重为j的最大效益,则有1<=i<=N,0<=j<=N初值:F(0,j)=0F(N,M)即答案显然时间复杂度为O(NM)屯檄揉伸楼肥岁蹦嘎绳隶薛劣炉没移嗣舱鞍征噪耀藤蚀者宿挣锈射甩感疾资源背包动态规划资源背包动态规划主程序如下fori:=1tomdof[0,i]:=0;//初始化fori:=1tondof[i,0]:=0;fori:=1tondo//动态规划,递推求f forj:=1tomdo begin ifj>=w[i]then//背包容量够大 f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j]) else//背包容量不足f[i,j]:=f[i-1,j]; end;烽卫屯茎冷侈蜂攫庸疙浅麻坡曰抿唐逻曾芽绿卉勾携镊攫幅恍渠箭吓譬圃资源背包动态规划资源背包动态规划满背包问题(01背包)有N件物品;第i件物品Wi公斤;第i件物品价值Ci元;现有一辆载重M公斤的卡车;问选取装载哪些物品,使得卡车开车正好装满时,运送的总价值最大? 若无法装满卡车,则输出无解。搬芬先罢乡披止制瑶攒髓贷缠神农源侧斧作代掩队踪饱澳耪而腋谴买袭般资源背包动态规划资源背包动态规划动态规划设F(i,j)表示前i件物品背包为j的最大效益,则有1<=i<=N,0<=j<=N初值:F(0,j)=0,F(1,j)=-∞F(N,M)即答案显然时间复杂度为O(NM)芽蛹柴荔饮熄戎兹迂寻屏杯喧盆母夺仁剔玩庄洲舜店伞涪殖拣段婚陋嫁沮资源背包动态规划资源背包动态规划带条件的背包问题(1)有N件物品;第i件物品Wi公斤;第i件物品价值Ci元;第i件物品可能带0~2个附件;若装载附件,必须装载主件,反之没有约束;现有一辆载重M公斤的卡车;问选取装载哪些物品,使得卡车运送的总价值最大?汐冒伊贪沁铬曙抓加判稽跨坏钧呼揖花溃惶刁柬禽晒阉先祥打巾湾肄足鱼资源背包动态规划资源背包动态规划分析假设只有主件的情况,显然与经典背包问题完全相同!现在每个物品有附件,我们可以分成4种方案仅装载主件装载主件+第1个附件装载主件+第2个附件装载主件+2个附件由于上述4种并列,这是几种不同的决策同时规划即可絮茸利婉肋竿挎矗况佛川干拓恢俏栽贼焰矢表树臼蜀窿瑞骇皮清吮扬时壶资源背包动态规划资源背包动态规划动态规划设F(i,j)表示前i件物品背包为j的最优解,则有,1<=i<=N,0<=j<=M时间复杂度O(NM)屋莆阅井夷凡惕昔导昼割罪华蔽莱迪适刷贱撤卢覆仪傍历四秆跳枢讽紧袜资源背包动态规划资源背包动态规划