一. 工作安排问题 (第一届选拔赛第一题)
【试题】 现有 N (N≤8) 件工作, 分别由 N 个人完成, 每人都完成一件,且只完成一 件,
每人完成不同工作的时间不同. 试设计一种分配工作方案, 使完成 N 件工作所需的总时间
最少.
原始数据由文本文件 EXAM1.TXT 给出, 其格式如下:
第 1 行: 工作任务数(N)
第 2 -- N+1 行: 第 i+1 行为第 i 个人完成各件工作所需的时间. 以
上各数均为不超过 1000 的正整数.
计算结果可直接在屏幕上输出: 第一行为工作分配方案, 共 N 组, 每组数
据的形式为 a-b, 其中 a 为工作人员编号, b 为他应完成的工作序号.
例: 设 EXAM1.TXT 的数据为:
4
2 15 13 4
10 4 14 15
9 14 16 13
7 8 11 9
对此, 一个正确的输出可以是
1-4, 2-2, 3-1, 4-3
TOTAL=28
/**//*
** Author:cjz
** Create Date:2008/04/07
*/
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int> > arr;
int n;
vector<int> min_vec;
int min_total=9999999;
void print_array(int n);
void solve(vector<int> temp);
int _tmain(int argc, _TCHAR* argv[])
{
ifstream in("c:\\aa.txt");
in>>n;
for(int i=0;i<n;i++)
{
vector<int> tmp;
for(int j=0;j<n;j++)
{
tmp.push_back(0);
in>>tmp[j];
}
arr.push_back(tmp);
}
print_array(n);
vector<int> vec;
solve(vec);
cout<<"----------------------------------------------------------------------------"<<endl;
for(int i=0;i<min_vec.size();i++)
{
cout<<(min_vec[i])<<" ";
}
in.close();
system("pause");
return 0;
}
void print_array(int n)
{
for(int i=0;i<n;++i)
{
for(int j=0;j<n;j++)
printf("%3d",arr[i][j]);
cout<<endl;
}
}
void solve(vector<int> vec)
{
if(vec.size()==n)
{
//得出一個解
int total=0;
for(int i=0;i<vec.size();i++)
{
total+=arr[i][vec[i]];
cout<<(vec[i])<<" ";
}
cout<<endl;
if(total<min_total)
{
min_vec=vec;
min_total=total;
}
return;
}
int index=-1;
int size=vec.size();
if(size>0)
index=vec[size-1];
for(int i=0;i<n;i++)
{
vector<int>::iterator iter=find(vec.begin(),vec.end(),i);
if(iter==vec.end())
{
vec.push_back(i);
solve(vec);
vec.pop_back();
}
}
}