背包问题实验报告(共15页).doc

《背包问题实验报告(共15页).doc》由会员分享，可在线阅读，更多相关《背包问题实验报告(共15页).doc（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上算法设计与分析实验报告书实验名称： 0/1背包问题 学 号： 姓 名： 实验时间： 2015年 6 月 1 日专心-专注-专业 一 实验目的和要求（1） 深刻掌握贪心法、动态规划法、回溯法的设计思想并能熟练运用（2） 理解这样一个观点：同样的问题可以用不同的方法来解决，一个好的算法是反复努力和重新修正的结果。 二 实验内容（1）分别用蛮力法贪心法、动态规划法、回溯法设计0/1背包问题的算法。（2）分析算法随n和C变化的时间性能，随机产生参数n和C，收集算法执行的时间（3）讨论n和C变化时，动态规划法和回溯法的时间性能。（4）讨论几种算法在该问题求解上的特点。三 实验环

2、境 VC+6.0四 设计思想及实验步骤 蛮力法的设计思想和步骤将所有排列下的背包的重量和价值都计算出来，选择重量不大于背包的总重量下的最大价值。贪心法的设计思想和步骤首先计算每种物品单位重量的价值vi/wi；按单位价值对物品进行升序排列。然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包，直到背包装满为止。动态规划法的设计思想和步骤令V(i, j)表示在前i个物品中能够装入容量为j的背包中的物品的最大价值，则可以得到如下动态函数：V（i, j）=0 (i=0或j=0)V( i, j) = V(i-1, j) j=wj按照下述方法来划分段：第一段只装入前1个物品，确定在各种情况下的

3、背包能够得到的最大价值；第二阶段，只装入2个物品，确定在各种情况下的背包能够得到的最大价值；以此类推，直到第n个阶段。最后V(n, C)便是容量为C的背包中装入n个物品时获取到的最大价值。回溯法的设计思想和步骤为了避免生成那些不可能产生最佳解的问题状态，要不断的利用越约束条件来剪掉那些实际上不可能产生所需解的节点，以减少问题额计算量。对于n种可选物品的0/1背包问题，其解空间长度由长度为n的0-1向量组成，可用子集数表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索进入左子树，否则返回上一节点，搜索右子数。时间测试的设计思想蛮力法由于需要考虑每一种情况所以物品的个数不能太多，所以设计

4、时间测试函数在1到32的范围内随机残生物品的个数n，然后在随机产生n个物品每个物品的重量和价值，将背包容量设为n个物品总重量的一半，求出最优解。重复执行背包求解过程，然后求出其平均时间消耗。算法描述如下：蛮力法：输入：物品总数n，每个物品的重量wi和价值vi，背包容量C输出：背包所装物品的最大总价值1. 求出2的n次方2. 循环i从1到m-1，2.1 求出i的二进制2.2 根据i的二进制序列，判断重量和是否小于或等于C，如果等于则求出总价值value，2.3 如果valuemaxValue, 则maxValue=value;，并把该二进制序列T复制到S数组中以记录最优解。贪心法：输入：物品总数

5、n，每个物品的重量wi和价值vi，背包容量C输出：背包所装物品的最大总价值1. 将每个物品的重量和价值存放到保存物品信息的结构体node中2. 将node数组中的物品暗中单位价值的大小从大到小排序3. Temp=C;4. 循环i从1到n如果nodei.w=temp，将物品放入背包，标记nodei=1; temp-=nodei.w; i+;如果temp=0背包被装满，结束循环。动态规划法输入：物品总数n，每个物品的重量wi和价值vi，背包容量C输出：背包所装物品的最大总价值1. 初始化过程图2. 双重循环，逐步求出将前i个物品放到容量为j的背包获得的最大价值 for(i=1;i=n;i+) fo

6、r(j=1;j=C;j+)如果j0;i-)如果VijVi-1j， 则xi=1;j=j-wi;否则 xi=0;回溯法（递归）输入：物品总数n，每个物品的重量wi和价值vi，背包容量C输出：背包所装物品的最大总价值1. 从第一个物品开始,t=1;2. 如果legal(t)=1,则backTrack（t+1）分析下一个物品3. 如果tn，求出背包的总价值value，如果value大于最大价值，则把最大价值更新，同时更新记录物品装入情况的数组P, 以记录最优解。六 核心源代码 #include#include#include#include#include#includeusing namespace

