背包问题实验报告

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<wiV( i, j) = maxV(i

3、-1, j), V(I, j-1)+vi j>=wj按照下述方法来划分段：第一段只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入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 如果value

5、>maxValue, 则maxValue=value;，并把该二进制序列T复制到S数组中以记录最优解。贪心法：输入：物品总数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输出：背包所装物

6、品的最大总价值1. 初始化过程图2. 双重循环，逐步求出将前i个物品放到容量为j的背包获得的最大价值 for(i=1;i<=n;i+) for(j=1;j<=C;j+)如果j<wi, 则Vij=Vi-1j;否则Vij=Max(Vi-1j,Vi-1j-wi+vi);3. 回溯求得最优解循环for(j=C,i=n;i>0;i-)如果Vij>Vi-1j， 则xi=1;j=j-wi;否则 xi=0;回溯法（递归）输入：物品总数n，每个物品的重量wi和价值vi，背包容量C输出：背包所装物品的最大总价值1. 从第一个物品开始,t=1;2. 如果legal(t)=1,则back

7、Track（t+1）分析下一个物品3. 如果t>n，求出背包的总价值value，如果value大于最大价值，则把最大价值更新，同时更新记录物品装入情况的数组P, 以记录最优解。六 核心源代码 #include<iostream>#include<algorithm>#include<stdlib.h>#include<stdio.h>#include<time.h>#include<windows.h>using namespace std;int w505, v505,n;long C;/回溯法int p500,P

8、500;/回溯法中分别记录当前解和最优解的状态数组int Value=0;/回溯法中的最大价值bool legal(int t) int sum=0; for(int i=1;i<=t;i+) sum+=wi*pi; if(sum>C) return false; else return true;void backTrack(int t) if(t>n) int i; int value=0; for(i=1;i<=n;i+) value+=vi*pi; /cout<<pi; if(value>Value) Value=value; for(i=1;

9、i<=n;i+) Pi=pi; else for(int i=1;i>=0;i-) pt=i; if(legal(t) backTrack(t+1); int Back() backTrack(1); return Value;/动态规划法int Max(int a,int b) return a>b?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+)fo

10、r(j=1;j<=C;j+)if(j<wi)Vij=Vi-1j;elseVij=Max(Vi-1j,Vi-1j-wi+vi);for(j=C,i=n;i>0;i-)if(Vij>Vi-1j)xi=1;j=j-wi;else xi=0; return VnC;/蛮力法int Force()/蛮力法int maxValue=0;int m=1<<n;int S32,T32;for(int i=1;i<m;i+)int t=1;int temp=i;while(temp)Tt+=temp%2;temp=temp/2;int j;/*for(j=1;j<

11、t;j+) cout<<Tj;*/int weight=0,value=0;for(j=1;j<t;j+)if(Tj=1 && weight+wj<=C )weight=weight+wj;value=value+vj;if(maxValue<value)maxValue=value;int k=0;for(j=0;j<t;j+)Sk+=Tj;return maxValue;/贪心法struct Node int i; double w,v;node500;int cmp(Node a,Node b) return (a.v/a.w)>

12、(b.v/b.w);int 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+) cout<<nodei.w<<" "<<nodei.v<<endl; */ int temp=C; i=1; while(temp && (i<=n) if(nodei.w<=temp) maxValue+

13、=nodei.v; nodei.i=1; temp-=nodei.w; / cout<<nodei.w<<" " i+; return maxValue;int Random() return (rand()%(1000)+1);void text(int (*matter)() LARGE_INTEGER litmp;LONGLONG start,over;double dfMinus,dfFreq,dfTim; QueryPerformanceFrequency(&litmp); dfFreq=(double)litmp.QuadPart

14、; QueryPerformanceCounter(&litmp); start=litmp.QuadPart;for(int k=0;k<100;k+) C=0; n=Random()%30; for(int i=1;i<=n;i+) wi=Random(); vi=Random(); C=C+wi; C=C/2; matter(); /cout<<matter()<<endl; QueryPerformanceCounter(&litmp); over=litmp.QuadPart; dfMinus=(double)(over-start

15、); dfTim=dfMinus/dfFreq/100; cout<<"平均时间T(k): " printf("%et",dfTim); cout<<endl;int main()cout<<"先测试算法的正确性"<<endl;n=4;C=10;w1=7;w2=3;w3=4;w4=5;v1=42;v2=12;v3=40;v4=25;cout<<"蛮力法"<<Force()<<endl;cout<<"贪心法&qu

16、ot;<<greed()<<endl;cout<<"动态规划法"<<KnapSack()<<endl;cout<<"回溯法"<<Back()<<endl;cout<<"测试时间效率："<<endl;srand(unsigned)time(NULL);cout<<"动态规划法的执行时间："<<endl;cout<<"蛮力法的执行时间："<

17、<endl;text(Force);cout<<"贪心法的执行时间"<<endl;text(greed);cout<<"动态规划法的执行时间"<<endl;text(KnapSack);cout<<"回溯法的执行时间"<<endl; text(Back);return 0;七 实验结果及分析下面的结果是每个算法都分别运行50次后的平均运行时间：根据结果可以得出，蛮力算法的效率是最低的，回溯算法的时间效率优势很明显是最高的，而贪心法和动态规划的效率也均高于蛮力

18、法，且二者相差不明显。蛮力法时间复杂性分析：对于n个元素的集合，其子集数量时2n,所以不论生成子集的算法效率有多高，蛮力法求接0/1背包问题都会导致一个下界为2n的算法。蛮力法的特点：蛮力法是一种简单直接的解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。贪心法时间复杂性分析：贪心法首选对物品进行了排序，按照价值/重量将序排列，此处采用的是快速排序，时间复杂性为O(nlogn);然后按照物品的大小依次装入背包中，其时间复杂性我O(n),故总的时间复杂性为O(nlogn)。贪心法的特点：贪心法的贪心策略需要满足最优子结构性质和整体贪心选择性质。在o/1背包问题中，选择单位重量价值最大的物

19、品，在背包价值增长和背包容量消耗两者之间寻找平衡，作为贪心策略满足最优子结构性质。动态规划法的时间复杂性分析：动态规划法的算法中第一个for循环的时间性能是O(n), 第二个for循环的时间性能是O(C),第三个for循环是两层嵌套的for循环其时间性能是O(n*C),算法的时间复杂性是O(n*C)；动态规划法的特点：动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，下次需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。回溯法的时间复杂性分析：回溯法实质上是蛮力穷举法，所以最不理想的情况下，回溯法求解0/1背包问题的时间复杂度为O(2n).在求0/1背包问题中，回溯法做到了很好的剪枝，减少了运算量，所以虽然回溯法本质上是蛮力穷