用蛮力法、动态规划法和贪心法求解01背包问题讲解

算法设计与分析项目名称：用蛮力法、动态规划法和贪心法求解0/1背包问题作者姓名：余武丹李红波刘红梅完成日期：2013年9月20日目录第一章：简介（Introduction）第二章：算法定义（AlgorithmSpecification）第三章：测试结果（TestingResults）第四章：分析和讨论第一章：简介（Introduction）0/1背包问题是给定n个重量为{w1,w2,…,wn}、价值为{v1,v2,…,vn}的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数：于是，问题归结为寻找一个满足约束条件式1，并使目标函数式2达到最大的解向量X=(x1,x2,…,xn)。背包的数据结构的设计：typedefstructobject{intn;//物品的编号intw;//物品的重量intv;//物品的价值}wup;wupwp[N];//物品的数组，N为物品的个数intc;//背包的总重量第二章：算法定义（AlgorithmSpecification）1、蛮力法蛮力法是一种简单直接的解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。蛮力法的关键是依次处理所有的元素。用蛮力法解决0/1背包问题，需要考虑给定n个物品集合的所有子集，找出所有可能的子集（总重量不超过背包容量的子集），计算每个子集的总价值，然后在他们中找到价值最大的子集。所以蛮力法解0/1背包问题的关键是如何求n个物品集合的所有子集，n个物品的子集有2的n次方个，用一个2的n次方行n列的数组保存生成的子集，以下是生成子集的算法：voidforce(inta[][4])//蛮力法产生4个物品的子集{inti,j;intn=16;intm,t;for(i=0;i16;i++))1(}1,0{1nixCxwiniii（式1）niiixv1max（式2）{t=i;for(j=3;j=0;j--){m=t%2;a[i][j]=m;t=t/2;}}for(i=0;i16;i++)//输出保存子集的二维数组{for(j=0;j4;j++){printf(%d,a[i][j]);}printf(\n);}｝以下要依次判断每个子集的可行性，找出可行解:voidpanduan(inta[][4],intcw[])////判断每个子集的可行性，如果可行则计算其价值存入数组cw,不可行则存入0{inti,j;intn=16;intsw,sv;for(i=0;i16;i++){sw=0;sv=0;for(j=0;j4;j++){sw=sw+wp[j].w*a[i][j];sv=sv+wp[j].v*a[i][j];}if(sw=c)cw[i]=sv;elsecw[i]=0;}在可行解中找出最优解，即找出可行解中满足目标函数的最优解。以下是找出最优解的算法：intfindmax(intx[16][4],intcv[])//可行解保存在数组cv中，最优解就是x数组中某行的元素值相加得到的最大值{intmax;inti,j;max=0;for(i=0;i16;i++){if(cv[i]max){max=cv[i];j=i;}}printf(\n最好的组合方案是：);for(i=0;i4;i++){printf(%d,x[j][i]);}returnmax;}。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(1≤i≤n)个物品中能够装入容量为j（1≤j≤C）的背包中的物品的最大值，则可以得到如下动态规划函数：V(i,0)=V(0,j)=0（式3）(式4)式3表明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值均为0。式4的第一个式子表明：如果第i个物品的重量大于背包的容量，则装入iiiiwjvwjiVjiVwjjiVjiV}),1(),,1(max{),1(),(前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包；第二个式子表明：如果第i个物品的重量小于背包的容量，则会有以下两种情况：（1）如果把第i个物品装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；（2）如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值较大者作为把前i个物品装入容量为j的背包中的最优解。以下是动态规划法求解背包问题的算法：intfindmaxvalue(wup*p,intx[])//x数组用来存放可行解，p是指向存放物品数组的指针{inti,j;intmaxvalue;intvalue[N+1][C+1];for(j=0;j=C;j++)value[0][j]=0;//初始化第0行for(i=0;i=N;i++)value[i][0]=0;//初始化第0列//计算数组value中各元素的值for(i=1;i=N;i++,p++)for(j=1;j=C;j++){if(p-wj){value[i][j]=value[i-1][j];}else{value[i][j]=max(value[i-1][j],(value[i-1][j-p-w]+p-v));//max函数求两个数当中的大者}}//逆推求解j=C;for(i=N;i0;i--){if(value[i][j]value[i-1][j]){x[i-1]=1;//是否被选中的向量的下标也是从0开始j=j-wp[i-1].w;//存放物品的下标从0开始}elsex[i-1]=0;}maxvalue=value[N][C];//最大值returnmaxvalue;}3、贪心法贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解（OptimalSolution），但通常能获得近似最优解（Near-OptimalSolution）。贪心法求解的问题的特征：（1）最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。（2）贪心选择性质所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。用贪心法求解问题应该考虑如下几个方面：（1）候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。例如，在付款问题中，各种面值的货币构成候选集合。（2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。（3）解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。（4）选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款问题中，贪心策略就是在候选集合中选择面值最大的货币。（5）可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。背包问题至少有三种看似合理的贪心策略：（1）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。（2）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。（3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。应用第三种贪心策略，每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，然后我们就面临了一个最优子问题——它同样是背包问题，只不过背包容量减少了，物品集合减少了。因此背包问题具有最优子结构性质。先按单位重量价值最大对物品进行排序，用冒泡排序算法进行排序的算法如下：voidbublesort(wupwp[]){inti,k;wupp;intflag;for(i=1;iN;i++){flag=0;for(k=N-1;k=i;k--){if(wp[k-1].v/wp[k-1].wwp[k].v/wp[k].w)//比较物品单位重量的价值，按从大到小排序{p.n=wp[k-1].n;p.v=wp[k-1].v;p.w=wp[k-1].w;wp[k-1].n=wp[k].n;wp[k-1].v=wp[k].v;wp[k-1].w=wp[k].w;wp[k].n=p.n;wp[k].v=p.v;wp[k].w=p.w;flag=1;}}if(flag==0)break;}}然后再用贪心策略选择的算法如下：inttx_findmaxvalue(wupwp[],intx[])//用贪心算法找出放入背包中物品的最佳组合//wp为指向物品数组,x是存放解向量的数组{inti;intcw,maxvalue;cw=C;//cw为中间变量，用来临时存储背包的总重量bublesort(wp);Outputwp(wp);maxvalue=0;for(i=0;iN;i++)//对已排过序的数组，顺序选择物品是否可以放入背包{if(wp[i].wcw)//如果物品的重量小于背包的重量，则放入背包{x[wp[i].n-1]=1;//该物品被选中，对应的向量为1maxvalue=maxvalue+wp[i].v;//累加价值cw=cw-wp[i].w;//每放入一件物品背包的总重量减少}elsex[wp[i].n-1]=0;}returnmaxvalue;}第三章：测试结果（TestingResults）1.蛮力法测试结果：输入完毕后按Enter键有如下结果：2.动态规划法调试结果3.贪心法调试结果：(1).空间最优的贪心策略结果(2).价格最优的贪心策略结果(3).价格空间比最优的贪心策略结果第四章：分析和讨论算法的时间复杂度和空间复杂度的分析，对算法进一步改进的讨论。附录：源代码（基于C语言的）1.蛮力法求解01背包问题源程序：#includestdafx.h#includestdlib.h#inclu