问题标题: 1048 工作分配问题怎么超时

Question

0

已解决

程天瑞

资深守护

#include <iostream>
using namespace std;
int maxl=10001,g[20],f[20],a[20][20],n;
bool p[6]={0};
int search(int step,int t)
{
    for (int i=1;i<=n;i++)
    if (!p[i])
    {
        p[i]=1;
        t+=a[step][i];
        if (step<n)
            search(step+1,t);
        else if (t<maxl)
        {
            maxl=t;
        }   
        t-=a[step][i];
        p[i]=0; 
    }
}
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
            cin>>a[i][j];
    }
    search(1,0);
    cout<<maxl; 
    return 0;
}

Answer 1

已采纳

杨喆

初级守护

你需要加入一个剪枝的操作，也就是如果在中间分配到某一个人的工作时已经超过当前找到的最小值就不要继续找这个方案了。

Answer 2

王文博

缔造者之神

1

Answer 3

高见宸

初级光能

1

Answer 4

朱小川

缔造者

1

Answer 5

张庭瑜

初级守护

你好，我不是酷町堂学员看不到题目，能否把题目复制进问题里？等一会我来解答

Answer 6

葛新

资深守护

1048 工作分配问题

题目描述 Description

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

输入描述 Input Description

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

输出描述 Output Description

计算出的最小总费

样例输入 Sample Input

3
4 2 5
2 3 6
3 4 5

样例输出 Sample Output

9

问题标题: 1048 工作分配问题怎么超时

6 个回答: