剪枝

第一次碰到需要剪枝优化的题

题目描述

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

输入

第一行一个正整数n(1<=n<=20),接下来的n 行，每行n 个数，表示工作费用 。

输出

输出有m行，每行输出最小总费用。

样例输入

5
50 43 1 58 60
87 22 5 62 71
62 98 97 27 38
56 57 96 73 71
92 36 43 27 95

样例输出

144

第一次提交代码：

#include <cstdio>
using namespace std;

const int INF = 0x3f3f3f3f;
int n;
int a[30][30];
bool vis[30];
int sum = INF;
int cnt = 0;
void dfs(int x)
{
    if(x>n-1 && cnt<sum)
    {
        sum = cnt;
        return;
    }
    for(int i = 0; i < n; i++)
        if(!vis[i])
        {
            vis[i] = 1;
            cnt += a[i][x];
            dfs(x+1);
            cnt -= a[i][x];
            vis[i] = 0;
        }
}

int main()
{
    // freopen("input.txt","r",stdin);
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            scanf("%d", &a[i][j]);
    dfs(0);
    printf("%d\n", sum);

    return 0;
}

提交后时间超限，在 dfs 函数内添加简单的剪枝即可。

新的dfs函数：

void dfs(int x)
{
    if(cnt > sum) //剪枝
        return;
    if(x>n-1 && cnt<sum)
    {
        sum = cnt;
        return;
    }
    for(int i = 0; i < n; i++)
        if(!vis[i])
        {
            vis[i] = 1;
            cnt += a[i][x];
            dfs(x+1);
            cnt -= a[i][x];
            vis[i] = 0;
        }
}

耗时7，一个小小的剪枝居然带来这么明显的优化！

这题也是经典的回溯算法