算法設(shè)計(jì)與分析期末論

1、.算法設(shè)計(jì)與分析論文學(xué)院：計(jì)算機(jī)學(xué)院專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)姓名：龔振學(xué)號(hào)：311109010212;分?jǐn)?shù)20得分一、 簡(jiǎn)答（任選兩題，2×10分=20分） 1.簡(jiǎn)述動(dòng)態(tài)規(guī)劃算法求解問(wèn)題的一般步驟。答：找出最優(yōu)解的性質(zhì)，并刻畫其機(jī)構(gòu)特征；遞歸地定義最優(yōu)值；以自底向上的方式計(jì)算出最優(yōu)值；根據(jù)計(jì)算最優(yōu)值時(shí)地帶的信息，構(gòu)造最優(yōu)解。6.簡(jiǎn)述回溯法求解問(wèn)題的一般步驟。答：(1)用回溯法解題通常包含一下3個(gè)步驟(2)針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；(3)確定易于搜索的解空間；(4)以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝反函數(shù)避免無(wú)效搜索。分?jǐn)?shù)二、算法設(shè)計(jì)與程序?qū)崿F(xiàn) （任選兩題，2×

2、;40分=80分）統(tǒng)一要求（若該題有特殊要求，會(huì)在題中給出）：1. 設(shè)計(jì)算法2. 分析計(jì)算復(fù)雜度3. 程序?qū)崿F(xiàn)4. 最后通過(guò)簡(jiǎn)例說(shuō)明程序?qū)崿F(xiàn)過(guò)程5. 需將源程序附上，程序需有必要的注釋語(yǔ)句6. 需給出程序運(yùn)行結(jié)果截圖80得分1、 工作分配問(wèn)題：設(shè)有件工作分配給個(gè)人。將工作分配給第個(gè)人所需費(fèi)用為。為每一個(gè)人分配一件不同的工作，并使總費(fèi)用達(dá)到最小。1.1設(shè)計(jì)算法工作分配按照遍歷應(yīng)該有n!種分法，從中找出所需費(fèi)用最少的費(fèi)用。這里采用遞歸的方法解決問(wèn)題對(duì)于每一條路徑所需費(fèi)用為expense=，其中表示第i建工作分配給第pi個(gè)人時(shí)所需費(fèi)用，p1pn互不相同，即每個(gè)人只能分配一件工作。在計(jì)算的時(shí)候可以設(shè)計(jì)

3、expense(i)等于分配過(guò)第i件工作后這時(shí)所達(dá)到的總費(fèi)用，分配第i+1i+1件工作，總費(fèi)用expense(i+1)=expense(i)+,當(dāng)i<n時(shí)，繼續(xù)遞歸，當(dāng)i=n時(shí)判斷本此分配的工作總費(fèi)用是否比之前保存的最低費(fèi)用小，是則把此次分配總費(fèi)用值賦給minexpense，并保存此次分配的路徑給q?？梢栽O(shè)計(jì)如下遞歸函數(shù)void workdistribute(int i,int n,int *p,int x,int cN)for(int j=1;j<=n;j+)if(xj=0)xj=1;x0+=cij;pi=j;if(i<n)workdistribute(i+1,n,p,x,

4、c);elseif(minexpense>x0|minexpense=-1)minexpense=x0;for(int k=1;k<=n;k+)qk=pk;x0-=cij;xj=0;1.2分析計(jì)算復(fù)雜度1.3程序?qū)崿F(xiàn)進(jìn)行宏定義N大小為100,在以后可以重新賦值#define N 100int qN=0;/定義全局變量q數(shù)組用來(lái)保存工作分配路徑int minexpense=-1;/定義全局變量用來(lái)保存分配中最小費(fèi)用void workdistribute(int i,int n, int p,int x,int cN);主函數(shù)void main() int n=0;int cNN;in

