工作分配问题

设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。设计一个算法，对于给定的工作费用，为每一个人都分配1件不同的工作，并使总费用达到最小。#includeiostreamusingnamespacestd;#defineMAX1000intn;intw[21][21];intcp;//積累的工作費用intbestp=MAX;//最少工作費用intx[21];//當前路徑intbest[21];//最少工作費用的路徑voidswap(inta,intb){inttemp=x[a];x[a]=x[b];x[b]=temp;}voidbacktrack(inti){if(in){//限界函數保證了一定小於bestpbestp=cp;for(intj=1;j=n;j++)best[j]=x[j];return;}elsefor(intj=i;j=n;j++){if(cp+w[i][x[j]]bestp){cp+=w[i][x[j]];swap(i,j);backtrack(i+1);swap(i,j);cp-=w[i][x[j]];}}}intmain(){cinn;for(inti=1;i=n;i++)for(intj=1;j=n;j++)cinw[i][j];for(inti=1;i=n;i++)x[i]=i;cp=0;backtrack(1);coutbestp;return0;}