当前位置:首页 >> IT/计算机 >>

回溯法解0-1背包问题实验报告


实验 4
一 、实验要求

回溯法解 0-1 背包问题

1.要求用回溯法求解 0-1 背包问题; 2.要求交互输入背包容量,物品重量数组,物品价值数组; 3.要求显示结果。

实验仪器和软件 软件平台 二 、实验仪器和软件平台
仪器 :带 usb 接口微机 软件平台:WIN-XP + VC++6.0

三 、实验源码
#include "stdafx.h" #include<iostream> #include<cstdio> #include<conio.h> #include<iomanip> using namespace std; template<class ty> class Knap { public: friend void Init(); friend void Knapsack(); friend void Backtrack(int i); friend float Bound(int i); bool operator<(Knap<ty> a)const { if(fl<a.fl) return true; else return false; } private: ty w; //重量 ty v; //价值 float fl; //单位重量的价值 v/w int kk; //记录第几个物品 int flag; //记录是否放入包中 }; template<class ty> void Sort(Knap<ty> *li,int n) {

int i,j,k; Knap<ty> minl; for(i=1;i<n;i++) { minl=li[0]; k=0; for(j=1;j<=n-i;j++) { if(minl<li[j]) { minl=li[j]; swap(li[j],li[k]); } } }

k=j;

} namespace jie //命名空间 { int c=0,n=0; int *x=NULL; Knap<int> *bag=NULL; int cp=0,cw=0; int bestp=0; } using namespace jie; void Init() { int i=0; cout<<endl; cout<<"请输入物品数量 n = "; cin>>n; cout<<endl; cout<<"请输入背包容量 C = "; cin>>c; cout<<endl; bag=new Knap<int> [n]; x=new int[n]; cout<<"请依次输入"<<n<<"个物品的重量 W:"<<endl; for(i=0;i<n;i++) cin>>bag[i].w; cout<<endl; cout<<"请依次输入"<<n<<"个物品的价值 P:"<<endl; for(i=0;i<n;i++) cin>>bag[i].v; for(i=0;i<n;i++) { bag[i].flag=0; bag[i].kk=i; bag[i].fl=1.0*bag[i].v/bag[i].w; } }

void Backtrack(int i) { if(i>=n) //到达叶节点 { bestp=cp; //更新最优价值 return; } if(cw+bag[i].w<=c) //进入左子树 { bag[i].flag=1; cw+=bag[i].w; cp+=bag[i].v; Backtrack(i+1); cw-=bag[i].w; cp-=bag[i].v; } if(Bound(i+1)>bestp)//进入右子树 { bag[i].flag=0; Backtrack(i+1); } } //计算当前节点处的上界 float Bound(int i) { int cleft = c-cw; //剩余容量 float b = cp; while (i<n&&bag[i].w<=cleft) { //以物品单位重量价值递减序装入 cleft-=bag[i].w ; b+=bag[i].v; i++; } //装满背包 if (i<n) b+=1.0*bag[i].v/bag[i].w * cleft; return b; } void Knapsack() //计算最优解和变量值 { int L(0); //用 L 累计价值,初始价值设置为 0 for(int k=0;k<n;k++) { x[bag[k].kk]=bag[k].flag; //x=0 表示未放入背包,x=1 表示放入背包 L+=bag[k].flag*bag[k].v; //价值累加 } cout<<endl; cout<<"当前最优价值为:"<<L<<endl; cout<<"变量值 x = ";

for(int i=1;i<=n;i++) { cout<<x[i-1]; } delete []bag; bag=NULL; delete []x; x=NULL; cout<<endl; getch(); } int main() { cout<<endl; cout<<"|**********回溯法解 0-1 背包问题**********|"<<endl; Init(); Backtrack(0); Knapsack(); return 0; }

四 、运行结果

实验小结 五 、实验小结
通过该实验,我充分了解了回溯法与分支界限法的区别。回溯法在问题的解 空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树 的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该 结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深 度优先策略搜索。


