计算机算法设计与分析(第三版)王晓东编著,第五章回溯法算法源代码 01背包问题,装载问题递归回溯,装载问题跌代回溯,批处理作业调度问题,符号三角形问题,n后问题的递归算法,n后问题的跌代算法,0-1背包问题递归回溯算法,0-1背包问题跌代回溯算法,最大团回溯算法,图的m着色问题 ,旅行售货员问题
// 递归回溯算法--01背包问题
#include <iostream.h>
#include <iomanip.h>
const int n=3; //物品个数
int w[n]={16,15,15}, v[n]={45,25,25}, c=30;
int cv=0, bestv=0, bestx[n]={0}, x[n]={0}, cw=0, rv;
void Backtrack(int t)
{
if (t+1>n)
{
if (cv>bestv)
{
bestv=cv;
for (int j=0; j<n; j++) bestx[j]=x[j];
}
return;
}
// 搜索子树
rv-=v[t];
// 搜索左子树
if (cw+w[t]<=c)
{
x[t]=1;
cw+=w[t];
cv+=v[t];
Backtrack(t+1);
cw-=w[t];
cv-=v[t];
}
// 搜索右子树
if (cv+rv>bestv)
{
x[t]=0;
Backtrack(t+1);
}
rv+=v[t];
}
void main()
{
cout<<"\n W :";
for (int i=0; i<n; i++) cout<<setw(4)<<w[i];
cout<<"\n V :";
rv=0;
for (i=0; i<n; i++)
{
rv+=v[i];
cout<<setw(4)<<v[i];
}
Backtrack(0);
cout<<"\n\n X:";
for (i=0; i<n; i++) cout<<setw(4)<<x[i];
cout<<"\n\n";
}
// 装载问题递归回溯
#include <iostream.h>
#include <iomanip.h>
const int n=5; //集装箱数
template <class Type>
class Loading
{
friend MaxLoading(Type [], Type, Type, int []);
private:
void Backtrack(int i);
int *x, //当前解
*bestx; // 当前最优解
Type *w, // 集装箱重量
c1, // 第一艘船的载重量
c2, // 第二艘船的载重量
cw, // 当前装载的重量
bestw, // 当前最优装载重量
r; // 剩余集装箱的重量
};
// 搜索第t层结点
template <class Type>
void Loading <Type>::Backtrack(int t)
{
// 到达叶结点
if (t+1>n)
{
if (cw>bestw)
{
bestw=cw;
for (int j=0; j<n; j++) bestx[j]=x[j];
}
return;
}
// 搜索子树
r-=w[t];
if (cw+w[t]<=c1)
{
// 搜索左子树
x[t]=1;
cw+=w[t];
Backtrack(t+1);
cw-=w[t];
}
if (cw+r>bestw)
{
// 搜索右子树
x[t]=0;
Backtrack(t+1);
}
r+=w[t];
} // 算法时间复杂度为O(2^n)
template <class Type>
Type MaxLoading(Type w[], Type c1, Type c2, int bestx[])
{
Loading <Type> X;
// 初始化X
X.x=new int [n];
X.w=w;
X.c1=c1;
X.c2=c2;
X.bestx=bestx;
X.bestw=0;
X.cw=0;
X.r=0;
for (int i=0; i<n; i++) X.r+=w[i];
X.Backtrack(0); // 从根结点开始搜索
delete [] X.x;
return X.bestw; // 返回最优装载重量
}
void main()
{
int w[]={10,40,20,50,30}, c1=80, c2=70, x[n]={0};
cout<<"\n n = "<<n<<"\n\n c1 = "<<c1<<"\n\n c2 = "<<c2<<"\n\n W :";
for (int i=0; i<n; i++) cout<<setw(4)<<w[i];
cout<<"\n\n BestW = "<<MaxLoading(w,c1,c2,x);
cout<<"\n\n X1:";
for (i=0,c1=0; i<n; i++)
{
cout<<setw(4)<<x[i];
if (!x[i]) c1+=w[i];
}
if (c1>c2) cout<<"\n\n No Solusion (c2="<<c1<<")";
else
{
cout<<"\n\n X2:";
for (i=0; i<n; i++) cout<<setw(4)<<(x[i]?0:1);
}
cout<<"\n\n";
}
// 装载问题跌代回溯
#include <iostream.h>
const int n=5;
void main()
{
int C=65, W[n]={10,22,40,15,31};
int j=0; //已装上轮船的集装箱数
int x[n]={0}; //装上轮船的集装箱号
int m[n]={0}; //
第5章 回溯法 1 引言 ?相信大家都走过迷宫或者玩过走迷宫的游戏吧,在 走迷宫的过程中,我们从入口出发,到达路口后, 选择一条岔路进入,到达下一个路口,然后再选...
算法设计与分析 回溯法第5章 回溯法 ? 学习要点 ? 理解回溯法的深度优先搜索策略 ? 掌握用回溯法解题的算法框架 ? ...
第五章 回溯法_IT/计算机_专业资料。回溯法 1 ? ? 1 回溯法及基本思想 2 回溯法应用 例8.1 八皇后问题 ? a盲目的枚举算法 ? b加约束的枚举算法 ? c递...
第5章 回溯法 清华大学出版社 1 ? ? ? 学习要点理解回溯法的深度优先搜索策略 掌握用回溯法解题的算法框架 ? ? (1)递归回溯(2)迭代回溯 ? ? (3)子集树...
第5章 回溯法 回溯法的应用步骤 1、针对所给问题,定义问题的解空间; 2、确定易于搜索的解空间结构; 3、以深度优先的方式搜索解空间,并且在搜索过程中用剪枝 ...
第5章 回溯法 通过应用范例学习回溯法的设计策略(1)装载问题; (2)批处理作业调度; (3)符号三角形问题 (4)n后问题; (5)0-1背包问题; (6)最大团问题; ...
第五章 ? 教学目标 ?掌握回溯法的算法框架 ?理解回溯法的基本思想 回溯法 ?掌握回溯法及分支限界法的异同 ?掌握子集树、排列树及满m叉树的算法设计模式 ?通过...
第5章 回溯法 迷宫问题 7月7日,世界上最大的玉米迷宫在大连金州区登沙河镇正式对外营业, 除了300多亩的“勇者之旅”玉米迷宫,还将娱乐、休闲、拓展、农 村...
第5章 回溯法_理学_高等教育_教育专区。第5章 回溯法 1 ? 学习要点 ? 理解回溯法的深度优先搜索策略。 ? 掌握用回溯法解题的算法框架 ? (1)递归回溯 ? (...
第5章 回溯法 ? 学习要点 ? 理解回溯法的深度优先搜索策略 ? 掌握用回溯法解题的算法框架 ? (1)递归回溯最优子结构性质 ? (2)迭代回溯贪心选择性质 ? (3...
热门文档