0-1背包问题实验报告
一・问题描述
4•给定n种物品和一个背包。
物品i的重量是w[i],其价值为v[i],背包容量为Co
问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。
2在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。
不能将物品i装入背包多次，也不能只装入部分的物品io
问题规模
1.物品数目：n=50,
2.背包容量：c=1000,
3.每个物品重量分别为：
{220,208,198,192,180,180,165,162,160,158,
155,130,125,122,120,118,115,110,105,101,
100,100,98,96,95,90,88,82,80,77,
75,73,70,69,66,65,63,60,58,56,
50,30,20,15,10,8,5,3,1,1}
4.每个物品价值分别为：
{80,82,85,70,72,70,66,50,55,25,
50,55,40,48,50,32,22,60,30,32,
40,38,35,32,25,28,30,22,50,30,
45,30,60,50,20,65,20,25,30,10,
20,25,15,10,10,10,4,4,2,1}
三. 实验方法
本次实验将分别通过动态规划法，贪心算法，回溯法及分支界限法四种方法解决0-1背包问题。
四. 算法分析
I •动态规划法
(1)•对动态规划的0-1背包问题，在给定c>0,w
i>0, v
i>0, 1<=i<=n,要求找出一个n 元0-1 向量(x1,x2,...)xn 1},1 < i；使得
x
i{0,
wx
■
I
i 1
n
i而且max
v
ix
io
c,
i1n同时可得出其递推关系，设最优值是背包容量为j,可选物品
i,i+1…盼背包问题的最优值。
于是可建立计算m(l,j)的递归式：
在j>=w
i,为max{m(i+1 ,j),m(i+1 j-w
i)+v
i}，
在0<=j<w
i 时,m(i+15j);
m[n,j]在j>=w
n时为v
n,在OWj <w
n为0。
且该算法的特点是：随着包中物品的加入，包中容量也随之不断在变化,每次包中放物品前都基于包中剩余的容量，当达到最优解时，此时包不一定都装满。
该算法所需的算法的计算时间复杂性为0(2 n),若所给物品重量
i是整数时,该算法的计算时间复杂性为O(min{nc,2n}).
(2).实验结果为：总共装进背包的容量是1OOO；
装进背包物品的总价值为3076o
II .贪心算法
(1)•贪心算法在解决问题的时候，总是做出当前看来是最好的选择，并不从整体上最优加以考虑。
在做出局部意义上的最优选择之后，我们能得到一个近似的最优解，即使它不一定是最优的，但在要求不那么精确地情况下，往往能较为便捷地得到结
果。
贪心算法求解背包问题的步骤：
首先计算每种物品单位重量的价值vi/wi ；
然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背
包。
若将这种物品全部装入背包后，背包内的物品总量未超过C,则选择单位重
量价值次高的物品并尽可能多地装入背包。
依此策略一直进行下去，直到背包装满为止。
(2).实验结果为：
装入背包的物品总价值为：3087o
(3)结果分析：
使用贪心算法，时间复杂度为O (n*logn)。
优于动态规划算法，空间占有也较动态规划少，但贪心算法所得得结果并不一定是最优解。
皿•回溯法
(1)•问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空
间。
问题的解空间应至少包含问题的一个(最优)解。
(2)•回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结
点(根结点)出发，以深度优先的方式搜索整个解空间。
这个开始结点就成为一个活结点，同时也成为当前的扩展结点。
在当前的扩展结点处，搜索向纵深方向移至一个新结点。
这个新结点就成为一个新的活结点，并成为当前扩展结点。
如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。
换句话说，这个结点不再是一个活结点。
此时，应往回移动(回溯)至最近的一个活结点处，并使这个活结点成为当前的扩展结点。
回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空
间中已没有活结点时为止。
(3)•算法设计步骤:
a.针对所给问题，定义问题的解空间；
b •确定易于搜索的解空间结构；
C.以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；
(4).实验结果：
装入背包物品的总价值为：3090o (5)結果分析:
回溯法在最坏的情况下有0(2)个右儿子节点需要计算上界，且计算上界的时间为On
n
(n),所以回溯法时间复杂度为0 (n*2)。
而且对空间复杂性分析来说，该算法
需要栈来存储中间值，故空间复杂度大。
同时随着问题规模的扩大，会使得问题处理起来的时间花销增大,故而构建良好的剪枝函数成为回溯法的关键所在。
但由于回溯法德适应性比较好，很多问题的解决也都会采用它。
IV •分支界限法
(1)•分支限界法运用优先队列扩展了活结点的运行空间。
使得算法在广域中可以较为快捷的剪掉冗余枝。
整个解空间较之于回溯法是快速聚类的，故其时间复杂度较回溯法优，但在空间上却需要相当一部分的处理能力。
对于离散的最优化方法较为适宜，这是分支法好处,却也是其局限所在。
(2)•算法设计步骤：
a.各物品按性价比有大到小排序，构建解空间树；
b.由根节点出发，检查当前左儿子结点的可行性，如果可行，将它加入到子集树
和活动队列中；
c.仅当右儿子结点满足上界约束，才将它加入子集树和活结点优先序列。
d.重复b.c至整个解空间结束。
(3).实验结果：
装入背包的物品的总价值为：3027o。