ACM乐园
Love Me,Love My Code!
posts - 53,  comments - 24,  trackbacks - 0
问题描述:
设有n件工作分配给n个人。为第i个人分配工作j所需的费用为c[i][j] 。试设计一个算法,计算最佳工作分配方案,为每一个人都分配1 件不同的工作,并使总费用达到最小。
数据输入 :
第一行一个正整数n(1<=n<=20),接下来的n 行,每行n 个数,表示工作费用 。
结果输出:
输出有m行,每行输出最小总费用。
输入样例:
5
50 43 1 58 60
87 22 5 62 71
62 98 97 27 38
56 57 96 73 71
92 36 43 27 95
输出样例:
144

用回溯法求解,这就是在全排列中找出费用最小的
//工作分配问题
/*

3
10 2 3
2 3 4
3 4 5
*/
#include 
<iostream>
#include <algorithm>
using namespace std;

int table[21][21],n,best,r[21];

int compute(int k)
{
    
int temp=0,i;
    
for(i=1;i<=k;i++)
        temp
+=table[i][r[i]];
    
return temp;
}

void search(int k)
{
    
if(k==n)
    {
        
int temp=compute(n);
        
if(temp<best)
            best
=temp;
        
return;
    }
    
for(int i=k;i<=n;i++)
    {
        swap(r[i],r[k]);
        
if(compute(k) < best)
            search(k
+1);
        swap(r[i],r[k]);
    }
}

int main()
{
    
int i,j;
    
while(cin>>n,n)
    {
        
for(i=1;i<=n;i++)
            
for(j=1;j<=n;j++)
                cin
>>table[i][j];
        
for(i=1;i<=n;i++)
            r[i]
=i;
        best
=INT_MAX;
        search(
1);
        cout
<<best<<endl;
    }
    
return 0;
}


posted on 2012-10-24 22:24 大大木马 阅读(8068) 评论(1)  编辑 收藏 引用

FeedBack:
# re: 工作分配问题(回溯算法)
2015-08-19 08:52 | 45
/*
时间:2011-11-20
作者:xiaosi
题目:工作分配问题
*/
#include<iostream>
#include<cstdio>
using namespace std;

#define M 100
class Work
{
friend void work();
private:
void Backtrack(int t);
int N;//N件工作 N个人
int cw;//当前费用
int bestw;//最少费用
int flag[M];
int c[M][M];//费用
public:
void Print();
};


void Work::Backtrack(int t)
{//搜索t第层
int i,j;
if(t>N)//到达叶子节点
{
if(cw<bestw)
{
bestw = cw;
}
return;
}
else
{
for(i=1;i<=N;i++)
{
if(cw<bestw&&flag[i]==0)
{
cw+=c[t][i];
flag[i]=1;
Backtrack(t+1);
cw-=c[t][i];
flag[i] = 0;
}

}
}
}

void work()
{
int i,j;
Work w;
w.bestw = 1000000;
w.cw = 0;
scanf("%d",&w.N);
for(i=1;i<=w.N;i++)
{
for(j=1;j<=w.N;j++)
{
scanf("%d",&w.c[i][j]);
}
}
for(j=1;j<=w.N;j++)
{
w.flag[j]=0;
}
w.Backtrack(1);

printf("%d\n",w.bestw);
}

int main()
{
work();
return 0;
}  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2015年8月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

常用链接

留言簿(1)

随笔档案(53)

文章档案(2)

搜索

  •  

积分与排名

  • 积分 - 62269
  • 排名 - 353

最新评论

阅读排行榜

评论排行榜