|
蓝森林 http://www.lslnet.com 2006年6月6日 10:18
 [回溯法]请教一个程序的解？高程试题！
哪位大虾能帮我做出来，最重要的是能够给出解析过程，小弟我在这里先谢过啦！除了填空（3）较简单外，别的空似乎都有点难度！
[说明]
假设需要将N个任务分配给N个工人同时去完成，每个人都能承担这N个任务，但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案，在该方案中，为每个人分配1个不同的任务。
程序中，N个任务从0开始依次编号，N个工人也从0开始依次编号，主要的变量说明如下：
c[i][j]:将任务i分配给工人j的费用；
task[i]:值为0表示任务i未分配，值为j表示任务i分配给工人j；
worker[k]:值为0表示工人k未分配任务，值为1表示工人k已分配任务；
mincost:最小总费用。
[C程序]
＃include <stdio.h>;
＃define N 8 /*N 表示任务数和工人数*/
int c[N][N]；
unsigned int mincost = 65535； /*设置的初始值，大于可能的费用*/
int task[N]，temp[N]，worker[N]；
void plan(int k,unsigned int cost)
{ int i；
if（ __(1)__ && cost<mincost）{
mincost = cost；
for(i=0；i<N；i++) temp[i]=task[i]；}
else{
for(i=0；i<N；i++) /*分配任务 k*/
if (worker[i]==0 && __(2)__){
worker[i]=1；task[k]= __(3)__；
Plan( __(4)__，cost+c[k][i])；
__(5)__； task[k] = 0；
}/*if*/
}
}/*Plan*/
void main()
{ int i,j；
for(i=o；i<N；i++){ /*设置每个人任务由不同工人承担时的费用及全局数组的初值*/
worker[i]=0；task[i]=0；temp[i]=0；
for(j=0；j<n；j++)
scanf("%d",&c[i][j])；
}
Plan(0，0)； /*从任务0开始分配*/
printf("\n最小差用=%d\n"，mincost)；
for(i=0；i<N；i++)
printf("Task% is assigned to Worker%d\n",i,temp[i])；
} /*main*/ |
[回溯法]请教一个程序的解？高程试题！
和2002年高程背包问题是一个解法。 |
[回溯法]请教一个程序的解？高程试题！
[code]#include <stdio.h>;
#include <stdlib.h>;
#define N 8 /*N 表示任务数和工人数*/
int c[N][N];
unsigned int mincost = 65535; /*设置的初始值，大于可能的费用*/
int task[N];
int temp[N];
int worker[N];
void plan(int k,unsigned int cost)
{
int i;
if( [color=red]k == N[/color] && cost < mincost){
mincost = cost;
for (i = 0; i < N; i++)
temp[i] = task[i];
}else{
for (i = 0; i < N; i++)
/*分配任务 k*/
if (worker[i] == 0 && [color=red]cost + c[k][i] < mincost[/color]){
worker[i] = 1;
task[k] =[color=red] i; [/color]
plan(k + 1, cost + c[k][i]);
[color=red]worker[i] = 0;[/color]
task[k] = 0;
}/*if*/
}
}/*Plan*/
void main()
{
int i,j;
for (i = 0; i < N; i++){ /*设置每个人任务由不同工人承担时的费用及全局数组的初值*/
worker[i] = 0;
task[i] = 0;
temp[i] = 0;
}
plan(0, 0); /*从任务0开始分配*/
printf("\n最小差用=%d\n", mincost);
for (i = 0; i < N; i++){
for (j = 0; j < N; j++)
printf("%-2d ", c[i][j]);
printf("\n");
}
printf("\n\n");
for (i = 0; i < N; i++)
printf("Task%d is assigned to Worker%d\n", i, temp[i]);
}/*main*/[/code] |
[回溯法]请教一个程序的解？高程试题！
第二个空好像不对吧，答案不是这么写的，不过我也犯了和你同样的错误。
另外，能不能解释下第5个空？ |
[回溯法]请教一个程序的解？高程试题！
我觉得第二个空并不一定需要 cost + c[k][i] < mincost 只是减少了递归的次数， 实际上默认的遍历所有可能同样可以获得mincost
第五个空是为下一步循环重新将任务k 赋给下一个非空用户，由于在本次循环中已经把任务k 分给i 用户了所以要清除 |
[回溯法]请教一个程序的解？高程试题！
背包问题是无解的，至少目前是
cost + c[k][i] < mincost 的目的就是为了减少递归的次数，但实际上出现这个条件的可能并不高，因而对效率的影响有限
这个解法是O(n!)的，随着n的增大，速度会变得难以忍受。。。 |
[回溯法]请教一个程序的解？高程试题！
楼上的更正一下 有解 只是NP问题 |
[回溯法]请教一个程序的解？高程试题！
我说的有解是指P问题，即在确定图林机上多项式时间可解
在确定图林机上复杂度为指数级的算法可以认为是无解，如RSA |
| |
