工作分配问题。设有 n 件工作要分配给 n 个不同的人去完成。将工作 i 分配给第 j 个人所需
要花费的费用为 Cij。设计一个算法，为每个人都分配一件不同的工作，并使总费用达到最
小。
【程序代码】
#include<iostream>
#include<ctime>
#include<iomanip>
using namespace std;
void Swap(int &x,int &y);
class WorkAssignment
{
friend void WorkAsmt(int **c,int n,int *bestx);
private:
void Backtrack(int i);
int **c,//个作业所需要的处理时间
*x,//当前作业调度
*bestx,//当前最优分配
best,//当前最优值
n,//作业数
cx;//当前值
};
//回溯
void WorkAssignment::Backtrack(int i)
{
if(i>=n)
{
for(int j=1;j<n;j++)
bestx[j]=x[j];
best=cx;
}
else
for(int j=i;j<n;j++)
{
cx+=c[i][x[j]];
if(cx<best)
{
Swap(x[i],x[j]);
Backtrack(i+1);
Swap(x[i],x[j]);
}
cx-=c[i][x[j]];
评论5