《资源背包动态规划》.ppt

该【《资源背包动态规划》 】是由【相惜】上传分享，文档一共【32】页，该文档可以免费在线阅读，需要了解更多关于【《资源背包动态规划》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。背包类动态规划问题长沙市雅礼中学朱全民整理ppt经典的背包问题〔01背包〕有N件物品;第i件物品Wi公斤;第i件物品价值Ci元;现有一辆载重M公斤的卡车;问选取装载哪些物品,使得卡车运送的总价值最大?整理ppt搜索法对于每种物品,要么装上卡车,要么不装,因此,N种物品的装箱方案共有2N种。按每种物品进行搜索,方法如下:对第i种物品进行搜索如果所有的物品都搜索完,那么更新最优解如果当前的估计达不到最优解,那么回溯如果第i种物品能放,那么放,并标记,否那么选下一个物品去除标记回溯整理ppt动态规划可以按每个物品进行规划,同样每种物品有选和不选两种选择设F(i,j)表示前i件物品载重为j的最大效益,那么有1<=i<=N,0<=j<=N初值:F(0,j)=0F(N,M)即答案显然时间复杂度为O(NM)整理ppt主程序如下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;整理ppt满背包问题〔01背包〕有N件物品;第i件物品Wi公斤;第i件物品价值Ci元;现有一辆载重M公斤的卡车;问选取装载哪些物品,使得卡车开车正好装满时,运送的总价值最大? 假设无法装满卡车,那么输出无解。整理ppt动态规划设F(i,j)表示前i件物品背包为j的最大效益,那么有1<=i<=N,0<=j<=N初值:F(0,j)=0,F(1,j)=-∞F(N,M)即答案显然时间复杂度为O(NM)整理ppt带条件的背包问题〔1〕有N件物品;第i件物品Wi公斤;第i件物品价值Ci元;第i件物品可能带0~2个附件;假设装载附件,必须装载主件,反之没有约束;现有一辆载重M公斤的卡车;问选取装载哪些物品,使得卡车运送的总价值最大?整理ppt分析假设只有主件的情况,显然与经典背包问题完全相同!现在每个物品有附件,我们可以分成4种方案仅装载主件装载主件+第1个附件装载主件+第2个附件装载主件+2个附件由于上述4种并列,这是几种不同的决策同时规划即可整理ppt动态规划设F(i,j)表示前i件物品背包为j的最优解,那么有,1<=i<=N,0<=j<=M时间复杂度O(NM)整理ppt