5、t xN=0;int pN=0;printf("ttt1.工作分配問(wèn)題nn");printf("請(qǐng)輸入人數(shù)n");scanf("%d",&n);下面用來(lái)輸入所需費(fèi)用for(int i=1;i<=n;i+)for(int j=1;j<=n;j+)scanf("%d",&cij);調(diào)用workdistribute(1,n,p,x,c);函數(shù)進(jìn)行遞歸分配工作，遞歸結(jié)束后進(jìn)行輸出最小費(fèi)用和此分法，以矩陣的形式顯示workdistribute(1,n,p,x,c);printf("%dn

6、",minexpense);此循環(huán)用來(lái)輸出最少費(fèi)用的分配方法for(int k=1;k<=n;k+)for(int j=1;j<=n;j+)if(qk!=j)printf(" ");elseprintf("%d ",ckj);printf("n");/workdistribute(i,n,p,x,c)函數(shù)設(shè)計(jì)，傳遞進(jìn)行分配的是第幾件工作i，已分配過(guò)的人X,分配的路徑p，以及費(fèi)用數(shù)組c，用X來(lái)保存已非配工作所需費(fèi)用void workdistribute(int i,int n,int *p,int x,int cN

7、)for(int j=1;j<=n;j+)if(xj=0)xj=1;x0+=cij;pi=j;if(i<n)/當(dāng)未分配完時(shí)繼續(xù)調(diào)用workdistribute(i+1,n,p,x,c);else/最后一事件分配完后，判斷此次分配是不是最小費(fèi)用if(minexpense>x0|minexpense=-1)/如果是最小分配或第一次分配，則保存此次分配數(shù)據(jù)minexpense=x0;for(int k=1;k<=n;k+)qk=pk;xj=0;x0-=cij;/返回上一層之前，先減去此事件分配的費(fèi)用1.4最后通過(guò)簡(jiǎn)例說(shuō)明程序?qū)崿F(xiàn)過(guò)程輸入事件數(shù)為3輸入費(fèi)用矩陣 C32 1 34

8、 5 21 2 1第一層第一次分配workdistribute(1,n,p,x,cN);分配過(guò)程c11,c22,c33 此時(shí)最小費(fèi)用是8 賦值給minexpense，并把1,2,3保存在q數(shù)組,最后一層遞歸返回上一次，第二中分配方式c11,c23,c32此時(shí)費(fèi)用時(shí)6，minexpense為6，1,3,2保存在q中，第一層第一次分配完畢，然后循環(huán)workdistribute(2,n,p,x,cN);第三種分配,c12,c21,c33，minexpesne=6,q:為1,3,2，第四次分配c12,c23,c31，minexpense=4，q：2,3,1第一層第二次分配完畢，然后循環(huán)workdist

9、ribute(3,n,p,x,cN);第五種分配c13,c21,c32,minexpense=4，q：2,3,1，第六種分配c13,c22,c31,minexpense=4，q：2,3,1返回主程序，輸出minexpense，q，2,3,1。輸出時(shí)輸出minexpense：4；輸出路徑時(shí)：只輸出二維數(shù)組c中第i行中第qi個(gè)數(shù)，其他輸出空格結(jié)果為 1 2 11.5源代碼注釋#include<stdio.h>#include <malloc.h>#define N 100int qN=0;/全局變量int minexpense=-1;/最小費(fèi)用void workdistri

10、bute(int i,int n, int p,int x,int cN);/遞歸函數(shù)void main() int n=0;int cNN;int xN=0;int pN=0;printf("ttt01工作分配問(wèn)題n");printf("請(qǐng)輸入人數(shù)n");scanf("%d",&n);for(int i=1;i<=n;i+)/輸入數(shù)組Cfor(int j=1;j<=n;j+)scanf("%d",&cij);workdistribute(1,n,p,x,c);/進(jìn)行分配printf(&

11、quot;%dn",minexpense);for(int k=1;k<=n;k+)for(int j=1;j<=n;j+)if(qk!=j)printf(" ");elseprintf("%d ",ckj);/輸出分配路徑printf("n");void workdistribute(int i,int n,int *p,int x,int cN)for(int j=1;j<=n;j+)/數(shù)組每一行的列循環(huán)if(xj=0)/i行j列沒(méi)分配則進(jìn)行分配xj=1;x0+=cij;pi=j;if(i<n)w

12、orkdistribute(i+1,n,p,x,c);else/判斷最后一事件分配完后，判斷此次分配是不是最小費(fèi)用if(minexpense>x0|minexpense=-1)/如果是最小分配或第一次分配，則保存此次分配數(shù)據(jù)minexpense=x0;for(int k=1;k<=n;k+)qk=pk;xj=0;x0-=cij;/當(dāng)此事件及以后的事件分配完后，/返回上事件進(jìn)行下一次分配前減去此次事件分配所需費(fèi)用1.6運(yùn)行結(jié)果2、 給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問(wèn)應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價(jià)值最大？要求對(duì)每種物品i裝入

13、背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i（要求使用遞歸法實(shí)現(xiàn)）。2.1設(shè)計(jì)算法在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有兩種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i，因此，該問(wèn)題稱為背包問(wèn)題。此問(wèn)題的形式化描述是，給定C>0,wi,vi>0，1in,要求找出n元0-1的向量(,.,),0,1,1in,使得C，而且達(dá)到最大。因此，0-1背包問(wèn)題是一個(gè)特殊的整數(shù)規(guī)劃問(wèn)題。設(shè)所給0-1背包問(wèn)題的子問(wèn)題的最優(yōu)值為m(i,j),即m(i,j)是背包容量為j,可選物品為i,i+1，···,n時(shí)0-1

14、背包問(wèn)題的最優(yōu)值。由0-1背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立如下計(jì)算m(i,j)的遞歸關(guān)系式m(i,j)= m(n,j)=2.2復(fù)雜度分析2.3程序?qū)崿F(xiàn)int knapsack(int i, int n,int v,int w,int c,int mN)if(i=n)/當(dāng)裝最低的物品時(shí)for(int j=1;j<=c;j+)if(wi<=j)mij=vi;xi=1;elsemij=0;else if(i>=1)/裝不是最底層物品時(shí)knapsack(i+1,n, v,w,c,m);/繼續(xù)遞歸，裝i層下物品for(int j=1;j<=c;j+)if(j>=wi&am

15、p;&mi+1j<=mi+1j-wi+vi)/當(dāng)背包容量不小于物品重量時(shí)的最優(yōu)放法mij=mi+1j-wi+vi;else/當(dāng)背包容量小于物品重量時(shí)mij=mi+1j;if(i=1)/當(dāng)所有物品都遍歷后，構(gòu)造最優(yōu)解traceback(i,m,w,c);return mic;/返回背包最大價(jià)值2.4程序?qū)崿F(xiàn)過(guò)程輸入時(shí)背包容量是8，物品個(gè)數(shù)是4，其重量分別是1, 4, 2, 3，價(jià)值分別為2, 1, 4, 3，主函數(shù)開始調(diào)用knapsack(1, w0,v,w,C,m),先遞歸到最下層i=n，背包容量從j=1到j(luò)=c開是循環(huán)，當(dāng)wi<=j是mij=mij=vi;xi=1;即m4

