text1.txt

来自「算法设计课程设计中」· 文本 代码 · 共 47 行

#include<stdio.h>
#include<stdlib.h>
int p[30][30];
int r[30],n,best=0;
void compute();
void backtrack(int t)//t为递归深度 
{// 回溯函数 
     int j,temp;
     if(t>n)compute();//计算每种组合的费用 
     else
     for(j=t;j<=n;j++){
             temp=r[t];r[t]=r[j];r[j]=temp;//交换r[t],r[j] 
             backtrack(t+1);
             temp=r[t];r[t]=r[j];r[j]=temp;//r[t],r[j] 换回来 
     }
}

void compute()
{
     int i,temp;
     for(i=1,temp=0;i<=n;i++)
     temp+=p[i][r[i]];
     if(best==0)best=temp;
     if(temp<best){
     best=temp;
     //for(int i=1;i<=n;i++)bestr[i]=r[i];
     }
}

int  main()
{
     int i,j;
     for(i=0;i<30;i++)
     r[i]=i;//初始化 
     while (scanf("%d",&n)==1)
     {
           for(i=1;i<=n;i++)
           for(j=1;j<=n;j++)
           scanf("%d",&p[i][j]);
           backtrack(1);
           printf("%d\n",best);
           best=0;
     }
    // system("PAUSE");
     return 0;
}