一. 工作安排問題 (第一屆選拔賽第一題)
【試題】 現有 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();
}
}
}