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

回溯法解0-1背包问题


#include <iostream> #include <queue> #include <stack> using namespace std; #define L 3 //?á?????? #define N 5 //?á?????? struct node { int a; int b; int layer; node(int m,int n,int l) { a=m; b=n; layer=l; } }; class Trend { private: stack<node> path; int c[N][N]; int sign[N],sign2[N]; public: Trend(int b[N][N]) { for(int i=0;i<N;i++) for(int j=0;j<N;j++) { sign[i]=0; c[i][j]=b[i][j]; } sign[L-1]=1; } int optpath(int j,int n,int sign[N]) { int min=0; if(n==1) { path.push(node(j,L-1,1)); return c[j][L-1]; }

else if(n<=0) return 1000; for(int k=0,i=0;i<N;i++) { int y=0; if(!sign[i]) { sign[i]=1; y=1; int sign3[N]; copy(sign3,sign); int m=optpath(i,n-1,sign3); if(!k&&c[j][i]) { path.push(node(j,i,n)); min=c[j][i]+m; k=1; } else if(k&&c[j][i]&&min>=c[j][i]+m) { min=c[j][i]+m; path.push(node(j,i,n)); } if(y)sign[i]=0; } } return min; } void prin() { cout<<"????????·?·¨?á????"<<endl; cout<<optpath(L-1,N,sign)<<endl; cout<<"The path is :"<<endl; int l=N,begin=L; cout<<L; while(!path.empty()) { node k=path.top(); if(k.a+1==begin&&k.layer==l) { begin=k.b+1; cout<<"-->"<<k.b+1;

l=l-1; } path.pop(); } cout<<endl; } void copy(int a[N],int b[N]) { for(int i=0;i<N;i++) a[i]=b[i]; } };

void main() { int A[5][5]={{1000,20,30,10,11},{15,1000,16,4,2},{3,5,1000,2,4},{19,6, 18,1000,3},{15,4,7,16,1000}}; Trend path1(A); path1.prin(); }


相关文章:
回溯算法解决0-1背包问题
回溯算法解决0-1背包问题 - 《算法分析与设计》 实验报告 2015-2016 年第 2 学期 实验班级: 学生姓名: 学号: 指导老师: 信息工程学院 实验项目名称:回溯算法....
用回溯法解决0-1背包问题
标签: 回溯法| 背包| 用回溯法解决0-1背包问题_工学_高等教育_教育专区。算法试验报告,用回溯法解决0-1背包问题 #include&lt;stdio.h&gt; int c; //背包容量 ...
回溯法解0-1背包问题实验报告
实验4 一 、实验要求 回溯法解 0-1 背包问题 1.要求用回溯法求解 0-1 背包问题; 2.要求交互输入背包容量,物品重量数组,物品价值数组; 3.要求显示结果。 ...
回溯法-0-1背包问题
回溯法-0-1背包问题 - 1、 问题描述 一、0-1 背包问题 给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,如何选择才能使 得物品的总价格最高...
回溯算法解决0-1背包问题(DOC)
回溯算法解决0-1背包问题(DOC) - 《算法分析与设计》 实验报告 2015-2016 年第 2 学期 实验班级: 学生姓名: 学号: 指导老师: 信息工程学院 实验项目名称...
回溯法和分支限界法解决0-1背包题
0-1 背包问题计科 1 班 朱润华 2012040732 方法 1:回溯法 一、回溯法描述: 用回溯法解问题时,应明确定义问题的解空间。问题的解空间至少包含问题的一个(最...
0-1背包问题的解决(回溯法)
回溯法| 背包| 0-1背包问题的解决(回溯法)_解决方案_计划/解决方案_实用文档。算法设计分析,通过回溯法和动态规划的方法解决0-1背包问题。 前面...
回溯法和分支限界法解决0-1背包题(精)
0-1 背包问题 计科 1 班 朱润华 2012040732 方法 1:回溯法 一、回溯法描述: 用回溯法解问题时,应明确定义问题的解空间。问题的解空间至少包含问题的一 个(...
回溯法和分支限界法解决0-1背包题要点
回溯法和分支限界法解决0-1背包题要点_其它_职业教育_教育专区。0-1 背包问题计科 1 班 朱润华 2012040732 方法 1:回溯法 一、回溯法描述: 用回溯法解问题...
回溯法解决01背包问题
回溯法解决01背包问题 - 回溯法是个既带有系统性又带有跳跃性的搜索算法。 它在包含问题的所有解的解空间树中按照 深度优先的策略,从根节点出发搜索解空间树。...
更多相关标签: