限界与剪枝求解0/1背包问题
一、 算法思想描述
首先对物体按照价值重量比进行排序。
再从第一个物体开始,对每个物体分两种状态求解:放入与不放入。
在每次求解时都计算该状态可能达到的最优价值,并放入大顶堆中。
当两种状态都求解完后从堆中取出堆顶元素,从该元素所代表的状态中继续进行分支计算。直到深度达到n,问题得到解。
回溯法求解0/1背包问题
给定背包的载重量M=20,有6个物体,价值分别为11,8,15,18,12,6,重量分别为5,3,2,10,4,2。利用回溯法求解上述问题。