当前位置:首页 » 《随便一记》 » 正文

工作分配问题-回溯法

28 人参与  2022年09月23日 16:24  分类 : 《随便一记》  评论

点击全文阅读


问题

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

Input

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

Output

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

Sample Input

3
10 2 3
2 3 4
3 4 5

Sample Output

9

分析

我们让每个工作选择一个人,每层dfs()表示工作m ,每个结点for循环表示被选择的人i ;
数组book[]记录人是都被选择分配了工作;
sum记录每个选择完后的费用总数;

AC代码

#include<iostream>#define N 9999using namespace std;int n;int sum=0,Min=N;int pay[N][N];int book[N];void dfs(int m) { //第m份工作if(m>n) {//工作分配完了 Min=min(Min,sum);//更新最小值 return;//结束 }for(int i=0; i<n; i++) { //第m份工作分给第i个人if(book[i]==0) {//如果第i个人没有被分配 book[i]=1;sum+=pay[m][i];if(sum<Min)//剪枝 dfs(m++);sum-=pay[m][i];//回溯 book[i]=0;}}}int main() {cin>>n;for(int i=0; i<n; i++) {for(int j=0; j<n; j++) {cin>>pay[i][j];}}dfs(1);cout<<Min<<"\n";}

代码分析

时间复杂度为O(n²)


点击全文阅读


本文链接:http://zhangshiyu.com/post/45061.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 送子观音节选列表_送子观音节选(程浩天殷茵程沐白)
  • 黄花落尽春光来结局+番外笔趣阁(宋晴沈子岳薛灵灵)_黄花落尽春光来结局+番外笔趣阁
  • 屠城时夫君带了外室逃生,后来他跪求我原谅推文_陆玄川秦绾绾***免费品鉴_小说后续在线阅读_无删减免费完结_
  • 完结文重生后我让校花保管所有准考证+完结篇列表_完结文重生后我让校花保管所有准考证+完结篇(秦雨然江述怀洛瑶)
  • 江映月小说小说全集+延伸+完本(前妻有喜,陆总请排队恭喜)畅享在线阅读
  • 风过南山,爱与愿违在线(唐婉心陆谨言)全书免费_(唐婉心陆谨言)风过南山,爱与愿违在线后续(唐婉心陆谨言)
  • 天阉老公出轨魅魔秘书,我找薄肌大佬生孩子他却后悔了免费(沈知薇贺宴礼)_天阉老公出轨魅魔秘书,我找薄肌大佬生孩子他却后悔了免费(沈知薇贺宴礼)
  • 秦雨然的重生后我让校花保管所有准考证彩蛋秦雨然江述怀洛瑶全书在线
  • 完结文送子观音高分完本列表_完结文送子观音高分完本(殷茵程沐白)
  • 此后春风皆过客(池婉白叙安)整本+后续+(此后春风皆过客)结局在线阅读
  • 春知晓梦不觉完结爽文(阮清歌薄时谦)_春知晓梦不觉完结爽文(阮清歌薄时谦)
  • 完结文流光错系断蓬之舟谢晚烟在线列表_完结文流光错系断蓬之舟谢晚烟在线(沈煜谢晚烟)

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1