[回溯法]请教一个程序的解？高程试题！

黑苦咖啡

哪位大虾能帮我做出来，最重要的是能够给出解析过程，小弟我在这里先谢过啦！除了填空（3）较简单外，别的空似乎都有点难度！

[说明]
　　假设需要将N个任务分配给N个工人同时去完成，每个人都能承担这N个任务，但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案，在该方案中，为每个人分配1个不同的任务。
　　程序中，N个任务从0开始依次编号，N个工人也从0开始依次编号，主要的变量说明如下：
　　c[j]:将任务i分配给工人j的费用；
　　task:值为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=task；}
　　　else{
　　　　for(i=0；i<N；i++)　　　　　/*分配任务 k*/
　　　　if (worker==0 && __(2)__){
　　　　　worker=1；task[k]= __(3)__；
　　　　　Plan( __(4)__，cost+c[k])；
　　　　　__(5)__； task[k] = 0；
　　　　}/*if*/
　　　}
　　}/*Plan*/

　　void main()
　　{ int i,j；
　　for(i=o；i<N；i++){　　　　/*设置每个人任务由不同工人承担时的费用及全局数组的初值*/
　　　worker=0；task=0；temp=0；
　　　for(j=0；j<n；j++)
　　　　scanf("%d",&c[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)；
　　}　　　　　　/*main*/

xzw077

和2002年高程背包问题是一个解法。

javacool

1. #include <stdio.h>;
   
2. #include <stdlib.h>;
   
3. 
   
4. #define N 8                        /*N 表示任务数和工人数*/
   
5. 
   
6. int c[N][N];
   
7. unsigned int mincost = 65535;                /*设置的初始值，大于可能的费用*/
   
8. int task[N];
   
9. int temp[N];
   
10. int worker[N];
    
11. 
    
12. void plan(int k,unsigned int cost)
    
13. {
    
14.         int i;
    
15.         if( [color=red]k == N[/color] && cost < mincost){
    
16.                 mincost = cost;
    
17.                 for (i = 0; i < N; i++)
    
18.                         temp[i] = task[i];
    
19.         }else{
    
20.                 for (i = 0; i < N; i++)
    
21.                         /*分配任务 k*/
    
22.                         if (worker[i] == 0 && [color=red]cost + c[k][i] < mincost[/color]){
    
23.                                 worker[i] = 1;
    
24.                                 task[k] =[color=red] i; [/color]
    
25.                                 plan(k + 1, cost + c[k][i]);
    
26.                                 [color=red]worker[i] = 0;[/color]
    
27.                                 task[k] = 0;
    
28.                         }/*if*/
    
29.         }
    
30. }/*Plan*/
    
31. 
    
32. void main()
    
33. {
    
34.         int i,j;
    
35.         for (i = 0; i < N; i++){                /*设置每个人任务由不同工人承担时的费用及全局数组的初值*/
    
36.                 worker[i] = 0;
    
37.                 task[i] = 0;
    
38.                 temp[i] = 0;
    
39.         }
    
40.         plan(0, 0); /*从任务0开始分配*/
    
41.         printf("\n最小差用=%d\n", mincost);
    
42.         for (i = 0; i < N; i++){
    
43.                 for (j = 0; j < N; j++)
    
44.                         printf("%-2d ", c[i][j]);
    
45.                 printf("\n");
    
46.         }
    
47.         printf("\n\n");
    
48.         for (i = 0; i < N; i++)
    
49.                 printf("Task%d is assigned to Worker%d\n", i, temp[i]);
    
50. }/*main*/

复制代码

黑苦咖啡

第二个空好像不对吧，答案不是这么写的，不过我也犯了和你同样的错误。
另外，能不能解释下第5个空？

javacool

我觉得第二个空并不一定需要 cost + c[k] < mincost 只是减少了递归的次数， 实际上默认的遍历所有可能同样可以获得mincost
第五个空是为下一步循环重新将任务k 赋给下一个非空用户，由于在本次循环中已经把任务k 分给i 用户了所以要清除

yzc2002

背包问题是无解的，至少目前是
cost + c[k] < mincost 的目的就是为了减少递归的次数，但实际上出现这个条件的可能并不高，因而对效率的影响有限
这个解法是O(n!)的，随着n的增大，速度会变得难以忍受。。。

javacool

楼上的更正一下 有解 只是NP问题

yzc2002

我说的有解是指P问题，即在确定图林机上多项式时间可解
在确定图林机上复杂度为指数级的算法可以认为是无解，如RSA