资源描述：
《动态规划法解0-1背包问题举例.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、0-1背包问题举例：设n=6，c=20，w={4，5，3，8，6，10},v={20，10，8，18，15，12}解：p[7]={(0,0)}q[7]=p[7]⊕(10,12)={(10,12)}p[6]={(0,0),(10,12)}q[6]=p[6]⊕(6,15)={(6,15),(16,27)}p[5]={(0,0),(6,15),(16,27)}q[5]=p[5]⊕(8,18)={(8,18),(14,33)}p[4]={(0,0),(6,15),(8,18),(14,33)}q[4]=p[4]⊕(3,8)={(3,8),(9,23),(1
2、1,26),(17,41)}p[3]={(0,0),(3,8),(6,15),(8,18),(9,23),(11,26),(14,33),(17,41)}q[3]=p[3]⊕(5,10)={(5,10),(8,18),(11,25),(13,28),(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)}q[2]=p[2]⊕(4,20)={(4,20),(7,28),(9
3、,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),(13,43),(15,46),(17,48),(18,53),(20,56)}构造最优解：i(bagc,bagv)-(wi,vi)∈p[i+1]?(wi,vi)xi1(20,56)-(4,20)∈p[2](4,20)12(16,36)-(5,10)∈p[3](5,10)13(11,26)-(3,8)∈p[4](3,8)
4、14(8,18)-(8,18)∈p[5](8,18)15(0,0)-(6,15)∈p[6](6,15)06(0,0)-(10,12)∈p[7](10,12)0X={1，1，1，1，0，0}。
