蛮力法、动归、贪心、分支限界法解01背包问题剖析.doc

算法综合实验报告 学 号： 1004121206 姓 名： 林 一、实验内容： 分别用蛮力、动态规划、贪心及分支限界法实现对0-1背包问题的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。 二、程序设计的基本思想、原理和算法描述： 蛮力法 1.1数据结构 注：结构体obj用来存放单个物品的价值和重量 typedef struct obj { int w;//物品的重量 int v;//物品的价值 }; 1.2 函数组成 void subset(int s[][10],int n)：用来生成子集的函数 void judge(int s[][10], obj obj[],int mark[],int n,int c)：判断子集的可行性 int getmax(int mark[],int n,int flag)：求解问题的最优解 void outputObj(int flag,int s[][10],int n):输出选择物品的情况 1.3 输入/输出设计 本程序通过键盘进行输入、屏幕进行输出。 1.4 符号名说明 符号 说明 S[][] 存放子集 mark[] 记录子集的可行性 n 物品的个数 c 物品的容量 max 记录背包所能产生的最大价值 flag 记录能产生最大价值的子集的编号 1.5 算法描述 算法的伪代码描述如下： 输入：背包的容量c,物品的个数n,n个物品的重量 w[n],价值v[n] 输出：装入背包的物品编号以及产生的最大价值 1.初始化最大价值 max=0,结果子集 s=φ; 2.对集合{1,2,......n}的每一个子集T，执行下述操作： 2.1初始化背包的价值 v=0，背包的重量 w=0; 2.2对子集t的每一个元素j 2.2.1 如果w+wjc,则 w=w+wj,v=v+vj; 2.2.2 否则，转步骤2考察下一个子集； 2.3如果maxv,则 max=v;s=t; 3.输出子集S中的各元素 动态规划法 2.1 数据结构 该程序不涉及任何数据结构 2.2 函数组成 int max(int i,int j);比较并返回两个数中的较大值 int KnapSack (int w[],int v[],int x[],int n,int c);求解背包取得的最大值 2.3 输入/输出设计 本程序通过键盘进行输入、屏幕进行输出。 2.4 符号名说明 符号 说明 n 物品的个数 c 物品的容量 w[] 物品的重量 v[] 物品的价值 x[] 物品的选择情况 V[][] 存放迭代结果 2.5 算法描述 算法的伪代码描述如下： 输入：背包的容量c,物品的个数n,n个物品的重量 w[n],价值v[n] 输出：装入背包的物品标号和背包获得的最大价值 1.初始化二维数组V[][]={0} 2.初始化二维数组的第0行，第0列 2.循环直到i==n 2.1 循环直到j=c 2.1.1 如果背包的容量不足以装入物品i,则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值相等 2.2.2 如果背包的容量可以装入物品i,分别计算装入物品i可达到的价值量V[i-1][j-w[i]]+v[i],以及不放入物品i可以得到的最大价值V[i-1][j]，取二者中的较大者作为把前i个物品装入容量为j的背包中的最优解 贪心法 3.1数据结构 注：结构体用来存放物品的重量、