1、實(shí)驗(yàn)二 貪心選擇算法姓名 ： 田圓圓 學(xué)號(hào)：2013125135一、實(shí)驗(yàn)?zāi)康呐c要求： 理解貪心選擇算法的思想。二、預(yù)習(xí)與準(zhǔn)備：貪心選擇算法思想：（1）貪心選擇能得到問題的最優(yōu)解，要證明我們所做的第一步選擇一定包含在一個(gè)最優(yōu)解總，即存在一個(gè)最優(yōu)解的第一步是從我們的貪心選擇開始。（2）在做出第一步貪心選擇后剩下的子問題應(yīng)該是和原問題類似的規(guī)模較小的子問題à為此我們可以用數(shù)學(xué)歸納法來證明貪心選擇能得到問題的最優(yōu)解。三、實(shí)驗(yàn)題目：1.在無向圖 G=(V,E) 中，假設(shè)每條邊 Ei 的長(zhǎng)度為 wi，找到由頂點(diǎn) V0 到其余各點(diǎn)的最短路徑。 2.背包問題給定n種物品和一個(gè)背包。物品i的重量是Wi

2、，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?3.多機(jī)調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。四、實(shí)驗(yàn)過程：1.用貪心算法求單元最短路徑問題：其中，disti：表示當(dāng)前從源到頂點(diǎn)i的最短特殊路徑長(zhǎng)度。實(shí)驗(yàn)代碼為：#include <iostream>#include <stdio.h>#include <limits.h>using namespace std;con

3、st int V = 9; /定義頂點(diǎn)個(gè)數(shù)/從未包含在SPT的集合T中，選取一個(gè)到S集合的最短距離的頂點(diǎn)。int getMinIndex(int distV, bool sptSetV) int min = INT_MAX, min_index; for (int v = 0; v < V; v+) if (sptSetv = false && distv < min) min = distv, min_index = v; return min_index;/ 打印結(jié)果void printSolution(int dist, int n) printf("

4、;Vertex Distance from Sourcen");for (int i = 0; i < V; i+)printf("%d tt %dn", i, disti);/source 代表源點(diǎn)void dijkstra(int graphVV, int source) int distV; / 存儲(chǔ)結(jié)果，從源點(diǎn)到 i的距離bool sptSetV; / sptSeti=true 如果頂點(diǎn)i包含在SPT中/ 初始化. 0代表不可達(dá)for (int i = 0; i < V; i+)disti = (graphsourcei = 0 ? INT_M

5、AX:graphsourcei);sptSeti = false;/ 源點(diǎn)，距離總是為0. 并加入SPTdistsource = 0;sptSetsource = true;/ 迭代V-1次，因此不用計(jì)算源點(diǎn)了，還剩下V-1個(gè)需要計(jì)算的頂點(diǎn)。for (int count = 0; count < V - 1; count+) / u，是T集合中，到S集合距離最小的點(diǎn)int u = getMinIndex(dist, sptSet);/ 加入SPT中sptSetu = true;/更新到V的距離。可以理解為Bellman-Ford中的松弛操作for (int v = 0; v < V

6、; v+)if (!sptSetv && graphuv && distu != INT_MAX&& distu + graphuv < distv)distv = distu + graphuv;printSolution(dist, V);int main() /* 以例子中的圖為例 */int graphVV = 0, 4, 0, 0, 0, 0, 0, 8, 0 , 4, 0, 8, 0, 0, 0, 0, 11, 0 , 0, 8, 0, 7, 0, 4, 0, 0, 2 , 0, 0, 7, 0, 9, 14, 0, 0, 0

7、, 0, 0, 0, 9, 0, 10, 0, 0, 0 , 0, 0, 4, 0, 10, 0, 2, 0, 0 , 0, 0, 0, 14, 0, 2, 0, 1, 6 , 8, 11, 0, 0, 0, 0, 1, 0, 7 , 0, 0, 2, 0, 0, 0, 6, 7, 0 ;dijkstra(graph, 0);return 0;2. 背包問題： #include<stdio.h> int f10100; /構(gòu)造最優(yōu)矩陣 void package0_1(int *w,int *v,int n,int c) int i,j; /初始化矩陣 for(i=1;i<=n

8、;i+) fi0 = 0; for(j=1;j<=c;j+) f0j = 0; for(i=1;i<=n;i+) for(j=1;j<=c;j+) /當(dāng)容量夠放入第i個(gè)物品，并且放入之后的價(jià)值要比不放大 if(wi <= j && fi-1j-wi + vi > fi-1j) fij = fi-1j-wi + vi; else fij = fi-1j; printf("最大價(jià)值: %d n",fnc); /構(gòu)造最優(yōu)解 void getResult(int n,int c,int *res,int *v,int *w) int i

