走进“深度搜索基础训练“，踏入c++算法殿堂（三）

第三道题是这样的：

   【搜索与回溯算法】工作分配问题 (Standard IO)

        

          
        
        
        

          

          AI 代码解读
        
      
      

时间限制: 1000 ms 空间限制: 262144 KB 具体限制

题目描述：

设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。试设计一个算法，为每一个人都分配一件不同的工作，并使总费用达到最小。设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。

输入：

一行有1个正整数n (1≤n≤20)。接下来的n行，每行n个数，第i行表示第i个人各项工作费用。

输出：

将计算出的最小总费用输出

样例输入：

3
4 2 5
2 3 6
3 4 5
样例输出：

9

小航看了看题，喃喃自语道：“应该可以像N皇后问题那样完成。”

“每个人都作为棋子，每份工作作为列，资金作为比较方法，一次次试，定能试出！另外，设置一个临时工费和最终公费，进行比较输出。照这样说，可以用搜索”，说着，他兴致勃勃地敲起了键盘。

#include<iostream>
using namespace std;
const int MAX=999999999;
int q=MAX,n,c[25][25],b[25];
void dg(int x,int ps)
{
    if(x>n)
    {
        if(ps<q) q=ps;
        return;
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            if(b[i]==0)
            {
                b[i]=1;
                dg(x+1,ps+c[i][x]);
                b[i]=0;
            }
        }

    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>c[i][j];
        }
    }
    dg(1,0);
    cout<<q;
}

        

          
        
        
        

          

          AI 代码解读
        
      
      

但是，结果却是：

没办法，只好修改。

#include<bits/stdc++.h>
using namespace std;
int n,a[25][1000],b[1000],s,ms=100000,i,j;
void dg(int x)
{
    if(x==n)
    {
        if(s<ms)
            ms=s;
    }
    else if(s<ms)
    {
        for(int i=0;i<n;i++)
        {
            if(!b[i])
            {
                s+=a[x][i];
                b[i]=1;
                dg(x+1);
                b[i]=0;
                s-=a[x][i];
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
            scanf("%d",&a[i][j]);
    }
    dg(0);
    printf("%d",ms);
    return 0;
}

        

          
        
        
        

          

          AI 代码解读
        
      
      

再次提交，小航又得到了一个碧绿而沁人心脾的100分!然后，他又滚动屏幕，把目光投入了下一题。欲知后事如何，请看下集。