文档介绍：经典的背包问题(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)多层背包问题有N件物品;第i件物品Wi公斤;第i件物品价值Ci元;现有一辆载重M公斤的卡车;第i件物品限制最多只能取Xi个;问选取装载哪些物品,使得卡车运送的总价值最大?