当前位置:   article > 正文

0-1背包问题(动态规划算法)_0背包公式

0背包公式

0-1背包问题(动态规划算法)

一、思路

我们直接从一个实例开始。
有五件商品,如下表,vi代表它的重量,pi代表它的价值,背包容量为13。
在这里插入图片描述
第一步,初始化备忘录表。
当背包容量为0时:P[i,0]=0;
当没有可选商品时:P[0,c]=0。
在这里插入图片描述
第二步,确定计算顺序。(也可从左到右、从下到上)
在这里插入图片描述
第三步,根据递推公式填表。
在这里插入图片描述
(现在我们结合下图二维表来理解)
i=1时,P[1,c]这行表示只有物品1可选。

P[1,1]位置:c=1,v[1]=10,c<v[i],背包容量小于可选商品,表示不能选该商品,即采用递推公式中P[i-1,c]该方案。将P[0,1]=0照抄在P[1,1]上。(也就是把该位置(i)的上一行(i-1)相同位置的数值抄写下来)

P[1,2]位置~P[1,9]位置也是上面的原理。

P[1,10]位置:c=10,v[1]=10,c>=v[i],背包容量大于等于可选商品,表示能选该商品,此时我们按照递推公式比较 选择该商品 和 不选该商品 哪个方案的P(价值)更大
选择该商品:P[i-1,c-v[i]]+p[i]=P[1-1,10-10]+p[1]=P[0,0]+24=24
不选该商品:P[i-1,c]=0
因为24>0,所以我们选择该商品。

依据上述两种情况填表即可。
在这里插入图片描述
当填完表后,我们知道了最大值,但怎么知道选择了哪些商品呢?
我们通过构造Rec[i,c]数组来记录是否选择该商品。
当选择商品时,Rec[i,c]=1;
当不选择商品时,Rec[i,c]=0;
在这里插入图片描述
在这里插入图片描述
我们由上图开始倒推选择了哪些商品:
Rec[5,13]=1,所以选择了商品五,13-v[5]=13-4=9(减去商品五的重量);
Rec[4,9]=1,代表选择了商品四,9-v[4]=9-5=4(减去商品四的重量);
Rec[3,4]=1,代表选择了商品三,4-v[3]=4-4=0(减去商品三的重量);
此时背包已装满。

所以所选物品为五、四、三。

二、伪代码

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/401535?site
推荐阅读
相关标签
  

闽ICP备14008679号