《蛮力法、动归、贪心、分支限界法解01背包问题》由会员分享，可在线阅读，更多相关《蛮力法、动归、贪心、分支限界法解01背包问题（29页珍藏版）》请在金锄头文库上搜索。
1、算法综合实验报告学 号： 1004121206 姓 名： 林 一、实验内容：分别用蛮力、动态规划、贪心及分支限界法实现对0-1背包问题的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。二、程序设计的基本思想、原理和算法描述：1、 蛮力法 1.1数据结构注：结构体obj用来存放单个物品的价值和重量 typedef struct obj int w;/物品的重量 int v;/物品的价值 ; 1.2 函数组成 void subset(int s10,int n)：用来生成子集的函数 void judge(int s10, obj obj,int mark,int n,int
2、c)：判断子集的可行性 int getmax(int mark,int n,int &flag)：求解问题的最优解 void outputObj(int flag,int s10,int n):输出选择物品的情况 1.3 输入/输出设计 本程序通过键盘进行输入、屏幕进行输出。 1.4 符号名说明 符号 说明 S 存放子集 mark 记录子集的可行性 n 物品的个数 c 物品的容量 max 记录背包所能产生的最大价值 flag 记录能产生最大价值的子集的编号 1.5 算法描述 算法的伪代码描述如下： 输入：背包的容量c,物品的个数n,n个物品的重量 wn,价值vn 输出：装入背包的物品编号以及产
3、生的最大价值 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如果maxc） 4.1 将第i个物品放入背包,objecti.Num=1； 4.2 c-=pron.Weight； 4.3 i+；5. 记录最后放入背包的物品的重量： objecti.Num=(double)C/objecti.Weight；4、 分支限界法 4.1数据结构 注：物品结
4、构体，存放物品价值、重量、单位价值、物品编号等信息 struct obj int v;/物品价值 int w;/物品重量 double avg;/物品单位价值 int id;/物品编号 ; 注：结构体node用来存放节点表节点 struct node node *parent,/父亲结点指针 *next;/后继结点指针 int level,/节点所处的层 isin,/记录物品是否装入背包，0代表不装,1代表装入 cw,/当前背包已经装入的物品重量 cv;/当前背包已经装入的物品价值 double ub;/结点的上界值 ; 4.2函数组成 int Partition(_Object r,int
5、first,int end)；以数组第一个元素为准对数组进行一次划分并返回基准元素的位置坐标 void QuickSort(_Object r,int first,int end)；快速排序 double Upb(int i,int cw,int cv);/计算上界值 node *nnoder(node * parent1,int isin1,double ub1);生成一个新的结点 void addnode(node *node1);/将结点添加到队列中 node *nextnode(); /取下一个结点 void fenzjx();/分支界限法的主要实现函数 void output();/
6、用于输出物品的选择情况及最优解4.3 输入/输出设计 本程序通过键盘进行输入、屏幕进行输出。 4.4 符号名说明 符号 说明 c 背包的容量 n 物品的个数 pro 存放物品信息 avg 物品的单位价值量 opv 背包容量最优解 popv 指向最优解的指针 level 节点的层 cw 当前背包装载量 cv 当前背包价值 ub 节点的上界值 isin 记录当前结点物品是否放入背包 flag 物品原来位置(4) 算法描述 算法的伪代码描述如下： 输入：背包的容量c,物品的个数n,n个物品的信息 pron 输出：装入背包的物品标号和背包获得的最大价值 1.对输入的物品按照单位价值量递减的顺序进行排序
7、 2.初始化问题最优解opv=0,初始化第0层结点，计算上界值 ub=Upb(0,0,0);并设置该结点设为优先级队列的根结点 3.循环直到优先级队列为空 3.1 如果取出当前结点位于第n-1层，则其子结点已是叶子结点，判断子结点取值情况，若得到的解大于当前问题得到的最优解opv，则重置问题的最优解opv 3.2 如果取出当前结点层 level n-1 对结点i的每个孩子结点x执行下列操作: 3.2.1 如果结点x可能产生的最优解ubopv，则丢弃该结点; 3.2.2 否则估算该节点x的目标函数值ub,将结点加入队列; 4.将该结点对应的最优值输出，回溯求得最优解的各个分量三、源程序及注释：1、蛮力法#include#includeusing namespace std;/物品typedef struct objint w;int v;
