資源描述：
《算法設(shè)計(jì)與分析第7講 背包問題.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、0-1背包問題給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?0-1背包問題是一個(gè)特殊的整數(shù)規(guī)劃問題。1背包問題的應(yīng)用1.一輛貨車有固定的載重量C，有n種貨物，每種貨物i的重量和價(jià)格是（wi,vi）,運(yùn)輸哪些貨物有最大的收益；2.一個(gè)計(jì)算機(jī)有內(nèi)存C,有n個(gè)程序，分別耗費(fèi)內(nèi)存及其所交費(fèi)用是（wi,vi）,調(diào)度哪些程序，使得費(fèi)用最大；2最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)所給0-1背包問題的一個(gè)最優(yōu)解是(y1,y2,…,yn),則（y2,y3,…yn）是右面的子問題的最優(yōu)解否則，存在（
2、z2,z3,..zn）,滿足約束條件，并且那么(y1,z2,z3…zn)，滿足原問題的約束，并且那么(y1,y2,…,yn)就不是原問題的最優(yōu)解了3最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)說明：一個(gè)n階的問題，可由一個(gè)n-1階的問題得到。以P(n,C)記錄一個(gè)n階，容量為C的問題,最優(yōu)價(jià)值F(n,C)，(y1,…yn)為最優(yōu)解，則如yn=1,(y1,…yn-1)是P(n-1,C-wn)的最優(yōu)解，從而F(n,C)=F(n-1,C-Wn)+vn如果yn=0,（y1,…yn-1）是P(n-1,C)的最優(yōu)解，從而F(n,C)=F(n-1,C)。因此，F(xiàn)(n,C)=ma
3、x(F(n-1,C-wn)+Vn,F(n-1,C)4遞歸樹F(n,C)=max(F(n-1,C-wn)+Vn,F(n-1,C)--------如果C<0,F(n,C)=-∞F(n,C)F(n-1,C-wn)F(n-1,C)F(n-2,C-Wn-Wn-1)F(n-2,C)F(n-2,C-wn)F(n-2,C-wn-1)動(dòng)態(tài)規(guī)劃－自底向上計(jì)算5F(n,C)=max(F(n-1,C-wn)+Vn,F(n-1,C)--------如果C<0,F(n,C)=-∞n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}c=012345678
4、910n=100666666666n=200669999999n=300669999111114n=4006699910111314n=50066991212151515回溯構(gòu)造解ifF(n,c)=F(n-1,c)xn=0,elsexn=1;ifxn=0,由F(n-1,c)繼續(xù)構(gòu)造xn-1,else由F(n-1,c-wn)構(gòu)造x5=1,x4=0,x3=0,x2=1,x1=1.算法例6復(fù)雜性計(jì)算矩陣元素需要nC次，故時(shí)間不僅與n相關(guān)，還與C相關(guān)。當(dāng)C比較大時(shí)，如C=2n,就是一個(gè)指數(shù)復(fù)雜性。那么，把C，w1,w2,…都除以某個(gè)數(shù)，時(shí)間變?。康悄?/p>
5、滿足他們除了結(jié)果都是整數(shù)才行。另外，根據(jù)遞歸樹，每一層實(shí)際上并不需要計(jì)算C個(gè)。時(shí)間還可以縮小。7結(jié)束8最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)所給0-1背包問題的子問題的最優(yōu)值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i，j)的遞歸式如下。9m(n,1),m(n,2),…m(n,C)m(n-1,1),m(n-1,2),…m(n-1,C)…..m(1,1),m(1,2),…m(1,C)其中，m(1,C)就是所求10算法Knapsack(Typev,intw[],
6、intc,intn,Type**m){jMax=min(w[n]-1,c)For(j=0;j1;i--){jmax=min(w[i]-1,c);For(j=0,j=w[1])m[1][c]=max
7、(m[1][c],m[2][c-w[1]]+v[1]);}11計(jì)算最優(yōu)值算法及其復(fù)雜性算法描述：P72算法復(fù)雜度分析：從m(i，j)的遞歸式容易看出，算法需要O(nc)計(jì)算時(shí)間。當(dāng)背包容量c很大時(shí)，算法需要的計(jì)算時(shí)間較多。例如，當(dāng)c>2n時(shí)，算法需要Ω(n2n)計(jì)算時(shí)間。實(shí)際上m(i,j)中的j跟wi相關(guān)，并不需要用到[1,C]的緊密分布,其中很多j沒有用到。12算法改進(jìn)由m(i,j)的遞歸式容易證明，在一般情況下，對(duì)每一個(gè)確定的i(1≤i≤n)，函數(shù)m(i,j)是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)。跳躍點(diǎn)是這一類函數(shù)的描述特征。在一般情況下，函數(shù)
8、m(i,j)由其全部跳躍點(diǎn)惟一確定。如圖所示。對(duì)每一個(gè)確定的i(1≤i≤n)，用一個(gè)表p[i]存儲(chǔ)函數(shù)m(i，j)的全部跳躍點(diǎn)。表p[i]可依計(jì)算m(