相关文章:
回溯法实验(0-1背包问题).doc
回溯法实验(0-1背包问题) - 算法分析与设计实验报告 第五 次附加实验 姓名 时间 实验名称 12.26 上午 学号 地点 班级 工训楼 309 回溯法实验(0-1 背包...
回溯法解0-1背包问题实验报告.doc
回溯法解0-1背包问题实验报告_IT/计算机_专业资料。用回溯法算法来解0-1背
用回溯法解决0-1背包问题.doc
标签: 回溯法| 背包| 用回溯法解决0-1背包问题_工学_高等教育_教育专区。算法试验报告,用回溯法解决0-1背包问题 #include<stdio.h> int c; //背包容量 ...
回溯法求0-1背包问题.doc
回溯法求0-1背包问题 - 《算法设计与分析》实验报告 学日号: 期: 姓得名: 分: 一、实验内容: 用回溯法求解 0/1 背包问题 注:给定 n 种物品和一个容量...
动态规划与回溯法解决0-1背包问题.doc
动态规划与回溯法解决0-1背包问题 - 0-1 背包动态规划解决问题 一、问题描
动态规划解决算法0-1背包问题实验报告(含源代码).doc
动态规划解决算法0-1背包问题实验报告(含源代码) - 1.设计一个O(n^2)
分支界限法解0-1背包问题实验报告.doc
分支界限法解0-1背包问题实验报告_数学_自然科学_专业资料。实验 5 一 、实验...(); return 0; } 四 、运行结果 五 、实验小结回溯法的求解目标是找出解...
实验3._回溯法的应用-0-1背包等问题.doc
实验3._回溯法的应用-0-1背包等问题 - 实验 4. 回溯法的应用- 0-1 背包问题 实验内容 本实验要求基于算法设计与分析的一般过程(即待求解问题的描述、算法...
回溯法-0-1背包问题.doc
回溯法-0-1背包问题 - 1、 问题描述 一、0-1 背包问题 给定一组物品,
回溯法、分支限界法解0-1背包问题(计算机算法设计与分....doc
回溯法、分支限界法解0-1背包问题(计算机算法设计与分析实验报告) - 报告中附
最新动态规划解决算法0-1背包问题实验报告(含源代码).doc
最新动态规划解决算法0-1背包问题实验报告(含源代码)_计算机软件及应用_IT...使用动态规划法和回溯法生成两个长字符串的最优化比对结果通过实际 案例,领会...
回溯法实验0 1背包问题 C++.doc
回溯法实验0 1背包问题 C++ - #include <iostream
回溯法在0_1背包问题中的应用.pdf
回溯法0_1背包问题中的应用 - 第 7 卷 % 第 12 期 软件导刊 2008年 12 月 Software Guide Vol.7 No.12 Dec. 2008 回溯法...
回溯法解决01背包问题.doc
回溯法解决01背包问题 - 回溯法是个既带有系统性又带有跳跃性的搜索算法。 它
回溯法01背包问题_图文.ppt
回溯法解决01背包问题 ? 问题举例最优值上界 ? 对于0-1背包问题回溯法的一个...实验报告 回溯法01背包 5页 1下载券 蛮力法、动态规划法、回... 12页 ...
回溯法解决符号三角形与0-1背包问题.doc
宁夏师范学院数学与计算机科学学院 《算法分析与设计》实验报告实验序号:9 学号姓 实验项目名称:回溯法解决符号三角形与 0-1 背包问题 名 专业、班时间 2014.06....
0-1背包问题(回溯法).doc
0-1背包问题(回溯法) - 0-1 背包问题(回溯法) 实验报告 姓 名: 学 号: 指导老师: 一.算法设计名称: 0-1 背包问题(回溯法) 二.实验内容 问题描述: ...
回溯法解决01背包问题_图文.ppt
实验报告 回溯法01背包 5页 1下载券 0-1背包问题的解决(回溯... 7页 免费 回溯法 背包问题 12页 1下载券 回溯法解0-1背包问题 3页 免费 回溯法...
回溯法和分支限界法解决0-1背包题.doc
∑ wi xi≤c,且∑ vi xi 达最大.即一个特殊的整数规划问题。 二、回溯法步骤思想描述: 0-1 背包问题是子集选取问题。0-1 背包问题的解空间可以用子集树...
算法0-1背包问题.doc
算法0-1背包问题 - 掌握回溯法、分支限界法的原理,并能够按其原理编程实现解决0-1背包问题,以加深对回溯法、分支限界法的理解。 1. 要求分别用回溯法和分支...
更多相关标签: