当前位置:首页 >> 计算机软件及应用 >>

算法回溯法的源代码

#include "stdafx.h" // 优化了回溯代码 // 即不移动到不可能包含比当前最优解还要好的解的右子树 #include<iostream.h> template<class T> class Loading { friend GetMaxLoading(T [], T, int); private: void Compute(int i); int n; c, cw, // 货箱数量 // 货箱重量数组 // 第一艘船的容量 T *w,

// 当前的装载重量 r; // 剩余货物的重量之和

bestw, // 目前最优装载重量 }; // 树的每个节点上,都有唯一的剩余货物重量 r template<class T> void Loading<T>::Compute(int i) { if (i > n) { // 与 16x1 有所不同,只要到移到了叶节点,就必定是最佳方案 // 暂时的理解:只有 cw + w[i] <= c 时,会继续往下深入,当前 x 就一定取值了。 // bestw = cw; return; } // r 是全局变量,减去当前货物的重量 // 无论放得下还是放不下,先减去当前货物重量再说 cout<<"r-w["<< i <<"]="<< r <<"-"<< w[i] <<"="; r -= w[i]; cout<< r<<endl; // 装下当前货物的时候,情况与 16x1 一模一样 if (cw + w[i] <= c) { // try x[i] = 1 cw += w[i]; Compute(i+1); cw -= w[i]; } // 如果当前装载货物的之和,加上剩余货物重量之和,是否大于当前最优装载 或者 cw + r >bestw 时,也会继续往下深入,但这样一定会最优解吗?

// 16x1 里每次必定继续往下计算,但现在不一定了 // 真正的意义:当前节点一定要取 x=1 的情况,即左孩子的值;否则一定得不到最优解 // // cout<<" 不取当前值的话,即使所有剩余货物 r+当前装载 cw,也不能比当前 bestw 更好 这个判断在每个节点都有,只要比较当前节点的 bestw 就行了 cw="<<cw<<", r="<< r <<""<<", bestw="<<bestw<<endl;

if (cw + r >bestw) // try x[i] = 0 Compute(i+1); else cout<<" cw + r >bestw,不必计算了!"<<endl; // r 恢复当前货物重量的值,退回准备从更高层去遍历 r += w[i]; } template<class T> T GetMaxLoading(T w[], T c, int n) { Loading<T> X; X.w = w; X.c = c; X.n = n; X.bestw = 0; X.cw = 0; // r 的初始值为所有重量之和 X.r = 0; for (int i = 1; i <= n; i++) X.r += w[i]; // 计算最佳装载,从 1 层算起(很重要)。0 层是无用值,放弃。 X.Compute(1); // 因为是自动递归计算,所以返回的时候,已经得到了最大装载值 // 返回的是全局变量的最大装载值,不是 Compute 函数的返回值 returnX.bestw; } void main(void) { /* int w[6] = {0, 5, 1, 6, 2, 7}; int n = 5; int c = 10; */ int w[5] = {0, 8, 6, 2, 3}; int n = 4; int c = 12;

cout<<"Value of max loading is"<<endl; cout<<GetMaxLoading(w,c,n) <<endl; }

源代码: 1.不带剪枝函数,非常类似装载问题 #include<iostream> #include<algorithm> using namespace std; class Knapsack{ public: Knapsack(double *pp,double *ww,intnn,double cc){ p = pp; w = ww; n = nn; c = cc; cw = 0; cp = 0; bestp = 0; x = new int[n]; cx = new int[n];
} void knapsack(){ backtrack(0); }

