工作分配问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

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

Input

输入数据的第一行有1 个正整数n (1≤n≤20)。接下来的n行，每行n个数，表示工作费用。

Output

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

Sample Input

Sample Output

Hint

Source

初始：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,Min,sum;//Min代表要求的 最小和，sum为临时求和
 4 int data[22][22];//都是 在一个 矩阵里面 求 最大或者 最小
 5 int book[22];//标记是否访问
 6 void dfs(int x){
 7     //if(x>=n) return ;//若是 超过了搜索的行 ，可以返回了 ,加不加都对，因为 下面的x->n 的时候，肯定是n个已经标记完了
 8     int cnt=0;//主要判断是否是 全部标记了
 9     for(int i=0;i<n;i++) if(book[i]==1) cnt++;//计算标记的个数
10     if(cnt==n&&Min>sum) Min=sum;//若是 全部标记了，且比最小值 小 ，更新最小值
11     for(int i=0;i<n;i++){
12         if(!book[i]){
13             book[i]=1;
14             sum+=data[x][i];
15             if(sum<Min) dfs(x+1);//剪掉 大于Min 的
16             book[i]=0;
17             sum-=data[x][i];
18         }
19     }
20 }
21 int main()
22 {
23     cin>>n;
24     Min=INT_MAX,sum=0;
25     for(int i=0;i<n;i++){
26         for(int j=0;j<n;j++)
27                 cin>>data[i][j];
28         book[i]=0;
29     }
30     dfs(0);
31     cout<<Min<<endl;
32     return 0;
33 }

优化：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,Min,sum;//Min代表要求的 最小和，sum为临时求和
 4 int data[22][22];//都是 在一个 矩阵里面 求 最大或者 最小
 5 int book[22];//标记是否访问
 6 void dfs(int x){
 7     //if(x>=n) return ;//若是 超过了搜索的行 ，可以返回了 ,加不加都对，因为 下面的x->n 的时候，肯定是n个已经标记完了
 8    // int cnt=0;//主要判断是否是 全部标记了
 9    // for(int i=0;i<n;i++) if(book[i]==1) cnt++;//计算标记的个数
10     if(x==n&&Min>sum) Min=sum;//若是 cnt==n全部标记了，且比最小值 小 ，更新最小值  ,也可以 不求cnt, x==n的时候 也对
11     for(int i=0;i<n;i++){
12         if(!book[i]){
13             book[i]=1;
14             sum+=data[x][i];
15             if(sum<Min) dfs(x+1);//剪掉 大于Min 的
16             book[i]=0;
17             sum-=data[x][i];
18         }
19     }
20 }
21 int main()
22 {
23     cin>>n;
24     Min=INT_MAX,sum=0;
25     for(int i=0;i<n;i++){
26         for(int j=0;j<n;j++)
27                 cin>>data[i][j];
28         book[i]=0;
29     }
30     dfs(0);
31     cout<<Min<<endl;
32     return 0;
33 }

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,Min;//Min代表要求的 最小和，sum为临时求和
 4 int data[22][22];//都是 在一个 矩阵里面 求 最大或者 最小
 5 int book[22];//标记是否访问
 6 void dfs(int x,int sum){
 7     if(x==n&&Min>sum) Min=sum;//若是 cnt==n全部标记了，且比最小值 小 ，更新最小值  ,也可以 不求cnt, x==n的时候 也对
 8     for(int i=0;i<n;i++){
 9         if(!book[i]){
10             book[i]=1;
11             if(sum<Min) dfs(x+1,sum+data[x][i]);//剪掉 大于Min 的,sum 当作参数 传递去的时候，回溯的时候，不必再有sum-=data[x][i]因为当前sum对整个循环有效
12             book[i]=0;
13         }
14     }
15 }
16 int main()
17 {
18     cin>>n;
19     Min=INT_MAX;
20     for(int i=0;i<n;i++){
21         for(int j=0;j<n;j++)
22                 cin>>data[i][j];
23         book[i]=0;
24     }
25     dfs(0,0);//第一个 为x=0 ,第二个 为sum=0
26     cout<<Min<<endl;
27     return 0;
28 }