0-1背包问题实验报告.doc

0-1背包问题实验报告
一．问题描述
给定n种物品和一个背包。物品i的重量是w[i]，其价值为v[i]，背包容量为c。
问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。
在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。
不能将物品i装入背包多次，也不能只装入部分的物品i。
二．问题规模
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}
每个物品价值分别为：
{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背包问题。
四．算法分析
Ⅰ.动态规划法
（1）.对动态规划的0-1背包问题，在给定c>0, >0，>0，1<=i<=n，要求找出一个n元0-1向量（x1,x2,…,xn）， {0，1},1≤i≤n；使得，而且。
同时可得出其递推关系，设最优值m[i,j]是背包容量为j，可选物品i,i+1…,n时0-1背包问题的最优值。于是可建立计算m(I,j)的递归式：
m[i,j]在j>=,为max{m(i+1,j),m(i+1,j-)+},
在0<=j<时，m(i+1,j);
m[n,j]在j>=时为，在0≤j≤为0。
且该算法的特点是：随着包中物品的加入，包中容量也随之不断在变化，每次包中放物品前都基于包中剩余的容量，当达到最优解时，此时包不一定都装满。该算法所需的算法的计算时间复杂性为O()，若所给物品重量是整数时，该算法的计算时间复杂性为O(min{nc,}).
（2）.实验结果为：总共装进背包的容量是1000；
装进背包物品的总价值为3076。

Ⅱ.贪心算法
（1）.贪心算法在解决问题的时候，总是做出当前看来是最好的选择，并不从整体上最优加以考虑。在做出局部意义上的最优选择之后，我们能得到一个近似的最优解，即使它不一定是最优的，但在要求不那么精确地情况下，往往能较为便捷地得到结果。
贪心算法求解背包问题的步骤:
首先计算每种物品单位重量的价值vi/wi；
然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。
若将这种物品全部装入背包后，背包内的物品总量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包。
依此策略一直进行下去，直到背包装满为止。
(2). 实验结果为：
装入背包的物品总价值为：3087。
（3）结果分析：
使用贪心算法，时间复杂度为O（n*logn）。