背包问题 #
- 背包问题的介绍
- 背包问题的算法分析
- 背包问题代码实现
背包问题的介绍 #
给定n种物品和一个容量为c的背包,每个物品i的重量为Wi,其价值为Vi。要求选择物品装入背包,使得装入背包中物品的总价值最大?在选择物品i装入背包的时候,同一物品可以被选择多次,同时也不一定要将全部物品装入。
例如:背包的容量为50公斤,物品A重10公斤价值60元,物品B重20公斤,价值100元,物品C重30公斤,价值120元,该如何装载使得背包的价值最大?
背包问题的算法分析 #
贪心策略的制定:
- 价值贪心策略:选择价值最大的物品
- 重量贪心策略:选择重量最小的物品
- 价值重量比策略:选择单位价值最大的物品
因为物品可以被分割,所以对于背包只存在两种情况,要么能够装载所有物品,要么被装满。因此能够很简单的证明,背包所装的物品单位价值越高,最后的价值最大。因此只需要将输入物品的单位价值从大到小排序,依次选择即可。
背包问题的代码实现 #
c=50 w=[10,20,30]#将物品的重量和价值按照单位价值排序,可自行使用排序算法排序,建议使用字典 v=[60,100,120] res=[]#保存放入物品质量 value = 0 i = 0 while True: if(c-w[i]>=0): res.append(w[i]) c = c - w[i] else: i += 1 if i == len(w): break for i in res: value += v[w.index(i)] print('放入物品重量为:', res) print('总价值为:', value)
小结 #
- 根据背包问题,理解贪心算法的概念
- 掌握背包问题求解的贪心算法,能够根据实际问题作出合适的贪心策略
习题 #
- 1.如果上述例子中,物品不可分割,每件物品为可选和不可选两个状态?就变为了0-1背包问题,仍用上述的贪心策略能够得出正确答案吗?如果不能举出反例并说明原因
- 2.请用回溯的方法,求解问题1中的0-1背包问题?