-
Problem Description
設有n件作業分配給n個人，將作業i分配給第j個人所需的費用為
c
i
j
c_{ij}
cij?，試設計一個演算法，為每一個人都分配1件不同的作業，并使總費用達到最小，
設計一個演算法，對于給定的作業費用，計算最佳作業分配方案，使總費用達到最小，
Input
輸入資料的第一行有1 個正整數n (1≤n≤20)，接下來的n行，每行n個數，表示作業費用，
Output
將計算出的最小總費用輸出，
Sample Input
3
10 2 3
2 3 4
3 4 5
Sample Output
9
-
解題思路
為作業 i 安排第 j 個人的解決方法與“運動員最佳匹配問題”類似，讓一方選另一方，這樣就可以構成一棵排列樹，我們讓作業“選”人，那排列樹的結點代表人，而層就代表作業，如下圖左上角的G1表示工人1，且在第一層，表示為作業 1 安排第 1 個人，即將作業1分配給工人1，
-
樣例分析
注：由上可知，最小值可能有多個，但效果一樣，最侄訓傳的都是9，
-
代碼實作
#include <bits/stdc++.h>
using namespace std;
int n;
int pay[21][21]; //pay[i][j]表示將作業i分配給第j個人的費用為pay[i][j]
int Min=INT_MAX; //因為要求最小值，所以將Min初始化為最大整數（int型）
int sum=0; //記錄搜索程序中得到的作業費用和
int book[21]; //用于標記一個人是否已被分配作業：book[i]=0表示沒有被分配作業；book[i]=1表示已經被分配作業
void dfs(int t)
{
if(t>=n) //已經到達葉子結點，繼續判斷是否找到了最小總費用
{
if(Min>sum) //沒有找到最小總費用
{
Min=sum; //更新最小總費用
return;
}
}
for(int i=0;i<n;i++) //為第作業t安排人
{
if(!book[i]) //第i個人還沒有被安排作業
{
book[i]=1; //將作業t分配給第i個人
sum+=pay[t][i]; //更新總費用
if(sum<Min) //如果當前得到的sum小于最小值，就向下搜索子樹；否則剪枝
dfs(t+1);
book[i]=0; //沒有得到比Min更小的和，回溯
sum-=pay[t][i];
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>pay[i][j];
}
book[i]=0;
}
dfs(0);
cout<<Min<<endl;
return 0;
}
-
運行結果
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/237107.html
標籤：其他