算法設(shè)計(jì)和分析實(shí)驗(yàn)四：貪心算法求解背包問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)五：貪心算法求解背包問題實(shí)驗(yàn)內(nèi)容應(yīng)用貪心算法求解離散背包問題，分析時(shí)間復(fù)雜度。有一個(gè)承重為W的背包和n個(gè)物品，它們各自的重量和價(jià)值分別是wi和vi（1<=i<=n），設(shè) 求這些物品中最有價(jià)值的一個(gè)子集。如果每次選擇某一個(gè)物品的時(shí)候，只能全部拿走，則這一問題稱為離散（0-1）背包問題；如果每次可以拿走某一物品的任意一部分，則這一問題稱為連續(xù)背包問題。 算法思想 動(dòng)態(tài)規(guī)劃的思想： 對較小的子問題進(jìn)行一次求解，并把結(jié)果記錄下來，然后利用較小問題的解，求解出較大問題的解，直到求解出最大問題的解。引進(jìn)一個(gè)二維數(shù)組chMAXMAX，用chij記錄CH1與CH2的L

2、CS 的長度，bij記錄chij是通過哪一個(gè)子問題的值求得的，以決定搜索的方向。我們是自底向上進(jìn)行遞推計(jì)算，那么在計(jì)算chi,j之前，chi-1j-1，chi-1j與chij-1均已計(jì)算出來。此時(shí)我們根據(jù)CH1 i = CH2j還是CH1i != CH2j，就可以計(jì)算出chij。算法length(string CH1,string CH2,int bMAXMAX)/用于構(gòu)建動(dòng)態(tài)數(shù)組/輸入：兩字符竄/輸出：最長公共子序列for(i=1;i<=ch1Len;i+)/二重循環(huán)求解for(int j=1;j<=ch2Len;j+)if(CH1i-1=CH2j-1)/相等字符chij=chi

3、-1j-1+1;bij=0;else if(chi-1j>=chij-1)/上比較大chij=chi-1j;bij=1;else/左比較大chij=chij-1;bij=-1;printCS(int bMAXMAX,string x,int i,int j)/回溯求出最長子序列輸出/輸入：標(biāo)記數(shù)組/輸出：最長子序列if(i = 0 | j = 0)/邊界，返回return; if(bij = 0) printCS(b, x, i-1, j-1);/左上cout<<xi-1<<" " else if(bij = 1) printCS(b, x,

4、i-1, j);/上 else printCS(b, x, i, j-1);/左源程序/應(yīng)用貪心算法求解離散背包問題#include<iostream>using namespace std;#define MAX 100/結(jié)構(gòu)體struct Elem double W;double V;double P;int number;/順序表struct SqList Elem *elem;int length;int listsize;/構(gòu)造一個(gè)空的線性順序表void InitList_Sq(SqList &L)L.elem=(Elem *)malloc(100*sizeof(

5、Elem);L.length=0;L.listsize=100;/*/構(gòu)造背包,順序表/*void input(SqList &L)cout<<"請輸入物品的個(gè)數(shù)："cin>>L.length;for(int i=0;i<L.length;i+)cout<<"請輸入第"<<i+1<<"個(gè)物品的重量和價(jià)值："cin>>L.elemi.W>>L.elemi.V;L.elemi.P=L.elemi.V/L.elemi.W;cout<<

6、;"價(jià)值比為："<<L.elemi.P<<endl;L.elemi.number=i+1;/*/插入排序由大到小/*void inser(SqList &L) Elem inserter;int index;/inserter待插入合適位置的元素,index指示插入位置 for(int pass=1;pass<L.length;pass+) /共比較size-1輪inserter=L.elempass;/第pass輪時(shí),待插入的對象是apassindex=pass-1;while(index>=0&&inserte

7、r.P>L.elemindex.P) /尋找插入位置L.elemindex+1=L.elemindex;index-;/指針前移，再比較L.elemindex+1=inserter;/跳出while時(shí)，找到插入位置/end of forcout<<"按照價(jià)值比由大到小排列的順序?yàn)椋?quot;for(pass=0;pass<L.length;pass+)cout<<L.elempass.number<<" "cout<<endl;/*8/背包程序/采用貪心算法/根據(jù)價(jià)值和重量的比來實(shí)現(xiàn)貪心算法/*void

8、 bag(SqList L)double w,sumV=0,sumW=0;int listMAX,a=0;cout<<"請輸入背包承重量W:"cin>>w;inser(L);for(int i=0;i<L.length;i+)while(sumW+L.elemi.W<=w)sumW=sumW+L.elemi.W;sumV=sumV+L.elemi.V;lista+=L.elemi.number;cout<<"最后包里的總重量為："<<sumW<<endl;cout<<"最后包里的總價(jià)值為："<<sumV<<endl;cout<<"放到背包中的物品的序號(hào)列表為："for(i=0;i<a;i+)cout<<listi<<" "int main()cout<<"貪心算法求解背包問題"<<endl;SqList L; InitList_Sq(L);input(L);bag(L);return 0;實(shí)驗(yàn)結(jié)論1、 運(yùn)行截圖查找最長公共子序列長度時(shí)