?

1. 題目

2. 問(wèn)題描述：工作分配問(wèn)題，每個(gè)人做不同的工作需要支付不同的費(fèi)用，需要設(shè)計(jì)算法合理地分配工作使總費(fèi)用最小。

3. 基本的解空間圖例：

限制函數(shù)保證最后的解一定是最小值。

4. 代碼：

#include<iostream> using namespace std; #define MAX 1000 int n; int w[21][21]; int cp;//積累的工作費(fèi)用 int bestp=MAX;//最少工作費(fèi)用 int x[21];//當(dāng)前路徑 int best[21];//最少工作費(fèi)用的路徑 void swap(int a,int b) {int temp=x[a];x[a]=x[b];x[b]=temp; } void backtrack(int i) {if(i>n){//限界函數(shù)保證了一定小於bestp bestp=cp;for(int j=1;j<=n;j++)best[j]=x[j];return;}else for(int j=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]];}} } int main() {cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>w[i][j];for(int i=1;i<=n;i++)x[i]=i;cp=0;backtrack(1);cout<<bestp; return 0; }

5. 心得：算法中如何剪枝是一個(gè)比較核心的問(wèn)題，同時(shí)也要注意算法的時(shí)間復(fù)雜度。

轉(zhuǎn)載于:https://www.cnblogs.com/RS-Sakura/p/10164832.html

總結(jié)

以上是生活随笔為你收集整理的第五章实践上机报告的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。