void backtrack(int i){//回溯法 if(i > n){ if(cp>bestp){ bestp = cp; for(int i = 0; i < n; i++) x[i] = cx[i]; } return; }

if(cw + w[i] <= c){//搜索右子树 cw += w[i]; cp += p[i]; cx[i] = 1; backtrack(i+1); cw -= w[i];

cp -= p[i]; } cx[i] = 0; backtrack(i+1);//搜索左子树 } void printResult(){ cout<< "可以装入的最大价值为:" <<bestp<<endl; cout<< "装入的物品依次为:"; for(int i = 0; i < n; i++){ if(x[i] == 1) cout<< i+1 << " "; } cout<<endl; } private: double *p,*w; int n; double c; double bestp,cp,cw;//最大价值,当前价值,当前重量 int *x,*cx; }; int main(){ double p[4] = {9,10,7,4},w[4] = {3,5,2,1}; Knapsack ks = Knapsack(p,w,4,7); ks.knapsack(); ks.printResult(); return 0; } 2.带剪枝函数的递归回溯(待看) #include<iostream> using namespace std; class Knap { friend int Knapsack(int p[],int w[],intc,int n ); public: void print() { for(int m=1;m<=n;m++) { cout<<bestx[m]<<" "; }

cout<<endl; }; private: int Bound(int i); void Backtrack(int i); int c;//背包容量 int n; //物品数 int *w;//物品重量数组 int *p;//物品价值数组 intcw;//当前重量 intcp;//当前价值 intbestp;//当前最优值 int *bestx;//当前最优解 int *x;//当前解 }; int Knap::Bound(int i) { //计算上界 int cleft=c-cw;//剩余容量 int b=cp; //以物品单位重量价值递减序装入物品 while(i<=n&&w[i]<=cleft) { cleft-=w[i]; b+=p[i]; i++; } //装满背包 if(i<=n) b+=p[i]/w[i]*cleft; return b; } void Knap::Backtrack(int i) { if(i>n) { if(bestp<cp) { for(int j=1;j<=n;j++) bestx[j]=x[j]; bestp=cp; }

return; } if(cw+w[i]<=c) //搜索左子树 { x[i]=1; cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i]; cp-=p[i]; } if(Bound(i+1)>bestp)//搜索右子树 { x[i]=0; Backtrack(i+1); } } class Object { friend int Knapsack(int p[],int w[],intc,int n); public: int operator<=(Object a)const { return (d>=a.d); } private: int ID; float d; }; int Knapsack(int p[],int w[],intc,int n) { //为 Knap::Backtrack 初始化 int W=0; int P=0; int i=1; Object *Q=new Object[n]; for(i=1;i<=n;i++) { Q[i-1].ID=i; Q[i-1].d=1.0*p[i]/w[i]; P+=p[i]; W+=w[i];

} if(W<=c) return P;//装入所有物品 //依物品单位重量排序 float f; for( i=0;i<n;i++) for(int j=i;j<n;j++) { if(Q[i].d<Q[j].d) { f=Q[i].d; Q[i].d=Q[j].d; Q[j].d=f; } } Knap K; K.p = new int[n+1]; K.w = new int[n+1]; K.x = new int[n+1]; K.bestx = new int[n+1]; K.x[0]=0; K.bestx[0]=0; for( i=1;i<=n;i++) { K.p[i]=p[Q[i-1].ID]; K.w[i]=w[Q[i-1].ID]; } K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; //回溯搜索 K.Backtrack(1); K.print(); delete [] Q; delete [] K.w; delete [] K.p; return K.bestp; } void main() { int a[] ={0,9,10,7,4};

int b[] ={0,3,5,2,1}; int c=7; int n=4; int i=0; int *p=a; int *w=b;

cout<<"最优解为(bestx):"<<endl; cout<<"最优值为(bestp):"<<endl; cout<<Knapsack(p,w,c,n)<<endl; }


