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

算法回溯法的源代码


#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; }


相关文章:
回溯法解四色方柱问题实验报告 JAVA源代码
回溯法解四色方柱问题实验报告 JAVA源代码 - 算法与分析 课程设计报告 题专班学姓 目:回溯法解四色方柱问题 业: 级: 号: 名: 网络工程 1020552 102055203...
单源最短路径(贪心法)实验报告
单源最短路径(贪心法)实验报告 - 湖南大学算法分析与设计实验报告 含源码... 我回顾了回溯法求解最短路径问题, 在其中...贪婪算法---单源最短路径... 4页 ...
更多相关标签: