实验项目三 用蛮力法动态规划法和贪心法求解背包问题.doc

实验项目三 用蛮力法、动态规划法和贪心法求解0/1背包问题 实验目的 1、学会背包的数据结构的设计，针对不同的问题涉及到的对象的数据结构的设计也不同； 2、对0-1背包问题的算法设计策略对比与分析。 实验内容： 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)。 背包的数据结构的设计： typedef struct object { int n;//物品的编号 int w;//物品的重量 int v;//物品的价值 }wup; wup wp[N];//物品的数组，N为物品的个数 int c;//背包的总重量 1、蛮力法 蛮力法是一种简单直接的解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。蛮力法的关键是依次处理所有的元素。 用蛮力法解决0/1背包问题，需要考虑给定n个物品集合的所有子集，找出所有可能的子集（总重量不超过背包容量的子集），计算每个子集的总价值，然后在他们中找到价值最大的子集。 所以蛮力法解0/1背包问题的关键是如何求n个物品集合的所有子集，n个物品的子集有2的n次方个，用一个2的n次方行n列的数组保存生成的子集，以下是生成子集的算法： void force(int a[16][4])//蛮力法产生4个物品的子集 { int i,j; int n=16; int m,t; for(i=0;i16;i++) { 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); } ｝ 以下要依次判断每个子集的可行性，找出可行解: void panduan(int a[][4],int cw[])////判断每个子集的可行性，如果可行则计算其价值存入数组cw,不可行则存入0 { int i,j; int n=16; int sw,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; else cw[i]=0; } 在可行解中找出最优解，即找出可行解中满足目标函数的最优解。以下是找出最优解的算法： int findmax(int x[16][4],int cv[])//可行解保存在数组cv中，最优解就是x数组中某行的元素值相加得到的最大值 { int max; int i,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]); } return max; } 。 2、动态规划法 动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。 动态规划法设计算法一般分成三个阶段： （1）分段：将原问题分解为若干个相互重叠的子问题； （2）分析：分析问题是否满足最优性原理，找出动态规划函数的递推式； （3）求解：利用递推式自底向上计算，实现动态规划过程。 0/1背包问题可以看作是决策一个序列(x1, x2, …, xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策