实验5分支限界.docxVIP

《算法设计与分析》实验报告实验5 分支限界算法姓名 学号 班级网络131实验日期2016.11.29 实验地点学院305一、实验目的：掌握分支限界算法的设计思想与设计方法。二、实验环境1、硬件环境CPU：2.0GHz 内存：4GB 硬盘：100GB2、软件环境操作系统：win7编程环境：devc++编程语言：c三、实验内容1、问题有一个背包，最大限重为C，有n个物品，重量分别为W=w1, w2, …, wn，价值分别为V=v1, v2, …, vn要求使用分支限界算法找出一个装载方案，使得放入背包物品的价值之和最大。输出装载方案和该方案下的背包所装物品总重量及总价值。2、数据结构（1）解的结构typedef struct treenode（2）有哪些信誉好的足球投注网站空间的结构 int bbfifoknap(int w[],int v[],int n,int c,int* bestValue)3、算法伪代码PackSolu(G, n, C) 输入： G[]存储物品的数据结构,n表示物品个数，C表示背包容量 输出：一个用来存储各个物品装入数目的数组 1. Sort(G) // 将物品从大到小排序 2. v-0; w-0; i-0; // v表示装入背包的总值，w表示装入背包的总重，i表示物品的索引 3. while i n do 4. if 背包可装下j个第i种物品 5. then v-(v+G[i].v)；w-(w+G[i].w)；solu[i] = 1; 6. else solu[i] = 0; 7. if v 界的值best_v then 更新最优解 8. while solu[i] = 0 and i 0 do i--; // 回溯到上一个装入的物品 9. if solu[i] 0 then solu[i] = 0;w-(w-G[i].w);v-(v-G[i].v);i++ 10. if i 0 then goto 3 4、算法分析时间复杂度：O(2^n)空间复杂度：O(n)5、关键代码（含注释）#includeiostream#includequeueusing namespace std;typedef struct treenode{ int weight; int value; int level; int flag;}treenode;queuestruct treenode que;int enQueue(int w,int v,int level,int flag,int n,int* bestvalue){ treenode node; node.weight = w; node.value = v; node.level = level; node.flag = flag; if (level == n) { if (node.value *bestvalue) { *bestvalue = node.value; } return 0; }else { que.push(node); }}//w为重量数组，v为价值数组，n为物品个数，c为背包容量，bestValue为全局最大价值int bbfifoknap(int w[],int v[],int n,int c,int* bestValue){ //初始化结点 int i=1; treenode tag, livenode; livenode.weight = 0; livenode.value = 0; livenode.level = 1; livenode.flag = 0;//初始为0 tag.weight = -1; tag.value = 0; tag.level = 0; tag.flag = 0;//初始为0 que.push(tag); while (1) { if (livenode.weight + w[i - 1] = c) { enQueue(livenode.weight + w[i - 1], livenode.value + v[i - 1], i, 1,n,bestValue); } enQueue(livenode.weight,livenode.value, i, 0,n,bestValue); livenode = que.front(