蛮力法-动态规划法-贪心法求解背包问题(共28页).doc

精选优质文档-倾情为你奉上实验名称：用蛮力法、动态规划法和贪心法求0/1背包问题组的编号：28 作者姓名 ： xxx xxx xxx算法设计与分析完成日期：2013年9月22日星期日专心-专注-专业 目录第一章：简介1第二章：算法规范2数据结构2伪代码3第三章 ：算法测试4 蛮力法4动态规划5贪心法5第四章：分析讨论6算法分析6时间复杂度分析16附录17声明17第一章 ：简介 问题的描述：0/1背包问题是给定n个重量为w1, w2, ,wn、价值为v1, v2, ,vn的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数： （式1）（式2）于是，问题归结为寻找一个满足约束条件式1，并使目标函数式2达到最大的解向量X=(x1, x2, , xn)。背包的数据结构的设计：typedef struct objectint n;/物品的编号int w;/物品的重量int v;/物品的价值wup;wup wpN;/物品的数组，N为物品的个数int c;/背包的总重量 第二章:算法规范数据结构：0/1背包问题是给定n个重量为w1, w2, ,wn、价值为v1, v2, ,vn的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中，在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。所以，我们用了数组，函数作为主要的数据结构。用蛮力法、动态规划法和贪心法求解0-1背包问题的算法设计对比与分析。伪代码如下所示一、蛮力法1,1.1，定义物品结构1.2 input 物品编号，重量，价值2，蛮力法产生子集3，判断子集的可行性4从可行解中找出最优解5输出最优解二、动态规划法1.1 定义物品结构wup1.2定义物品输入函数inputwp1.3定义物品输出函数outputwp2，定义函数findmaxvalue3，输入物品4，调用findmaxvalue5，输出结果三、贪心法1.1 定义物品结构wup1.2 输入物品2，对v/w排序3，输出物品4，选择物品5，计算物品总价值6，输出物品总价值和最优解 第三章：测试结果1. 蛮力法2. 动态规划法3.贪心法这个结果没有运行出来，请老师原谅，谢谢。第四章：分析和讨论（一）算法思想分析：1蛮力法：蛮力法是一种简单直接的解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。蛮力法的关键是依次处理所有的元素。用蛮力法解决0/1背包问题，需要考虑给定n个物品集合的所有子集，找出所有可能的子集（总重量不超过背包容量的子集），计算每个子集的总价值，然后在他们中找到价值最大的子集。所以蛮力法解0/1背包问题的关键是如何求n个物品集合的所有子集，n个物品的子集有2的n次方个，用一个2的n次方行n列的数组保存生成的子集，以下是生成子集的算法：void force(int a4)/蛮力法产生4个物品的子集 int i,j; int n=16; int m,t; for(i=0;i<16;i+) t=i; for(j=3;j>=0;j-) m=t%2; aij=m; t=t/2; for(i=0;i<16;i+)/输出保存子集的二维数组 for(j=0;j<4;j+) printf("%d ",aij); printf("n"); 以下要依次判断每个子集的可行性，找出可行解:void panduan(int a4,int cw)/判断每个子集的可行性，如果可行则计算其价值存入数组cw,不可行则存入0 int i,j; int n=16; int sw,sv; for(i=0;i<16;i+) sw=0; sv=0; for(j=0;j<4;j+) sw=sw+wpj.w*aij; sv=sv+wpj.v*aij; if(sw<=c) cwi=sv; else cwi=0; 在可行解中找出最优解，即找出可行解中满足目标函数的最优解。以下是找出最优解的算法：int findmax(int x164,int cv)/可行解保存在数组cv中，最优解就是x数组中某行的元素值相加得到的最大值int max;int i,j;max=0;for(i=0;i<16;i+) if(cvi>max)max=cvi; j=i;printf("n最好的组合方案是：");for(i=0;i<4;i+)printf("%d ",xji);return max;2动态规划法：动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。动态规划法设计算法一般分成三个阶段：（1）分段：将原问题分解为若干个相互重叠的子问题；（2）分析：分析问题是否满足最优性原理，找出动态规划函数的递推式；（3）求解：利用递推式自底向上计算，实现动态规划过程。 0/1背包问题可以看作是决策一个序列(x1, x2, , xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了(x1, , xi-1)，在决策xi时，问题处于下列两种状态之一：（1）背包容量不足以装入物品i，则xi=0，背包不增加价值；（2）背包容量可以装入物品i，则xi=1，背包的价值增加了vi。 这两种情况下背包价值的最大者应该是对xi决策后的背包价值。令V(i, j)表示在前i(1in)个物品中能够装入容量为j（1jC）的背包中的物品的最大值，则可以得到如下动态规划函数： V(i, 0)= V(0, j)=0 （式3） (式4)式3表明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值均为0。式4的第一个式子表明：如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包；第二个式子表明：如果第i个物品的重量小于背包的容量，则会有以下两种情况：（1）如果把第i个物品装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；（2）如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值较大者作为把前i个物品装入容量为j的背包中的最优解。 以下是动态规划法求解背包问题的算法：int findmaxvalue(wup *p,int x)/x数组用来存放可行解，p是指向存放物品数组的指针 int i,j;int maxvalue;int valueN+1C+1;for(j=0;j<=C;j+)value0j=0; /初始化第0行for(i=0;i<=N;i+)valuei0=0;/初始化第0列/计算数组value中各元素的值for(i=1;i<=N;i+,p+)for(j=1;j<=C;j+)if(p->w >j)valueij=valuei-1j;elsevalueij=max(valuei-1j,(valuei-1j-p->w+p->v);/max函数求两个数当中的大者/逆推求解j=C;for(i=N;i>0;i-)if(valueij>valuei-1j)xi-1=1;/是否被选中的向量的下标也是从0开始j=j-wpi-1.w;/存放物品的下标从0开始else xi-1=0;maxvalue=valueNC;/最大值return maxvalue;3贪心法： 贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。 这种局部最优选择并不总能获得整体最优解（Optimal Solution），但通常能获得近似最优解（Near-Optimal Solution）。贪心法求解的问题的特征：（1）最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。（2）贪心选择性质 所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。用贪心法求解问题应该考虑如下几个方面：（1）候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。例如，在付款问题中，各种面值的货币构成候选集合。（2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。（3）解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。 （4）选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款问题中，贪心策略就是在候选集合中选择面值最大的货币。（5）可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。 背包问题至少有三种看似合理的贪心策略： （1）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。 （2）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。 （3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。应用第三种贪心策略，每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，然后我们就面临了一个最优子问题它同样是背包问题，只不过背包容量减少了，物品集合减少了。因此背包问题具有最优子结构性质。先按单位重量价值最大对物品进行排序。然后再用贪心策略选择的算法如下：float find(float pN,float wN,float xN ,float M,int n) /*先放单位价值量大的物体，再考虑小的物体*/ int i; float maxprice; for (i = 0; i < n; i+) xi = 0; i = 0; maxprice=0; while (i < n && wi < M) M=M-wi; xi =wi; /* 表示放入数量 */ maxprice=maxprice+pi; xn-1=M; i+; if (i < n &&M> 0) maxprice=maxprice+pi*xi/wi; i+; return maxprice;T(n)=O(n2)（二）0/1背包问题的时间复杂度分析方法类型时间复杂蛮力法动态规划法贪心法 T(n)=O(n2)#include <stdio.h>#define N 4#define c 10/总重量typedef struct objectint n;/物品的编号int w;/物品的重量int v;/物品的价值wup;wup wpN;/物品的数组，N为物品的个数/int c;/背包的总重量void force(int a4)/蛮力法产生个物品的子集 int i,j; int n=16;/16行int a164; int m,t; for(i=0;i<16;i+) t=i; for(j=3;j>=0;j-) m=t%2; aij=m; t=t/2; for(i=0;i<16;i+)/输出保存子集的二维数组 for(j=0;j<4;j+) printf("%d ",aij); printf("n"); int findmax(int x4,int cv)/可行解保存在数组cv中，最优解就是x数组中某行的元素值相加得到的最大值 int max;int i,j;max=0; for(i=0;i<16;i+) if(cvi>max)max=cvi; j=i;printf("n最好的组合方案是：");for(i=0;i<4;i+) printf("%d ",xji); printf("n"); return max; void main()void force(int a4);/函数声明int findmax(int x4,int cv); void panduan(int a4,int cw );/函数声明wup wpN;int x164;int max;int a164,cw16,cv16;int i,j,sw,sv;for (i=0;i<N;i+)printf("请输入第%d个物品的编号,重量和价值:n",i+1);scanf("%d%d%d",&wpi.n,&wpi.w,&wpi.v);printf("n");force(a);for(i=0;i<16;i+) sw=0; sv=0; for(j=0;j<4;j+) sw=sw+wpj.w*aij; sv=sv+wpj.v*aij; if(sw<=c) cwi=sv; else cwi=0; max=findmax(a,cw); printf("最大的价值是:"); printf("%d",max); printf("n"); #include <stdio.h>#define N 4#define C 10typedef struct objectint n;/物品的编号int w;/物品的重量int v;/物品的价值wup;wup wpN;/物品的数组，N为物品的个数void inputwp(wup *p)int i,j;for (i=0;i<N;i+)printf("请输入第%d个物品的编号重量和价值:n",i+1);scanf("%d",&p->n);scanf("%d",&p->w); scanf("%d",&p->v);p=p+1;printf("n");void outputwp(wup *p)int i,j;for (i=0;i<N;i+)printf("%d,%d,%d",p->n,p->w,p->v);printf("n");p+;printf("n");int max(int x,int y) return(x>y?x:y);int findmaxvalue(wup *p,int x)/x数组用来存放可行解，p是指向存放物品数组的指针 int i,j;int maxvalue;int valueN+1C+1;for(j=0;j<=C;j+)value0j=0; /初始化第行for(i=0;i<=N;i+)valuei0=0;/初始化第列/计算数组value中各元素的值for(i=1;i<=N;i+,p+)for(j=1;j<=C;j+)if(p->w >j)valueij=valuei-1j;elsevalueij=max(valuei-1j,(valuei-1j-p->w+p->v);/max函数求两个数当中的大者/逆推求解j=C;for(i=N;i>0;i-)if(valueij>valuei-1j)xi-1=1;/是否被选中的向量的下标也是从开始j=j-wpi-1.w;/存放物品的下标从开始else xi-1=0;maxvalue=valueNC;/最大值return maxvalue;void main()wup *p;void inputwp(wup *p);void outputwp(wup *p); int xN; int i;int maxvalue;printf ("背包的总质量为：%d",C);printf ("n");p=wp;inputwp(p);p=wp;outputwp(p);maxvalue=findmaxvalue(p,x);printf("n最大的价值是：%dn",maxvalue);printf ("物品的最佳组合是:n");for(i=0;i<N;i+)printf("%d",xi);printf("n");#include <stdio.h> #include <stdlib.h> typedef struct char name10;int weight; int price; Project; Project *Input(Project *wp,int TotalNum,int TotalWeight) int i,j,Way,GoBack,RealWeight,RealPrice,TotalPrice; Project temp; do printf("请选择:n"); printf(" 1.空间最优n"); printf(" 2.价格最优n"); printf(" 3.价格空间比最优n"); scanf("%d",&Way); switch(Way) case 1: for(i=0;i<TotalNum;i+) for(j=0;j<TotalNum-i-1;j+) if(wpj.weight>wpj+1.weight) temp=wpj; wpj=wpj+1; wpj+1=temp; break; case 2: for(i=0;i<TotalNum;i+) for(j=0;j<TotalNum-i-1;j+) if(wpj.price<wpj+1.price) temp=wpj; wpj=wpj+1; wpj+1=temp; break; case 3: for(i=0;i<TotalNum;i+) for(j=0;j<TotalNum-i-1;j+) if(float)wpj.price/(float)wpj.weight<(float)wpj+1.price/(float)wpj+1.weight) temp=wpj; wpj=wpj+1; wpj+1=temp; break;default: printf("输入错误!n"); exit(1); i=0; RealWeight=wp0.weight; TotalPrice=wp0.price; printf("被装入背包的物品是:n(物品名价格重量)n"); while(RealWeight<TotalWeight&&i<TotalNum) printf("%s %d %dn",wpi.name,wpi.price,wpi.weight); i+; RealWeight+=wpi.weight; TotalPrice+=wpi.price; RealWeight-=wpi.weight; TotalPrice-=wpi.price; printf("求解结束!背包所装物品总重量:%d,总价值:%dn",RealWeight,TotalPrice); printf("退出本次测试请按!n"); scanf("%d",&GoBack); while(GoBack!=0); return wp; void main() int InputWay,TotalNum,i,TotalWeight,RealWeight,Goon,TotalPrice; Project *Array; FILE *fp; do printf("请选择数据录入方式!n"); printf(" 1.文件读入n"); printf(" 2.键盘输入n"); scanf("%d",&InputWay); switch(InputWay) case 1: printf("请输入背包最大容量:"); scanf("%d",&TotalWeight); fp=fopen("data.txt","r"); fscanf(fp,"%dn",&TotalNum); if(Array=(Project*)malloc(TotalNum*sizeof(Project)=NULL) printf("内存已满,申请空间失败!n"); exit(1); else for(i=0;i<TotalNum;i+) fscanf(fp,"%s %d %dn",&Arrayi.name,&Arrayi.price,&Arrayi.weight); fclose(fp); Array=Input(Array,TotalNum,TotalWeight); break; case 2: printf("请输入物品数量及背包容量n"); scanf("%d%d",&TotalNum,&TotalWeight); if(Array=(Project*)malloc(TotalNum*sizeof(Project)=NULL) printf("内存已满,申请空间失败!n"); exit(1); else printf("请输入:物品名价格重量n"); for(i=0;i<TotalNum;i+)scanf("%s%d%d",&Arrayi.name,&Arrayi.price,&Arrayi.weight); Array=Input(Array,TotalNum,TotalWeight); break; default: printf("输入错误!n"); exit(1); printf("继续其他数据测试请按n"); scanf("%d",&Goon); while(Goon=1); delete Array; 声明 我们在此声明，这个题为“用蛮力法、动态规划法和贪心法求解0/1背包问题”的项目的所有工作是由作为一组的我们的成员的各自的努力而完成的。 人员安排: 程序员：xxx 测试员：xxx 报告书写员：xxx