原题

题目

题目描述

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

输入格式

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

输出格式

最小总费用。

输入样例

3
4 2 5
2 3 6
3 4 5

输出样例

9

思路

用深搜做。
建一个\(f\)数组用来存放这个位置是否被找过。
\(a\)数组就是题目中的\(c\)数组。
然后深搜，可以通过剪枝优化卡过校内\(OJ\)。

代码

var
  f:array[0..21] of boolean;
  a:array[0..21,0..21] of longint;
  n,i,j,min,s:longint;//以上都是定义
 procedure dfs(k:longint);//dfs函数
  var
    i:longint;
  begin
    for i:=1 to n do//1到n
      if f[i] then//如果没被找过
        begin
          f[i]:=false;//设为找过
          s:=s+a[k,i];//加上
          if k=n then//如果等于n，找最小值
            if s<min then
              min:=s;
          if k<>n then if s<min then//如果不等于n且s依旧小于min，则继续找
            dfs(k+1);
          s:=s-a[k,i];//减回来
          f[i]:=true;//设为没找过
        end;
  end;
begin
  readln(n);//读入n
  for i:=1 to n do for j:=1 to n do read(a[i,j]);//读入a数组
  fillchar(f,sizeof(f),true);//f初始化全部为TRUE
  min:=maxlongint;s:=0;//初始化
  dfs(1);//深搜
  writeln(min);//输出最小值
end.

工作分配问题

原文：https://www.cnblogs.com/wuzhenyu/p/13278676.html