工作分配问题【回溯法】

问题描述

设有 nn 件工作分配给 nn 个人。将工作 ii 分配给第 jj 个人所需的费用为 cijcij。试设计一个算法，为每一个人都分配一件不同的工作，并使总费用达到最小。

设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。

输入格式

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

输出格式

一行，1 个整数，即最小总费用。

样例一

input

3 4 2 5 2 3 6 3 4 5

output

9

数据范围与约定

时间限制： 1s1s

内存限制： 256MB

 

#include<bits/stdc++.h> using namespace std; int t[31][31]; int ans=0x7fffff; bool gz[30]; int ls=0; void sz(){ ans=min(ans,ls); } void search(int n,int k){ if(k==n+1){ sz(); return ; } for(int i=1;i<=n;i++){ if(!gz[i]){ gz[i]=true; ls+=t[k][i]; if(ls<ans){ search(n,k+1); } ls-=t[k][i]; gz[i]=false; } } } int main(){ int n; cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>t[i][j]; search(n,1); cout<<ans<<endl; return 0; }

 

转载于:https://www.cnblogs.com/luv-letters/p/8550591.html

相关资源：回溯算法 作业分配问题