16、1m48值為0,0,3,3,3,3,3,3;返回上一層i=3,j從1循環(huán)到c時(shí)if(j>=wi&&mi+1j<=mi+1j-wi+vi)時(shí)用mij=mi+1j-wi+vi計(jì)算出mij值，反之mij=mi+1j，計(jì)算第3層時(shí)，第4層以計(jì)算出，得第三層m31m38值為 0, 4, 4, 4, 7, 7, 7, 7；然后返回第二層同樣方式得m21m28值為0, 4, 4, 4, 7, 7, 7, 7；返回到第一層，此時(shí)計(jì)算出第一層值m11m182, 4, 6, 6, 6, 7, 9, 9, 9。此時(shí)判斷條件if(i=1)成立，計(jì)算最優(yōu)解w0保存的是物體的個(gè)數(shù)n，當(dāng)i不大于

17、物品個(gè)數(shù)時(shí)，通過(guò)判斷if(mic=mi+1c，當(dāng)背包價(jià)值數(shù)組第i行最后的值于下行最后值相同，第i個(gè)物品不放，m18=9m28=7,所物品1放入，m28=m38=7,物體2不放入背包，m38=7m48=3所以物體3放入,而m58=0m48,物體4也放入，此時(shí)調(diào)用traceback(i+1,m,w,c-wi);后i=5>n=4，返回上一層，遞歸結(jié)束x1x4=1,0,1,1;回到main函數(shù)輸出背包最大價(jià)值9，以及放入物品重量和價(jià)值1,2，2,4，3,3。程序結(jié)束。2.5程序源代碼及注釋#include<stdio.h>#define N 50int knapsack(int i,

18、int n,int v,int w,int c,int mN);/計(jì)算最大價(jià)值遞歸函數(shù)int traceback(int i, int mN,int w,int c);/尋找所放物品遞歸函數(shù)int xN=0;/用來(lái)標(biāo)記物品是否被放入void main()int wN=0,vN=0;int mNN=0;int C=0,n=0;printf("tt 02.背包問(wèn)題遞歸n");printf("輸入背包容量:n");scanf("%d",&C);printf("輸入物體數(shù)量:n",&n);scanf(&qu

19、ot;%d",&n);printf("輸入物體重量和價(jià)值n");for(int i=1;i<=n;i+)scanf("%d %d",&wi,&vi);w0+;printf("最大價(jià)值為：%dn",knapsack(1, w0,v,w,C,m);printf("所放物品重量和價(jià)值為：n");printf("重量 價(jià)值n");for( i=1;i<=w0;i+)if(xi=1)printf(" %d %dn",wi,vi);/輸出所放物品重量和價(jià)值scan