相关文章:
算法回溯法的源代码.doc
算法回溯法的源代码 - #include stdafx.h // 优化了回溯代码
算法之回溯法实现.doc
算法之回溯法实现 - 实验 4 回溯法实现 一、实验目标: 1.熟悉回溯法应用场景及实现的基本方法步骤; 2.学会回溯法的实现方法和分析方法: 二、实验内容 1. ...
算法设计与分析(详细解析(含源代码)).doc
算法设计与分析(详细解析(含源代码)) - 常用算法设计方法 要使计算机能完成人们预定的工作, 首先必须为如何完成预定的工作设计一个算法, 然 后再根据算法编写程序...
数学建模十大算法部分带有源代码_图文.ppt
数学建模十大算法部分带有源代码 - 数学建模竞赛中应当 掌握的十类算法 ? ? ? ? ? ? ? ? ? ? 蒙特卡罗算法 数据处理算法 数学规划算法 图论算法 动态规划、...
c语言经典算法回溯法.doc
c语言经典算法回溯法 - c 语言经典算法 五、回溯法 回溯法也称为试探法, 该
回溯算法之01背包问题JAVA源程序.pdf
回溯算法之01背包问题JAVA源程序 - 实验报告 11 课程 数据结构与算法 班级 11 计本 实验名称 学号 回溯法 105032011130 第 姓名 页 风律澈 实验日期:2013 年....
回溯算法-N后问题和符号三角形java算法源程序.doc
回溯算法-N后问题和符号三角形java算法源程序 - 实验报告 10 课程 数据结构与算法 实验名称 班级 11 计本 学号 回溯法 105032011130 姓名 第页 风律澈 实验...
算法题及源程序.doc
算法题及源程序 - 大量的算法题与pascal源程序,是信息学奥林匹克竞赛的好书。... 回溯法回溯法是一种选优搜索法,按选优...排序算法源代码 59页 1下载券 《...
马踏棋盘回溯算法C++源代码.doc
马踏棋盘回溯算法C++源代码_IT/计算机_专业资料。马踏棋盘回溯算法C++源代码,VS2010测试通过 马踏棋盘回溯算法完整源代码(在 VS2010 中调试通过) : #include "...
算法分析设计回溯法求解装载问题实验报告.pdf
算法分析设计回溯法求解装载问题实验报告_IT/计算机_专业资料。算法分析设计回溯法求解装载问题,完美版报告 回溯法求解装载问题一、方法一般原理回溯法也称为试探法,...
回溯法解四色方柱问题实验报告 JAVA源代码.pdf
回溯法解四色方柱问题实验报告 JAVA源代码 - 算法与分析 课程设计报告 题专班学姓 目:回溯法解四色方柱问题 业: 级: 号: 名: 网络工程 1020552 102055203...
算法设计与分析:回溯法-实验报告.doc
算法设计与分析:回溯法-实验报告 - 应用数学 学院 姓名 实验题目 信息安全 专业 班 学号 回溯算法 实验评分表 序 评分项目 号 1 指导教师评分标准 完成度 评分...
算法实验代码.txt
算法实验代码 - 附录1:求矩阵连乘的最少计算次数的源代码 http://wen
基于回溯法的排课算法.pdf
+86-551-5690963 5690964 基于回溯法的排课算法杨兴旺(昆明广播电视大学,云南 昆明 650216 ) 摘要:多年来,排课算法是众多专家学者感兴趣的课题,同时也取得了诸多...
0027算法笔记【回溯法】回溯法与装载问题.doc
0027算法笔记【回溯法回溯法与装载问题_计算机软件及应用_IT/计算机_专业...(int i=1;i<=n;i++) { X.r+=w[i]; 迭代回溯具体代码如下: [cpp]...
算法设计与分析第5章 回溯法_图文.ppt
? wi xi ? c1 i ?1 用回溯法设计解装载问题的O(2n)计 算时间算法。在...代码如下: for(j=1;j...
算法分析复习题目及答案.doc
算法分析复习题目及答案 - 一、选择题 1、二分搜索算法是利用( A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法...
第九章 回溯法算法设计_图文.ppt
第九章 回溯法算法设计 - 石志国 《算法分析与设计(C++描述)》课件... 第九章 回溯法算法设计_工学_高等教育_教育...按照搜索子集合树框架来写代码子集,为大集合...
算法分析与设计常见算法思想_图文.doc
(DFS) 深度优先搜索算法也叫回溯法,其基本策略是:...伪代码(使用栈实现) ,递归实现: long DFS(图 g,...Dijkstra 算法 for 单源最短路径 Dijkstra(迪杰...
算法是程序设计的灵魂.doc
随机化算法在内的一些算法,包含了一些随机输入。 形式化算法的概念部分源自尝试...我们一般常见的几种算法分析设计策略主要有:动态规划、贪心算法回溯法、分支...
更多相关标签: