跪求各位高手帮忙解决这个回溯算法题目

来源：百度知道 编辑：UC知道 时间：2024/05/21 11:07:33
假设需要将N项任务分别分配给N个工人同时完成，每个工人都可以承担这N项任务，但费用不同。假设开设C[N][N]数组，来存储N个工人承担N项任务所需的费用，其中C[i][j] 存储第i个工人承担第j项任务的费用。
请用“回溯”法求出总费用最小的一种工作安排方案。

这题最好的方法是抽象成二分图的最佳匹配问题，然后用KM算法解决
不过你既然说了要回溯，那就回溯吧

const int N=...;
int C[N][N];
int stack[N];
bool flag[N];

int Find(int depth,int cost)
{
if (depth==N) return cost;
else
{
int i;
int best;
best=0x7FFFFFFF;
for (i=0;i<N;i++)
if (flag[i])
{
int now;
flag[i]=false;
stack[depth]=i;
now=Find(depth+1,cost+C[depth][i]);
if (now!=-1 && now<best) best=now;
flag[i]=true;
}
if (best==0x7FFFFFFF) return -1;
else return best;
}
}

main()
{
//读取数据...
memset(flag,true,sizeof(flag));
printf("%d\n",Find(0,0));
}

这个程序只求出了最小的费用，你要求出方案的话在这个框架上修改就可以了