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

算法设计与分析项目名称:用蛮力法、动态规划法和贪心法求解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)于是,问题归结为寻找一个满足约束条件式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;i<16;i++){t=i; for(j=3;j>=0;j--) { m=t%2; a[i][j]=m; t=t/2; }}for(i=0;i<16;i++)//输出保存子集的二维数组{ for(j=0;j<4;j++) { printf("%d",a[i][j]); } printf("\n");}}以下要依次判断每个子集的可行性,找出可行解:voidpanduan(inta[][4],intcw[])////判断每个子集的可行性,如果可行则计算其价值存入数组cw,不可行则存入0{inti,j;intn=16;intsw,sv;for(i=0;i<16;i++){ sw=0; sv=0; for(j=0;j<4;j++) { sw=sw+wp[j].w*a[i][j]; sv=sv+wp[j].v*a[i][j];} if(sw<=c) cw[i]=sv; else cw[i]=0;}在可行解中找出最优解,即找出可行解中满足目标函数的最优解。以下是找出最优解的算法:intfindmax(intx[16][4],intcv[])//可行解保存在数组cv中,最优解就是x数组中某行的元素值相加得到的最大值{ intmax; inti,j; max=0; for(i=0;i<16;i++) {if(cv[i]>max) {max=cv[i]; j=i; } } printf("\n最好的组合方案是:"); for(i=0;i<4;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)的