9、,j; j = c; for(i=n;i>=1;i-) if(fij != fi-1j) resi = 1; j = j - wi; void main() int w6 = 0,2,2,6,5,4;/每個(gè)物品的重量 int v6 = 0,6,3,5,4,6;/每個(gè)物品的價(jià)值 int res5 = 0,0,0,0,0; int n = 5; /物品的個(gè)數(shù) int c = 10; /背包能容的重量 int i,j; package0_1(w,v,n,c); for(i=0;i<=n;i+) for(j=0;j<=c;j+) printf("%2d ",fij

10、); printf("n"); getResult(n,c,res,v,w); printf("放入背包的物品為: n"); for(i=1;i<=n;i+) if(resi = 1) printf("%d ",i); 3. 多機(jī)器調(diào)配問題：#include "stdafx.h" #include "MinHeap.h" #include <iostream> #include <fstream> using namespace std; const int N =

11、 7;/作業(yè)個(gè)數(shù) const int M = 3;/機(jī)器臺(tái)數(shù) ifstream fin("4d7.txt"); class JobNode /friend void Greedy(JobNode ,int,int); /friend int main(void); public: operator int() const return time; /private: int ID,time; ; class MachineNode /friend void Greedy(JobNode ,int,int); public: operator int() const retu

12、rn avail; /private: int ID,avail; ; template<class Type> void Greedy(Type a,int n,int m); template<class Type> void SelectSort(Type a,int n); int main() JobNode aN+1 ;/各作業(yè)所需要的處理時(shí)間 cout<<"各作業(yè)所需要的處理時(shí)間為："<<endl; for(int i=1; i<=N; i+) fin>>ai.ID>>ai.time

13、; cout<<"ID:"<<ai.ID<<",time:"<<ai.time<<endl; Greedy(a,N,M); return 0; template<class Type> void Greedy(Type a,int n,int m) if(n<=m)/機(jī)器數(shù)量比作業(yè)數(shù)量多，直接分配 cout<<"直接為每個(gè)作業(yè)分配一臺(tái)機(jī)器."<<endl; return; SelectSort(a,n);/排序，從大到小 MinHea

14、p<MachineNode> H(m); MachineNode x; for(int i=1; i<=m; i+) x.avail = 0; x.ID = i; H.Insert(x); for(int i=1; i<=n; i+) x = H.RemoveMin(); cout<<"將機(jī)器"<<x.ID<<"從"<<x.avail<<"到" <<(x.avail+ai.time)<<"的時(shí)間段分配給作業(yè)"

15、 <<ai.ID<<endl; x.avail += ai.time; H.Insert(x);/根據(jù)新的avail值將x插入Heap中適當(dāng)位置 template<class Type> void SelectSort(Type a,int n) Type temp; int max; for(int i=1;i<n;i+) max=i; for(int j=i+1;j<=n;j+) if(amax<aj) max=j; if(max != i) temp = ai; ai = amax; amax = temp; /4d7 貪心算法 多機(jī)

16、調(diào)度問題#include "stdafx.h"#include "MinHeap.h"#include <iostream> #include <fstream> using namespace std; const int N = 7;/作業(yè)個(gè)數(shù)const int M = 3;/機(jī)器臺(tái)數(shù)ifstream fin("4d7.txt");class JobNode/friend void Greedy(JobNode ,int,int);/friend int main(void);public:operator

17、 int() constreturn time;/private:int ID,time;class MachineNode/friend void Greedy(JobNode ,int,int);public:operator int() constreturn avail;/private:int ID,avail;template<class Type> void Greedy(Type a,int n,int m);template<class Type> void SelectSort(Type a,int n);int main()JobNode aN+1

18、 ;/各作業(yè)所需要的處理時(shí)間cout<<"各作業(yè)所需要的處理時(shí)間為："<<endl;for(int i=1; i<=N; i+)fin>>ai.ID>>ai.time;cout<<"ID:"<<ai.ID<<",time:"<<ai.time<<endl;Greedy(a,N,M);return 0;template<class Type> void Greedy(Type a,int n,int m)if(n

19、<=m)/機(jī)器數(shù)量比作業(yè)數(shù)量多，直接分配cout<<"直接為每個(gè)作業(yè)分配一臺(tái)機(jī)器."<<endl;return;SelectSort(a,n);/排序，從大到小MinHeap<MachineNode> H(m);MachineNode x;for(int i=1; i<=m; i+)x.avail = 0;x.ID = i;H.Insert(x);for(int i=1; i<=n; i+)x = H.RemoveMin();cout<<"將機(jī)器"<<x.ID<<&

20、quot;從"<<x.avail<<"到"<<(x.avail+ai.time)<<"的時(shí)間段分配給作業(yè)"<<ai.ID<<endl;x.avail += ai.time;H.Insert(x);/根據(jù)新的avail值將x插入Heap中適當(dāng)位置template<class Type> void SelectSort(Type a,int n)Type temp; int max; for(int i=1;i<n;i+) max=i; for(int j=i+1;j<=n;j+) if(amax<aj) max=j; if(max != i