1.實(shí)踐問(wèn)題：工作分配問(wèn)題

2.問(wèn)題描述

設(shè)有n件工作分配給n個(gè)人。將工作i分配給第j個(gè)人所需的費(fèi)用為cij 。 設(shè)計(jì)一個(gè)算法，對(duì)于給定的工作費(fèi)用，為每一個(gè)人都分配1 件不同的工作，并使總費(fèi)用達(dá)到最小。

輸入格式:

輸入數(shù)據(jù)的第一行有1 個(gè)正整數(shù)n (1≤n≤20)。接下來(lái)的n行，每行n個(gè)數(shù)，表示工作費(fèi)用。

輸出格式:

將計(jì)算出的最小總費(fèi)用輸出到屏幕。

3.算法描述

解空間：(a1,a2,a3,......,an),a1表示第一個(gè)人被分配的工作序號(hào)，以此類(lèi)推。

解空間樹(shù)如下：

剪枝：

當(dāng)前工作費(fèi)用與下一個(gè)待分配工作費(fèi)用大于已知的可行解的費(fèi)用，則無(wú)需對(duì)其及其子樹(shù)進(jìn)行遍歷，即剪枝

for(int i=t;i<=n;i++)

{?? if(sum+c[t][a[i]]>m)

{

continue;

}

else

{

sum += c[t][a[i]];

swap(a[t],a[i]);

BackTrack(t+1);

swap(a[t],a[i]);

sum -= c[t][a[i]];

}

}

4.心得體會(huì)

課堂聽(tīng)講的時(shí)候覺(jué)得剪枝已經(jīng)都理解了，但在上機(jī)自己敲代碼時(shí)，代碼不夠?qū)ΨQ(chēng)導(dǎo)致出錯(cuò)，所以錯(cuò)了很多遍，后面錯(cuò)著錯(cuò)著就理解了，現(xiàn)在對(duì)回溯法也更加熟悉，不再是紙上談兵。

總結(jié)

以上是生活随笔為你收集整理的python第五章上机实践报告_第五章实践报告 - osc_kk5bjg1i的个人空间 - OSCHINA - 中文开源技术交流社区...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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