蛮力法动归贪心分支限界法解01背包问题.docx

算法综合实验报告
学号：1004121206姓名：林
一、实验内容：
分别用蛮力、动态规划、贪心及分支限界法实现对0-1背包问题的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。
二、程序设计的基本思想、原理和算法描述：
蛮力法
1.1数据结构
注：结构体obj用来存放单个物品的价值和重量
typedefstructobj
{
intw;//物品的重量
intv;//物品的价值
};
1.2函数组成
voidsubset(ints[][10],intn)：用来生成子集的函数
voidjudge(ints[][10],objobj[],intmark[],intn,intc)：判断子集的可行性
intgetmax(intmark[],intn,int&flag)：求解问题的最优解
voidoutputObj(intflag,ints[][10],intn):输出选择物品的情况
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+wj<c,则w=w+wj,v=v+vj;
2.2.2否则，转步骤2考察下一个子集；
2.3如果max<v,则max=v;s=t;
3.输出子集S中的各元素
动态规划法
2.1数据结构
该程序不涉及任何数据结构
2.2函数组成
intmax(inti,intj);比较并返回两个数中的较大值
intKnapSack(intw[],intv[],intx[],intn,intc);求解背包取得的最大值
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数据结构
注：结构体用来存放物品的重量、价值、单位价值、物品编号等信息
struct_Object
{
intValue;//物品价值
intWeight;//物品重量
doubleAveValue;//物品单位价值
doubleNum;//物品可以放入的数量
intkey;//物品标号
};
3.2函数组成
intPartition(_Objectr[],intfirst,intend)；以数组第一个元素为准对数组进行一次划分并返回基准元素的位置坐标
voidQuickSort(_Objectr[],intfirst,intend)；快速排序
doubleknaspsack(intn,intM,_Objectobject[])；求解背包问题的最优解
3.3输入/输出设计
本程序通过键盘进行输入、屏幕进行输出。
3.4符号名说明
符号说明n物品的个数c物品的容量pro[]物品的重量、价值、单位价值、编号
3.5算法描述
算法的伪代码描述如下：
输入：背包的容量c,物品的个数n,n个物品的重量pro[n].Weight,价值pro[n].Value
输出：装入背包的物品标号和背包获得的最大价值
计算物品的单位价值并存入pro[n].
将物品按照单位价值递减的顺序进行排序
i=0;
循环直到（object[i].Weight>c）
4.1将第i个物品放入背包,object[i].Num=1；
4.2c-=pro[n].Weight；
4.3i++；
记录最后放入背包的物品的重量：
object[i].Num=(double)C/object[i].W