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

工作分配问题-回溯法

29 人参与  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)
  • 赞助本站

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

最新文章

  • 全书浏览重生后联姻丈夫爱上KTV小妹,我死遁了(姜满裴聿琛温舒柠)_重生后联姻丈夫爱上KTV小妹,我死遁了(姜满裴聿琛温舒柠)全书结局
  • 时筠荣景琛小说(荣少的步步沦陷)外篇+结局(时筠荣景琛)全篇在线阅读
  • 重生在高考前,我笑着送小青梅和小混混去庆祝成人礼老书虫(沈晏安乔念),重生在高考前,我笑着送小青梅和小混混去庆祝成人礼老书虫
  • 送子观音优质(殷茵程沐白)全书免费_(殷茵程沐白)送子观音优质后续(殷茵程沐白)
  • 重生后,我笑送全班去三亚毕业旅行推荐_徐凯沈清别以为阅读_小说后续在线阅读_无删减免费完结_
  • 北风秋霜覆往忆完结+结局+番外(傅砚寒沈沐柒)全书浏览_北风秋霜覆往忆完结+结局+番外全书浏览
  • 小说大结局小说罗毅小说已更新+特别篇(转职神级辅助,转身上报国家!)纯净版
  • 碎骨揉香与君长诀精修版(褚明意萧鹤明)全书浏览_碎骨揉香与君长诀精修版全书浏览
  • 只因一块表,闺蜜害死我全家热门榜首_陆哲轩李俏陆少爆火全网_小说后续在线阅读_无删减免费完结_
  • 折寒枝簪起霜思全章+后续+结局(宋闻璟沈棠眠)_折寒枝簪起霜思全章+后续+结局(宋闻璟沈棠眠)
  • 高考前一周我绑定了上分系统(袁文淼徐靓靓)_高考前一周我绑定了上分系统(袁文淼徐靓靓)
  • 元乐曦楚寻风:结局+番外免费品鉴终极反转(楚寻风元乐曦):结局+番外评价五颗星

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

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