主要内容 #
- 问题描述
- 计算方法
- 参考代码
1. 问题描述 #
设有A,B,C,D,E五人从事J1,J2,J3,J4,J5五项工作,每人只能从事一项,他们的效益如下。
每人选择五项工作中的一项,在各种选择的组合中,找到效益最高的的一种组合输出。
2. 计算方法 #
- ⒈用数组f储存工作选择的方案;数组g存放最优的工作选择方案;数组p用于表示某项工作有没有被选择了,若工作已被选取则p(i) = 1,若该工作未被选取p(i) = 0。
- ⒉(1)选择p(i)=0的第i项工作;
(2)判断效益是否高于max已记录的效益,若高于则更新g数组及max的值。 - ⒊搜索策略: 回溯法(深度优先搜索dfs)。
这里简单讲一下:
深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。
这个算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。下面的一棵树,用DFS方法搜索每一个叶子节点的搜寻顺序如下所示:
3. 参考代码 #
#include < iostream > using namespace std; int Data[6][6]={{0,0,0,0,0,0},{0,13,11,10,4,7},{0,13,10,10,8,5},{0,5,9,7,7,4},{0,15,12,10,11,5},{0,10,11,8,8,4}}; int max1=0,g[10],f[10]; bool p[6]={0}; int go(int step,int t) // step是第几个人,t是之前已得的效益 { for (int i=1;i <=5;i++) if (!p[i]) //判断第i项工作没人选择 { f[step]=i; //第step个人,就选第i项工作 p[i]=1; //标记第i项工作被人安排了 t+=Data[step][i]; //计算效益值 if (step < 5) go(step+1,t); else if (t > max1) //保存最佳效益值 { max1=t; for (int j=1;j <=5;j++) g[j]=f[j]; //保存最优效益下的工作选择方案 } t-=Data[step][i]; //回溯 p[i]=0; } } int main() { go(1,0); //从第1个人,总效益为0开始 for (int i=1;i<=5;i++) cout<<char(64+i)<<":J"<<g[i]<<" "; //输出各项工作安排情况 cout<<endl; cout<<"supply:"<<max1<<endl; //输出最佳效益值 }