动态规划解决0-1背包问题

这几天算法老师布置了一个作业是关于背包问题的,在这里记录一下解决的过程:

一:背包问题的描述

有n1,n2,n3....个物品,每个物品的重量为w1,w2,w3.....,每个物品的价值为v1,v2,v3....,现在有一个承重量为C的背包,求出要怎样放物品才能使的装入背包的物品价值总和最大。
由于每个物品只有一个,并且只能选择放或不放,因此用0表示物体没有放进背包中,1表示物体放进背包中

二:分析过程(以具体的例题来分析)

题目描述: 现有一个可以承重为6的背包bag,以及3个物品,它们的重量分别为2,3,4,价值为1,2,5。用动态规划解决此背包问题,获取最佳组合
为了方便思考,我们使背包的重量从0开始逐渐向6加,并且假设还有一个重量为0的物品,这样,我们给四个物品编号为0,1,2,3。并得到以下表格,w代表物品重量,v代表物品价值。表中数据表示在当前容量下,所能放入的最大价值,数据如何得出,会在后边分析
动态规划解决0-1背包问题
分析问题:
在选择物品放入背包中时,有两种可能:假设当前物品编号为n

相关推荐