7、 std;int w505, v505,n;long C;/回溯法int p500,P500;/回溯法中分别记录当前解和最优解的状态数组int Value=0;/回溯法中的最大价值bool legal(int t) int sum=0; for(int i=1;iC) return false; else return true;void backTrack(int t) if(tn) int i; int value=0; for(i=1;i=n;i+) value+=vi*pi; /coutValue) Value=value; for(i=1;i=0;i-) pt=i; if(legal

8、(t) backTrack(t+1); int Back() backTrack(1); return Value;/动态规划法int Max(int a,int b) return ab?a:b;int KnapSack()/动态规划法int V505505;int x1005;int i,j;for(i=0;i=n;i+)/初始化第0列Vi0=0;for(j=0;j=C;j+)V0j=0;/初始化第0行for(i=1;i=n;i+)for(j=1;j=C;j+)if(j0;i-)if(VijVi-1j)xi=1;j=j-wi;else xi=0; return VnC;/蛮力法int Fo

9、rce()/蛮力法int maxValue=0;int m=1n;int S32,T32;for(int i=1;im;i+)int t=1;int temp=i;while(temp)Tt+=temp%2;temp=temp/2;int j;/*for(j=1;jt;j+) coutTj;*/int weight=0,value=0;for(j=1;jt;j+)if(Tj=1 & weight+wj=C )weight=weight+wj;value=value+vj;if(maxValuevalue)maxValue=value;int k=0;for(j=0;j(b.v/b.w);int

10、 greed() int i; int maxValue=0; for(i=1;i=n;i+) nodei.i=0; nodei.w=wi; nodei.v=vi; sort(node+1,node+n+1,cmp); /*for(i=1;i=n;i+) coutnodei.w nodei.vendl; */ int temp=C; i=1; while(temp & (i=n) if(nodei.w=temp) maxValue+=nodei.v; nodei.i=1; temp-=nodei.w; / coutnodei.w ; i+; return maxValue;int Random

11、() return (rand()%(1000)+1);void text(int (*matter)() LARGE_INTEGER litmp;LONGLONG start,over;double dfMinus,dfFreq,dfTim; QueryPerformanceFrequency(&litmp); dfFreq=(double)litmp.QuadPart; QueryPerformanceCounter(&litmp); start=litmp.QuadPart;for(int k=0;k100;k+) C=0; n=Random()%30; for(int i=1;i=n;

12、i+) wi=Random(); vi=Random(); C=C+wi; C=C/2; matter(); /coutmatter()endl; QueryPerformanceCounter(&litmp); over=litmp.QuadPart; dfMinus=(double)(over-start); dfTim=dfMinus/dfFreq/100; cout平均时间T(k): ; printf(%et,dfTim); coutendl;int main()cout先测试算法的正确性endl;n=4;C=10;w1=7;w2=3;w3=4;w4=5;v1=42;v2=12;v3=

13、40;v4=25;cout蛮力法Force()endl;cout贪心法greed()endl;cout动态规划法KnapSack()endl;cout回溯法Back()endl;cout测试时间效率：endl;srand(unsigned)time(NULL);cout动态规划法的执行时间：endl;cout蛮力法的执行时间：endl;text(Force);cout贪心法的执行时间endl;text(greed);cout动态规划法的执行时间endl;text(KnapSack);cout回溯法的执行时间endl; text(Back);return 0;七 实验结果及分析下面的结果是每个算

14、法都分别运行50次后的平均运行时间：根据结果可以得出，蛮力算法的效率是最低的，回溯算法的时间效率优势很明显是最高的，而贪心法和动态规划的效率也均高于蛮力法，且二者相差不明显。蛮力法时间复杂性分析：对于n个元素的集合，其子集数量时2n,所以不论生成子集的算法效率有多高，蛮力法求接0/1背包问题都会导致一个下界为2n的算法。蛮力法的特点：蛮力法是一种简单直接的解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。贪心法时间复杂性分析：贪心法首选对物品进行了排序，按照价值/重量将序排列，此处采用的是快速排序，时间复杂性为O(nlogn);然后按照物品的大小依次装入背包中，其时间复杂性我O(n),

15、故总的时间复杂性为O(nlogn)。贪心法的特点：贪心法的贪心策略需要满足最优子结构性质和整体贪心选择性质。在o/1背包问题中，选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡，作为贪心策略满足最优子结构性质。动态规划法的时间复杂性分析：动态规划法的算法中第一个for循环的时间性能是O(n), 第二个for循环的时间性能是O(C),第三个for循环是两层嵌套的for循环其时间性能是O(n*C),算法的时间复杂性是O(n*C)；动态规划法的特点：动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题

16、求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，下次需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。回溯法的时间复杂性分析：回溯法实质上是蛮力穷举法，所以最不理想的情况下，回溯法求解0/1背包问题的时间复杂度为O(2n).在求0/1背包问题中，回溯法做到了很好的剪枝，减少了运算量，所以虽然回溯法本质上是蛮力穷举法，因为减去了很多情况的分析，在时间效率上有很大的优势。八 实验体会（包括本实验中遇到的问题、具体的解决方法、还没有解决的问题、实验收获等）1. 开始时没有设置随机种子，导致每次运行测试的数据一样，后来看了下书知道了问题

17、所在。2. 贪心算法还有点问题，对于物品中存在若干个单位价值相同的物品时，可能得到的最优解是不正确的。例如：w1=3;w2=2;w3=1;w4=4;w5=5;v1=25;v2=20;v3=15;v4=40;v5=50;在物品重量及价值如上时，贪心法得到的最优解是60，但是其他三个算法的得到的最优解均是65，可见贪心法得到的结果是不正确的。3. 蛮力法的时间复杂度是O（2n），其形成的二进制序列与物品的个数有关，整形的长度只有32位，所以只有在物品的个数不超过32个才能用二进制序列一一表示，因为这个缘故我在时间效率测试函数中，将物品个数的随机总数设置在30以内，蛮力法的时间复杂度很大，如果测试次数很多的话程序要好久才能运行出结果，在这个问题上，我认为可以先粗略得出四中算法的时间效率差异，然后在比较贪心法、动态规划法和回溯法的时间效率。4. 回溯法是用递归形式写的，因为觉得递归的回溯要好理解一些，但是在写迭代的回溯法时，对于程序是如何回溯的我还有点模糊，所以代码还没调试成功。5. 在写这个实验报告感觉将四章的基本知识系统的复习了下，现在对于它们之间的思想，差异以及适用的范围有了更清晰的认识。0/1背包问题是个易理解有可以很好帮助我们理解不同算法思想的实例。