资源描述：
《动态规划法解0-1背包问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、动态规划法解0-1背包问题举例动态规划法解0-1背包问题设n=6，c=20，w={4，5，3，8，6，10},v={20，10，8，18，15，12}动态规划法解0-1背包问题设n=6，c=20，w={4，5，3，8，6，10},v={20，10，8，18，15，12}解：p[7]={(0,0)}，（W6,V6）=（10，12）q[7]=p[7]⊕(10,12)={(10,12)}p[6]={(0,0),(10,12)}动态规划法解0-1背包问题设n=6，c=20，w={4，5，3，8，6，10},v={20，10，8，18，15，12}解：p[
2、6]={(0,0),(10,12)}，（W5,V5）=（6，15）q[6]=p[6]⊕(6,15)={(6,15),(16,27)}p[5]={(0,0),(6,15),(16,27)}动态规划法解0-1背包问题设n=6，c=20，w={4，5，3，8，6，10},v={20，10，8，18，15，12}解：p[5]={(0,0),(6,15),(16,27)}（W4,V4）=（8，18）q[5]=p[5]⊕(8,18)={(8,18),(14,33)}p[4]={(0,0),(6,15),(8,18),(14,33)}动态规划法解0-1背包问题
3、设n=6，c=20，w={4，5，3，8，6，10},v={20，10，8，18，15，12}解：p[4]={(0,0),(6,15),(8,18),(14,33)}（W3,V3）=（3，8）q[4]=p[4]⊕(3,8)={(3,8),(9,23),(11,26),(17,41)}p[3]={(0,0),(3,8),(6,15),(8,18),(9,23),(11,26),(14,33),(17,41)}动态规划法解0-1背包问题设n=6，c=20，w={4，5，3，8，6，10},v={20，10，8，18，15，12}解：p[3]={(0,
4、0),(3,8),(6,15),(8,18),9,23),(11,26),(14,33),(17,41)},（W2,V2）=（5，10）q[3]=p[3]⊕(5,10)={(5,10),(8,18),(11,25),(13,8),(14,33),(16,36),(19,43)}p[2]={(0,0),(3,8),(5,10),(6,15),(8,18),(9,23),(11,26),(13,28),(14,33),(16,36),(17,41),(19,43)}动态规划法解0-1背包问题设n=6，c=20，w={4，5，3，8，6，10},v={
5、20，10，8，18，15，12}解：p[2]={(0,0),(3,8),(5,10),(6,15),(8,18),(9,23),(11,26),(13,28),(14,33),(16,36),(17,41),(19,43)}（W1,V1）=（4，20）q[2]=p[2]⊕(4,20)={(4,20),(7,28),(9,30),(10,35),(12,38),(13,43),(15,46),(17,48),(18,53),(20,56)}p[1]={(0,0),(3,8),(4,20),(7,28),(9,30),(10,35),(12,38)
6、,(13,43),(15,46),(17,48),(18,53),(20,56)}动态规划法解0-1背包问题设n=6，c=20，w={4，5，3，8，6，10},v={20，10，8，18，15，12}解：p[1]={(0,0),(3,8),(4,20),(7,28),(9,30),(10,35),(12,38),(13,43),(15,46),(17,48),(18,53),(20,56)}P[1]中的最后跳跃点(20,56)说明背包恰好装满，其最大价值可达56。∴m(1,c)=m(1,20)=56。以下构造最优解。动态规划法解0-1背包问题设
7、n=6，c=20，w={4，5，3，8，6，10},v={20，10，8，18，15，12}解：构造最优解当i=1,（W1,V1）=（4,20）∵(20,56)-(W1,V1)=(20,56)-(4,20)=(16,36)∈p[2]∴X1=1。p[2]={(0,0),(3,8),(5,10),(6,15),(8,18),(9,23),(11,26),(13,28),(14,33),(16,36),(17,41),(19,43)}动态规划法解0-1背包问题设n=6，c=20，w={4，5，3，8，6，10},v={20，10，8，18，15，12}
8、解：构造最优解当i=2,（W2,V2）=（5,10）∵(16,36)-(W2,V2)=(16,36)-(5,10)=(11,26)∈p[
