用蛮力法、动态规划法和贪心法求解0-1背包问题

1、实验项目三 用蛮力法、 动态规划法和贪心法求解 0/1背包问题实验目的1、学会背包的数据结构的设计，针对不同的问题涉及到的对象的数据结构的设计也不 同；2、对0-1 背包问题的算法设计策略对比与分析。实验内容：0/1背包问题是给定n个重量为w1, w2,wn、价值为v1, v2,，丫门的物品和一个容量为 C 的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。在 0/1 背包问题中，物品 i 或者被装入背包，或者不被装入背包，设xi 表示物品 i 装入背包的情况，则当 xi=0 时，表示物品 i 没有被装入背包， xi=1 时，表示物品 i 被装入背包。 根据问题的要求，有如下约束

2、条件和目标函数：（式1 ）（式2 ）1 ，并使目标函数式2 达到最大的解向量n wixi C i1xi 0,1 （1 i n） n max vi xi i1 于是，问题归结为寻找一个满足约束条件式 X=（x1, x2,x n）。背包的数据结构的设计：typedef struct object int n;/ 物品的编号 int w;/ 物品的重量 int v;/ 物品的价值 wup;wup wpN;/ 物品的数组， N 为物品的个数 int c;背包的总重量1、蛮力法蛮力法是一种简单直接的解决问题的方法， 常常直接基于问题的描述和所涉及的概念定义。蛮力法的关键是依次处理所有的元素。用蛮力法解决

3、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;

4、 for(i=0;i<16;i+)/ 输出保存子集的二维数组 for(j=0;j<4;j+) printf("%d ",aij); printf("n");以下要依次判断每个子集的可行性，找出可行解:void panduan(int a4,int cw)/ 判断每个子集的可行性，如果可行则计算其价值存入 数组cw,不可行则存入0int 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;i

5、f(sw<=c)cwi=sv;elsecwi=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、动态规划法

6、动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段， 一般来说， 子问题的重叠关系表现在对给定问题求解的递推关系 (也就是动态规划函数) 中， 将子问题的解求解一次并填入表中，当需要再次求解此子问题时， 可以通过 查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。动态规划法设计算法一般分成三个阶段：( 1)分段：将原问题分解为若干个相互重叠的子问题；( 2)分析：分析问题是否满足最优性原理，找出动态规划函数的递推式；( 3)求解：利用递推式自底向上计算，实现动态规划过程。0/1背包问题可以看作是决策一个序列(x1, x2,xn),对任一变量xi的决策

7、是决定xi=1还是xi=0。在对xi-1决策后，已确定了 (x1,xi-1),在决策xi时，问题处于下列两种状态 之一：( 1)背包容量不足以装入物品i ，则 xi=0 ，背包不增加价值；(2)背包容量可以装入物品i,则xi=1,背包的价值增加了vi。这两种情况下背包价值的最大者应该是对xi决策后的背包价值。令V(i, j)表示在前i(1wiwn）个物品中能够装入容量为j （iwjwc）的背包中的物品的最大值，则可以得到如下动态规划函数：V（i, 0）= V（0, j）=0 （式 3）V(i 1, j ) j wi(式 4)V(i, j)imaxV(i 1, j ), V(i 1, j wi

8、) vi j wi式 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 个

9、物品装入容量为 j 的背包中所取得的价值。显然，取二者中价值较大者作为把前i 个物品装入容量为j 的背包中的最优解。以下是动态规划法求解背包问题的算法：int巾ndmaxvalue(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;

10、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 开始 elsexi-1=0;maxvalue=valueNC;/ 最大值 return maxvalue;3、贪心法贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出

11、选择，而且一旦做出了选择， 不管将来有什么结果，这个选择都不会改变。 换言之， 贪心法并不是从整体 最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解（ Optimal Solution ） ，但通常能获得近 似最优解（ Near-Optimal Solution ） 。 贪心法求解的问题的特征：（ 1）最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。（ 2）贪心选择性质所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。用贪心法求解问题应该考虑如下几个方面：（

12、 1）候选集合C ：为了构造问题的解决方案，有一个候选集合C 作为问题的可能解，即问题的最终解均取自于候选集合C。 例如， 在付款问题中， 各种面值的货币构成候选集合。（ 2）解集合S:随着贪心选择的进行，解集合 S不断扩展，直到构成一个满足问题的 完整解。例如，在付款问题中，已付出的货币构成解集合。（ 3）解决函数solution ：检查解集合 S 是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。（ 4）选择函数 select:即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。 例如， 在付款问题中，贪心策略

13、就是在候 选集合中选择面值最大的货币。（ 5） 可行函数 feasible ： 检查解集合中加入一个候选对象是否可行， 即解集合扩展后是否满足约束条件。 例如， 在付款问题中， 可行函数是每一步选择的货币和已付出的货币相加 不超过应付款。背包问题至少有三种看似合理的贪心策略：（ 1）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长， 但背包容量却可能消耗得太快， 使得装入背包的 物品个数减少，从而不能保证目标函数达到最大。（ 2）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。 但是， 虽然每一步选择使背包的容量消耗

14、得慢了， 但背包的价值却没能保证迅速增长， 从而不能保证目标函数达到最大。（ 3 ）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。应用第三种贪心策略，每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量， 就可以把它装入， 并将背包容量减去该物品的重量， 然后我们就面临了一个最优子问题 它同样是背包问题， 只不过背包容量减少了， 物品集合减少了。 因此背包问 题具有最优子结构性质。先按单位重量价值最大对物品进行排序。然后再用贪心策略选择的算法如下：float find（float pN,float wN,float xN ,float M,int n）

15、 /* 先放单位价值量大的物体，再考虑小的物体*/int i;float maxprice;for (i = 0; i < n; i+)xi = 0;1 = 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;#include<stdio.h>#include&l

16、t;stdlib.h>#include<string.h>#define C 10/定义背包总重量为10#define N 4/ 定义物品个数为 4typedef struct object/ 背包的数据结构的设计int n;/ 物品的编号int w;/ 物品的重量int v;/ 物品的价值wup;wup wpN;/ 物品的数组， N 为物品的个数void inputwp(wup *p)/ 输入函数int i;/i 为物品的个数for (i=0;i<N;i+)/for 循环物品的个数，总的物品有N 个printf("n 请输入第 %d 个物品的编号、重量、价值

17、",i);scanf("%d",&p->n);/ 输入物品的编号 scanf("%d",&p->w);/ 输入物品的重量 scanf("%d",&p->v);/ 输入物品的价值 p=p+1;/p 为一个指针，指向下一个物品printf("n");/ 输出结果void ontputwp(wup *p)/ 输出函数int i;/i 为物品的个数for (i=0;i<N;i+)/for 循环物品的个数，总的物品有N 个printf("n 请输出第 %d

18、个物品的编号、重量、价值",i);printf("%d %d %d",p->n,p->w,p->v);/* 把物品的编号、重量、价值和起来输出给 i 个物品 */p=p+1;/ 指针指向下一个物品printf("n");/ 输出结果float find(float yN,float wN,float xN ,float M,int n) /* 先放单位价值量大的物体，再考虑小的物体*/int i;float maxprice;for (i = 0; i < n; i+)xi = 0;2 = 0;maxprice=0;while (i < n && wi < M)M=M-wi;xi =wi; /* 表示放入数量*/maxprice=maxprice+yi;xn-1=M;i+;if (i < n &&M> 0)maxprice=maxprice+yi*xi/wi; i+;return maxprice;void main()wup *p;/ 这是一个 wup 型的指针 pfloat yN;float wN;float xN;float M;int n;int i;float maxprice;printf