题目

设有A，B，C，D，E五人从事J1，J2，J3，J4，J5五项工作，每人只能从事一项，他们的效益如下。

-	J1	J2	J3	J4	J5
A	13	11	10	4	7
B	13	10	10	8	5
C	5	9	7	7	4
D	15	12	10	11	5
E	10	11	8	8	4

每人选择五项工作中的一项，在各种选择的组合中，找到效益最高的的一种组合输出。

代码

#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};
void go(int k,int t){
    for(int i=1;i<=5;i++){
        if(!p[i]){//当前工作没人做
            p[i]=1;
            f[k]=i;
            t+=data[k][i];
            if(k==5){
                if(t>max1) {
                    max1=t;
                    for(int j=1;j<=5;j++){//复制到到最终结果中
                        g[j]=f[j];
                    }
                }
            }else{
                go(k+1,t);
            }
            t-=data[k][i];//回溯，减掉
            p[i]=0;//回溯，设为此工作没人做
        }
    }
}
int main(){
    go(1,0);
    cout<<max1<<endl;
    for(int i=1;i<=5;i++){
        cout<<g[i]<<" ";
    }
    cout<<endl;
}

简析

其实也还是套模版练习题,我们用一个二位数组保存工作数据,0的位置用0代，从1开始。

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

1 for循环范围

从1到5，5项工作可选，每一项都能选。

    for(int i=1;i<=5;i++){

2 判断可选

需要用一个数组保存选中了的书，如第三项工作被选过，b[3]=1;

        if(!p[i]){//当前工作没人做

3 选中后

• 状态数组设为1
• 效益值加上这个数

  p[i]=1;
  f[k]=i;
  t+=data[k][i];

4 结束条件，搜索放方法

• 如果k为 5，5项工作都已经分配完成，此时判断效益是否大于当前保存的最大值
• 否则继续搜索

           if(k==5){
                if(t>max1) {
                    max1=t;
                    for(int j=1;j<=5;j++){//复制到到最终结果中
                        g[j]=f[j];
                    }
                }
            }else{
                go(k+1,t);
            }

5 回溯

• 状态数组设为0
• 效益值减掉这个数

            t-=data[k][i];//回溯，减掉
            p[i]=0;//回溯，设为此工作没人做