当前位置:首页 >> 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背包问题的解决(回溯法)
0-1背包问题的解决(回溯法)_解决方案_计划/解决方案_实用文档。算法设计分析,...回溯法解0-1背包问题实验... 4页 2下载券 回溯法解决符号三角形与... ...
0-1背包问题(回溯法)
0-1背包问题(回溯法) - 0-1 背包问题(回溯法) 实验报告 姓 名: 学 号: 指导老师: 一.算法设计名称: 0-1 背包问题(回溯法) 二.实验内容 问题描述: ...
回溯法和分支限界法解决0-1背包题(精)
0-1 背包问题 计科 1 班 朱润华 2012040732 方法 1:回溯法 一、回溯法描述: 用回溯法解问题时,应明确定义问题的解空间。问题的解空间至少包含问题的一 个(...
回溯法解决01背包问题
回溯法解决01背包问题 - 回溯法个既带有系统性又带有跳跃性的搜索算法。 它在包含问题的所有解的解空间树中按照 深度优先的策略,从根节点出发搜索解空间树。...
回溯法实验0 1背包问题 C++
回溯法实验0 1背包问题 C++ - #include &lt;iostream.h&gt; #include&lt;iomanip.h&gt; #include&lt;string.h&gt; int min(int w,int...
0-1背包问题(回溯法)
0-1背包问题(回溯法)_IT/计算机_专业资料。利用回溯法解决0-1背包问题的思想及关键代码。 二、实习过程 : 1、 解空间:用回溯法解问题时,应明确定义问题的解...
回溯法和分支限界法解决0-1背包题
0-1 背包问题计科 1 班 朱润华 2012040732 方法 1:回溯法 一、回溯法描述: 用回溯法解问题时,应明确定义问题的解空间。问题的解空间至少包含问题的一个(最...
回溯法求0-1背包问题
回溯法0-1背包问题 - 回溯法求 0-1 问题 1 题目分析与算法构造 0-1 背包问题: 给定 n 种物品和一个背包。 物品 i 的重量是 Wi, 其价值为 Vi, ...
算法分析与程序设计动态规划及回溯法解01背包问题...
算法分析与程序设计动态规划及回溯法解01背包问题 - 动态规划法、回溯法解 0-1 背包问题 2012 级 计科 庞佳奇 一、 1. 问题描述与分析 动态规划算法通常用于...
回溯法求01背包问题
回溯法求01背包问题 - 实验题目 给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值 为 vi,0/1 背包问题是如何选择装入背包的物品(物品不可...
更多相关标签: