第一篇：2背包問(wèn)題九講之完全背包問(wèn)題
P02: 完全背包問(wèn)題
題目
有N種物品和一個(gè)容量為V的背包，每種物品都有無(wú)限件可用。第i種物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。
基本思路
這個(gè)問(wèn)題非常類似于01背包問(wèn)題，所不同的是每種物品有無(wú)限件。也就是從每種物品的角度考慮，與它相關(guān)的策略已并非取或不取兩種，而是有取0件、取1件、取2件??等很多種。如果仍然按照解01背包時(shí)的思路，令f[i][v]表示前i種物品恰放入一個(gè)容量為v的背包的最大權(quán)值。仍然可以按照每種物品不同的策略寫(xiě)出狀態(tài)轉(zhuǎn)移方程，像這樣： f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
這跟01背包問(wèn)題一樣有O(VN)個(gè)狀態(tài)需要求解，但求解每個(gè)狀態(tài)的時(shí)間已經(jīng)不是常數(shù)了，求解狀態(tài)f[i][v]的時(shí)間是O(v/c[i])，總的復(fù)雜度可以認(rèn)為是O(V*Σ(V/c[i]))，是比較大的。
將01背包問(wèn)題的基本思路加以改進(jìn)，得到了這樣一個(gè)清晰的方法。這說(shuō)明01背包問(wèn)題的方程的確是很重要，可以推及其它類型的背包問(wèn)題。但我們還是試圖改進(jìn)這個(gè)復(fù)雜度。
一個(gè)簡(jiǎn)單有效的優(yōu)化
完全背包問(wèn)題有一個(gè)很簡(jiǎn)單有效的優(yōu)化，是這樣的：若兩件物品i、j滿足c[i]<=c[j]且w[i]>=w[j]，則將物品j去掉，不用考慮。這個(gè)優(yōu)化的正確性顯然：任何情況下都可將價(jià)值小費(fèi)用高得j換成物美價(jià)廉的i，得到至少不會(huì)更差的方案。對(duì)于隨機(jī)生成的數(shù)據(jù)，這個(gè)方法往往會(huì)大大減少物品的件數(shù)，從而加快速度。然而這個(gè)并不能改善最壞情況的復(fù)雜度，因?yàn)橛锌赡芴貏e設(shè)計(jì)的數(shù)據(jù)可以一件物品也去不掉。
這個(gè)優(yōu)化可以簡(jiǎn)單的O(N^2)地實(shí)現(xiàn)，一般都可以承受。另外，針對(duì)背包問(wèn)題而言，比較不錯(cuò)的一種方法是：首先將費(fèi)用大于V的物品去掉，然后使用類似計(jì)數(shù)排序的做法，計(jì)算出費(fèi)用相同的物品中價(jià)值最高的是哪個(gè)，可以O(shè)(V+N)地完成這個(gè)優(yōu)化。這個(gè)不太重要的過(guò)程就不給出偽代碼了，希望你能獨(dú)立思考寫(xiě)出偽代碼或程序。
轉(zhuǎn)化為01背包問(wèn)題求解
既然01背包問(wèn)題是最基本的背包問(wèn)題，那么我們可以考慮把完全背包問(wèn)題轉(zhuǎn)化為01背包問(wèn)題來(lái)解。最簡(jiǎn)單的想法是，考慮到第i種物品最多選V/c[i]件，于是可以把第i種物品轉(zhuǎn)化為V/c[i]件費(fèi)用及價(jià)值均不變的物品，然后求解這個(gè)01背包問(wèn)題。這樣完全沒(méi)有改進(jìn)基本思路的時(shí)間復(fù)雜度，但這畢竟給了我們將完全背包問(wèn)題轉(zhuǎn)化為01背包問(wèn)題的思路：將一種物品拆成多件物品。
更高效的轉(zhuǎn)化方法是：把第i種物品拆成費(fèi)用為c[i]*2^k、價(jià)值為w[i]*2^k的若干件物品，其中k滿足c[i]*2^k<=V。這是二進(jìn)制的思想，因?yàn)椴还茏顑?yōu)策略選幾件第i種物品，總可以表示成若干個(gè)2^k件物品的和。這樣把每種物品拆成O(log V/c[i])件物品，是一個(gè)很大的改進(jìn)。但我們有更優(yōu)的O(VN)的算法。
O(VN)的算法
這個(gè)算法使用一維數(shù)組，先看偽代碼：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-cost]+weight}
你會(huì)發(fā)現(xiàn)，這個(gè)偽代碼與P01的偽代碼只有v的循環(huán)次序不同而已。為什么這樣一改就可行呢？首先想想為什么P01中要按照v=V..0的逆序來(lái)循環(huán)。這是因?yàn)橐ＷC第i次循環(huán)中的狀態(tài)f[i][v]是由狀態(tài)f[i-1][v-c[i]]遞推而來(lái)。換句話說(shuō)，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時(shí)，依據(jù)的是一個(gè)絕無(wú)已經(jīng)選入第i件物品的子結(jié)果f[i-1][v-c[i]]。而現(xiàn)在完全背包的特點(diǎn)恰是每種物品可選無(wú)限件，所以在考慮“加選一件第i種物品”這種策略時(shí)，卻正需要一個(gè)可能已選入第i種物品的子結(jié)果f[i][v-c[i]]，所以就可以并且必須采用v=0..V的順序循環(huán)。這就是這個(gè)簡(jiǎn)單的程序?yàn)楹纬闪⒌牡览怼?/p>
值得一提的是，上面的偽代碼中兩層for循環(huán)的次序可以顛倒。這個(gè)結(jié)論有可能會(huì)帶來(lái)算法時(shí)間常數(shù)上的優(yōu)化。
這個(gè)算法也可以以另外的思路得出。例如，將基本思路中求解f[i][v-c[i]]的狀態(tài)轉(zhuǎn)移方程顯式地寫(xiě)出來(lái)，代入原方程中，會(huì)發(fā)現(xiàn)該
方程可以等價(jià)地變形成這種形式：
f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}
將這個(gè)方程用一維數(shù)組實(shí)現(xiàn)，便得到了上面的偽代碼。
最后抽象出處理一件完全背包類物品的過(guò)程偽代碼：
procedure CompletePack(cost,weight)
for v=cost..V
f[v]=max{f[v],f[v-c[i]]+w[i]}
總結(jié)
完全背包問(wèn)題也是一個(gè)相當(dāng)基礎(chǔ)的背包問(wèn)題，它有兩個(gè)狀態(tài)轉(zhuǎn)移方程，分別在“基本思路”以及“O(VN)的算法“的小節(jié)中給出。希望你能夠?qū)@兩個(gè)狀態(tài)轉(zhuǎn)移方程都仔細(xì)地體會(huì)，不僅記住，也要弄明白它們是怎么得出來(lái)的，最好能夠自己想一種得到這些方程的方法。事實(shí)上，對(duì)每一道動(dòng)態(tài)規(guī)劃題目都思考其方程的意義以及如何得來(lái)，是加深對(duì)動(dòng)態(tài)規(guī)劃的理解、提高動(dòng)態(tài)規(guī)劃功力的好方法。
第二篇：c語(yǔ)言版背包問(wèn)題
#include
int c[10][100];/*對(duì)應(yīng)每種情況的最大價(jià)值*/
int knapsack(int m,int n){
int i,j,w[10],p[10];
printf(“請(qǐng)輸入每個(gè)物品的重量,價(jià)值：n”);
for(i=1;i<=n;i++)
scanf(“%d,%d”,&w[i],&p[i]);
for(i=0;i<10;i++)
for(j=0;j<100;j++)
c[i][j]=0;/*初始化數(shù)組*/
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(w[i]<=j)/*如果當(dāng)前物品的容量小于背包容量*/
{
if(p[i]+c[i-1][j-w[i]]>c[i-1][j])
/*如果本物品的價(jià)值加上背包剩下的空間能放的物品的價(jià)值*/
/*大于上一次選擇的最佳方案則更新c[i][j]*/
c[i][j]=p[i]+c[i-1][j-w[i]];
else
c[i][j]=c[i-1][j];
}
else c[i][j]=c[i-1][j];
}
return(c[n][m]);
}
int main(){
int m,n;int i,j;
printf(“請(qǐng)輸入背包的承重量,物品的總個(gè)數(shù)：n”);
scanf(“%d,%d”,&m,&n);
printf(“旅行者背包能裝的最大總價(jià)值為%d”,knapsack(m,n));
printf(“n”);
return 0;}
第三篇：P07-有依賴的背包問(wèn)題
P07: 有依賴的背包問(wèn)題 簡(jiǎn)化的問(wèn)題
這種背包問(wèn)題的物品間存在某種“依賴”的關(guān)系。也就是說(shuō)，i依賴于j，表示若選物品i，則必須選物品j。為了簡(jiǎn)化起見(jiàn)，我們先設(shè)沒(méi)有某個(gè)物品既依賴于別的物品，又被別的物品所依賴；另外，沒(méi)有某件物品同時(shí)依賴多件物品。算法
這個(gè)問(wèn)題由NOIP2006金明的預(yù)算方案一題擴(kuò)展而來(lái)。遵從該題的提法，將不依賴于別的物品的物品稱為“主件”，依賴于某主件的物品稱為“附件”。由這個(gè)問(wèn)題的簡(jiǎn)化條件可知所有的物品由若干主件和依賴于每個(gè)主件的一個(gè)附件集合組成。按照背包問(wèn)題的一般思路，僅考慮一個(gè)主件和它的附件集合。可是，可用的策略非常多，包括：一個(gè)也不選，僅選擇主件，選擇主件后再選擇一個(gè)附件，選擇 主件后再選擇兩個(gè)附件??無(wú)法用狀態(tài)轉(zhuǎn)移方程來(lái)表示如此多的策略。（事實(shí)上，設(shè)有n個(gè)附件，則策略有2^n+1個(gè)，為指數(shù)級(jí)。）
考慮到所有這些策略都是互斥的（也就是說(shuō)，你只能選擇一種策略），所以一個(gè)主件和它的附件集合實(shí)際上對(duì)應(yīng)于P06中的一個(gè)物品組，每個(gè)選擇了主件又選擇了若干個(gè)附件的策略對(duì)應(yīng)于這個(gè)物品組中的一個(gè)物品，其費(fèi)用和價(jià)值都是這個(gè)策略中的物品的值的和。但僅僅是這一步轉(zhuǎn)化并不能給出一個(gè)好的算法，因?yàn)槲锲方M中的物品還是像原問(wèn)題的策略一樣多。
再考慮P06中的一句話： 可以對(duì)每組中的物品應(yīng)用P02中“一個(gè)簡(jiǎn)單有效的優(yōu)化”。這提示我們，對(duì)于一個(gè)物品組中的物品，所有費(fèi)用相同的物品只留一個(gè)價(jià)值最大的，不影響結(jié)果。所以，我們可以對(duì)主件i的“附件集合”先進(jìn)行一次01背包，得到費(fèi)用依次為0..V-c[i]所有這些值時(shí)相應(yīng)的最大價(jià)值f'[0..V-c[i]]。那么這個(gè)主件及它的附件集合相當(dāng)于V-c[i]+1個(gè)物品的物品 組，其中費(fèi)用為c[i]+k的物品的價(jià)值為f'[k]+w[i]。也就是說(shuō)原來(lái)指數(shù)級(jí)的策略中有很多策略都是冗余的，通過(guò)一次01背包后，將主件i轉(zhuǎn)化為 V-c[i]+1個(gè)物品的物品組，就可以直接應(yīng)用P06的算法解決問(wèn)題了。
較一般的問(wèn)題
更一般的問(wèn)題是：依賴關(guān)系以圖論中“森林”的形式給出（森林即多叉樹(shù)的集合），也就是說(shuō)，主件的附件仍然可以具有自己的附件集合，限制只是每個(gè)物品最多只依賴于一個(gè)物品（只有一個(gè)主件）且不出現(xiàn)循環(huán)依賴。
解決這個(gè)問(wèn)題仍然可以用將每個(gè)主件及其附件集合轉(zhuǎn)化為物品組的方式。唯一不同的是，由于附件可能還有附件，就不能將每個(gè)附件都看作一個(gè)一般的01背 包中的物品了。若這個(gè)附件也有附件集合，則它必定要被先轉(zhuǎn)化為物品組，然后用分組的背包問(wèn)題解出主件及其附件集合所對(duì)應(yīng)的附件組中各個(gè)費(fèi)用的附件所對(duì)應(yīng)的價(jià)值。
事實(shí)上，這是一種樹(shù)形DP，其特點(diǎn)是每個(gè)父節(jié)點(diǎn)都需要對(duì)它的各個(gè)兒子的屬性進(jìn)行一次DP以求得自己的相關(guān)屬性。這已經(jīng)觸及到了“泛化物品”的思想。看完P(guān)08后，你會(huì)發(fā)現(xiàn)這個(gè)“依賴關(guān)系樹(shù)”每一個(gè)子樹(shù)都等價(jià)于一件泛化物品，求某節(jié)點(diǎn)為根的子樹(shù)對(duì)應(yīng)的泛化物品相當(dāng)于求其所有兒子的對(duì)應(yīng)的泛化物品之和。
小結(jié)
NOIP2006的那道背包問(wèn)題我做得很失敗，寫(xiě)了上百行的代碼，卻一分未得。后來(lái)我通過(guò)思考發(fā)現(xiàn)通過(guò)引入“物品組” 和“依賴”的概念可以加深對(duì)這題的理解，還可以解決它的推廣問(wèn)題。用物品組的思想考慮那題中極其特殊的依賴關(guān)系：物品不能既作主件又作附件，每個(gè)主件最多 有兩個(gè)附件，可以發(fā)現(xiàn)一個(gè)主件和它的兩個(gè)附件等價(jià)于一個(gè)由四個(gè)物品組成的物品組，這便揭示了問(wèn)題的某種本質(zhì)。
我想說(shuō)：失敗不是什么丟人的事情，從失敗中全無(wú)收獲才是。
第四篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 背包問(wèn)題的求解
2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
背包問(wèn)題的求解
摘要 組合優(yōu)化問(wèn)題的求解方法研究已經(jīng)成為了當(dāng)前眾多科學(xué)關(guān)注的焦點(diǎn)，這不僅在于其內(nèi)在的復(fù)雜性有著重要的理論價(jià)值，同時(shí)也在于它們能在現(xiàn)實(shí)生活中廣泛的應(yīng)用。背包問(wèn)題是一個(gè)典型的組合優(yōu)化問(wèn)題，本課程設(shè)計(jì)用遞歸算法求解背包問(wèn)題，就是在資源有限的條件下，追求總的最大收益的資源有效分配問(wèn)題。關(guān)鍵詞 背包問(wèn)題；
遞歸算法；
1問(wèn)題描述
1.1問(wèn)題描述
背包問(wèn)題：設(shè)有不同價(jià)值、不同重量的物品n件，求從這n件物品中選取一部分的方案，使選中物品的總重量不超過(guò)指定的限制重量，但選中物品的價(jià)值之和最大。
1.2基本思想
（1）分別輸入n件物品的重量和價(jià)值。（2）采用遞歸尋找物品的方案。
（3）輸出最佳的裝填方案，包括選中的是哪幾種物品，總價(jià)值為多少。
2問(wèn)題分析
背包問(wèn)題的求解是一個(gè)很經(jīng)典的案例。對(duì)于它的分析與研究已經(jīng)到達(dá)了一定的深度，解決這個(gè)問(wèn)題有很多很多的辦法。其中遞歸方法是比較簡(jiǎn)化程序，也比較難理解的一個(gè)。
設(shè)n件物品的重量分別為w0,w1,?,wn-1,物品的價(jià)值分別為v0,v1,?,vn-1。采用遞歸尋找物品的選擇方案。設(shè)前面已經(jīng)有了多種選擇方案，并保留了其中最大的選擇方案于數(shù)組option[],設(shè)方案的的總價(jià)值存于變量maxv,當(dāng)前正在考察新方案其物品選擇情況保存于數(shù)組cop[]，嘉定當(dāng)前方案已經(jīng)考慮了前i-1件物品，現(xiàn)在正在考慮第i件物品；當(dāng)前方案已經(jīng)包含的物品的質(zhì)量之和為tw;至此，若其余物品都選擇可能的話，本方案能達(dá)到的總價(jià)值的期望值設(shè)為tv，算法引入tv是當(dāng)一旦當(dāng)前方案的總價(jià)值的期望值也小于前面方案的總價(jià)值maxv時(shí)，急需考察當(dāng)前方案變成無(wú)意義的工作，應(yīng)終止當(dāng)前方案，立即去考察下一個(gè)方案。因?yàn)楫?dāng)方案的總價(jià)值不比maxv大時(shí)，該方案不會(huì)不會(huì)再被考察。這同時(shí)保證函數(shù)后找到的方案一定會(huì)比前面的方案更好。2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 對(duì)于第i件物品的選擇有兩種可能：
（1）物品i被選擇，這種可能性僅當(dāng)包含它不會(huì)超過(guò)方案總重量的限制時(shí)才是可行的。選中后，繼續(xù)遞歸去考慮其余物品的選擇；
（2）物品i不被選擇，這種可能性僅當(dāng)不包物品i也有可能會(huì)找大價(jià)值更大的方案的情況。
就此，通過(guò)不斷地對(duì)從第一件開(kāi)始的物品到第n件物品進(jìn)行選擇或是不選擇，從而從各個(gè)方案的比較中選擇出最優(yōu)方案。
采用option[]和cop[]兩個(gè)數(shù)組，來(lái)輔助完成遞歸尋找物品的選擇方案。數(shù)組option[]起到一個(gè)“旗幟”作用，用來(lái)區(qū)別于未被選擇的物品，從而達(dá)到輸出被選擇的函數(shù)。而cop[]則像是一個(gè)中間變量，它在遞歸過(guò)程中不斷地發(fā)生變化，將有效的最終數(shù)據(jù)傳輸給數(shù)組option[]，起到一個(gè)橋梁作用。
3數(shù)據(jù)結(jié)構(gòu)描述
背包問(wèn)題結(jié)構(gòu)體：
struct{
int weight;
int value;
}a[N];4算法設(shè)計(jì)
4.1程序流程圖
2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
圖4-1 程序流程圖
4.2算法設(shè)計(jì)
根據(jù)問(wèn)題分析中的思想寫(xiě)出遞歸算法如下：
find（物品當(dāng)前選擇已達(dá)到的重量和tw,本方案可能達(dá)到的總價(jià)值為tv）｛
/*考慮物品i包含在當(dāng)前方案中的可能性*/ if（包含物品i是可接受的）｛
將物品i包含在當(dāng)前方案中；
if(i 以當(dāng)前方案作為臨時(shí)最佳方案保存； 恢復(fù)物品i不包含狀態(tài)； ｝ 2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) /*考慮物品i不包含在當(dāng)前方案中的可能性*/ if（不包含物品i僅是可考慮的） if(i 以當(dāng)前方案作為臨時(shí)最佳方案保存； ｝ void find(int i,int tw,int tv) { int k;if(tw+a[i].weight<=limitw) /*物品i包含在當(dāng)前方案的可能性*/ { cop[i]=1;if(i /*物品i不包含在當(dāng)前方案的可能性*/ if(i opion[k]=cop[k];maxv=tv-a[i].value;} } 5詳細(xì)程序清單 詳細(xì)程序清單見(jiàn)附錄。 6程序運(yùn)行結(jié)果 背包問(wèn)題求解界面如圖6-1所示。 圖6-1 背包問(wèn)題求解界面 程序調(diào)試成功。 在課程設(shè)計(jì)代碼調(diào)試過(guò)程中也出了不少差錯(cuò)，比如頭文件很容易忽略，同學(xué)指出才發(fā)現(xiàn)；一些符號(hào)像“；”也很容易丟掉或是中英文格式不正確；甚至像0和 O這種小錯(cuò)誤有時(shí)也會(huì)發(fā)生，在經(jīng)過(guò)調(diào)試和完善程序的過(guò)程中，這些錯(cuò)誤已經(jīng)全部改正。在此過(guò)程中我們學(xué)到了不少調(diào)試的技巧，極大得豐富了編程的知識(shí)，這些在程序的優(yōu)化方面幫助很大。 7心得體會(huì) 通過(guò)此次課程設(shè)計(jì)的實(shí)踐，感觸較深。不僅使我們加深了對(duì)書(shū)本知識(shí)的理解，而且鍛煉了我們編寫(xiě)程序、調(diào)試程序的能力。同時(shí)，此次課程設(shè)計(jì)也充分彌補(bǔ)了課堂教學(xué)中知識(shí)的缺陷。這次課程設(shè)計(jì)由于時(shí)間有限，對(duì)有些地方考慮的還不夠周到。 2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 在本課題中，我們研究了如何用遞歸算法求解組合優(yōu)化問(wèn)題中的背包問(wèn)題，背包問(wèn)題是一個(gè)典型的組合優(yōu)化問(wèn)題，就是在資源有限的條件下，追求總的最大收益的資源有效分配問(wèn)題。所以我們?cè)囍盟鶎W(xué)的數(shù)據(jù)結(jié)構(gòu)知識(shí)以及遞歸法來(lái)解決普通的背包問(wèn)題。背包問(wèn)題的遞歸思想確實(shí)有點(diǎn)難以理解，為了理解這個(gè)思想，我們確實(shí)花了很長(zhǎng)時(shí)間，不過(guò)很高興最后經(jīng)過(guò)我們的討論掌握了這個(gè)思想。 參考文獻(xiàn) [1] 徐孝凱.數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn).北京：清華大學(xué)出版社，2002:100-132 [2] 張乃笑.數(shù)據(jù)結(jié)構(gòu)與算法.北京：電子工業(yè)出版，2000:3-5 [3] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.北京： 清華大學(xué)出版社，2002:100-132 [4] 李春葆.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言篇）習(xí)題與解析（修訂版）.北京：清華大學(xué)出版，2000:45-66 Knapsack problem solving Li Shuai Zhu Zhili Kong Rongong(Department of Physics ,Dezhou University,Dezhou,253023)Abstract Combinatorial optimization problem solving method has become the focus of attention of the scientific, it not only lies in its inherent complexity has the important theoretical value, but also that they can in real life widely.Knapsack problem is a typical combinatorial optimization problem, the course is designed to use recursion algorithm for solving knapsack problem was under the condition of limited resources, the pursuit of the maximum benefit of the resources allocation problem.Keywords knapsack problem;recursive algorithm 2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 附錄：詳細(xì)程序清單 #include /*可實(shí)現(xiàn)最大總價(jià)值*/ int opion[N]，cop[N]; struct{ int weight; int value; }a[N];int n; void find(int i,int tw,int tv) { int k;if(tw+a[i].weight<=limitw) { cop[i]=1;if(i /*方案的選擇*/ /*當(dāng)前方案的選擇*/ /*背包問(wèn)題結(jié)構(gòu)體*/ /*物品種數(shù)*/ /*物品i包含在當(dāng)前方案的可能性*/ 7 2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) if(tv-a[i].value>maxv) /*物品i不包含在當(dāng)前方案的可能性*/ if(i 第%d種物品（重量，價(jià)值）：”,k+1);scanf(“%d,%d”,&w,&v);a[k].weight=w;a[k].value=v;totv+=v;} printf(“背包所能承受的總重量：”);scanf(“%d”,&limitw);maxv=0;for(k=0;k printf(“最佳裝填方案是：n”);for(k=0;k 0-1背包問(wèn)題 問(wèn)題描述 給定n種物品和一背包，物品i的重量是wi，其價(jià)值是pi，背包的容量是M，如何選擇裝入背包中的物品總價(jià)值最大？ 問(wèn)題分析 記c[i][m] 表示前i個(gè)物品，在背包容量大小為m的情況下，最大的裝載量。如果不放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入容量為m的背包中”，價(jià)值為c[i-1][m]；如果放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為m-w[i]的背包中”，此時(shí)能獲得的最大價(jià)值就是c[i-1][m-w[i]]再加上通過(guò)放入第i件物品獲得的價(jià)值p[i]。因?yàn)楸嘲畲笕萘縈未知。所以，我們的程序要從1到M一個(gè)一個(gè)的試。比如，開(kāi)始任選N件物品的一個(gè)?？磳?duì)應(yīng)M的背包，能不能放進(jìn)去，如果能放進(jìn)去，并且還有多的空間，則多出來(lái)的空間里能放N-1物品中的最大價(jià)值。從以上最大價(jià)值的構(gòu)造過(guò)程中可以看出： c(n,m)=max{c(n-1,m), c(n-1,m-w[n])+p(n)其中c[i-1][m] 表示第i件物品不裝入背包中，而c[i-1][m-w[i]] + p[i] 表示第i件物品裝入背包中。偽代碼： 1.最優(yōu)值max(x1*p1+x2*p2+??xn*pn)int knapsack(int m,int n,int *w,int *p){ bool a; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(w[i]<=j) { a=p[i]+c[i-1][j-w[i]]>c[i-1][j]; c[i][j]=a?p[i]+c[i-1][j-w[i]]:c[i-1][j]; //前者表示放i物品，后者表示不放i物品 } else //i號(hào)物品重量大于剩余容量，不能再放i號(hào)物品 c[i][j]=c[i-1][j]; } return(c[n][m]);//最后的值即為最優(yōu)值，返回主函數(shù) } 2.求最優(yōu)n元0-1向量(x1,x2,x3??,xn)int getbest(int m,int n,int *w,int *p){ if(n==0)return 0;//遞歸，每次遞歸n減1，n為0時(shí)退出 if(w[n]>m) { x[n]=0; getbest(m,n-1,w,p); } else { //如果c[n][m]由p[n]+c[n-1][m-w[n]]而來(lái),則x[n]=1; //如果c[n][m]由c[n-1][m]]而來(lái),則x[n]=0; x[n]=c[n-1][m]<=p[n]+c[n-1][m-w[n]]; if(x[n]) getbest(m-w[n],n-1,w,p); else getbest(m,n-1,w,p); } } 程序： #include bool a; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(w[i]<=j) { a=p[i]+c[i-1][j-w[i]]>c[i-1][j]; c[i][j]=a?p[i]+c[i-1][j-w[i]]:c[i-1][j]; //前者表示放i物品，后者表示不放i物品 } else //i號(hào)物品重量大于剩余容量，不能再放i號(hào)物品 c[i][j]=c[i-1][j]; } return(c[n][m]);//最后的值即為最優(yōu)值，返回主函數(shù) } //求最優(yōu)n元0-1向量(x1,x2,x3……,xn)int getbest(int m,int n,int *w,int *p){ if(n==0)return 0;//遞歸，每次遞歸n減1，n為0時(shí)退出 if(w[n]>m) { x[n]=0; getbest(m,n-1,w,p); } else { //如果c[n][m]由p[n]+c[n-1][m-w[n]]而來(lái),則x[n]=1; //如果c[n][m]由c[n-1][m]]而來(lái),則x[n]=0; x[n]=c[n-1][m]<=p[n]+c[n-1][m-w[n]]; if(x[n]) getbest(m-w[n],n-1,w,p); else getbest(m,n-1,w,p); } } void main(){ int m,n;int *w=NULL; int *p=NULL; printf(“輸入背包容量和貨物個(gè)數(shù)：”); scanf(“%d%d”,&m,&n);p=(int *)calloc(n,sizeof(int));//分配n*sizeof(int)的內(nèi)存大小，存取n個(gè)物品的價(jià)格 w=(int *)calloc(n,sizeof(int));//分配n*sizeof(int)的內(nèi)存大小，存取n個(gè)物品的質(zhì)量 if(!p||!w)//檢測(cè)分配是否成功 { printf(“Not Enough Memory!n”); exit(1);//分配失敗，退出 } for(int i=1;i printf(“物品x%d的重量和價(jià)值：”,i); scanf(“%d%d”,w+i,p+i);} printf(“n總價(jià)值最大為：%d”,knapsack(m,n,w,p)); printf(“n”); for(i=0;i<=n;i++)//打印執(zhí)行動(dòng)態(tài)規(guī)劃每步的值 for(int j=0;j<=m;j++) { printf(“%3d ”,c[i][j]); if(j==m) printf(“n”); } getbest(m,n,w,p); printf(“最優(yōu)n元0-1向量為：n”); for(i=1;i<=n;i++) printf(“x%d ”,i); printf(“n”); //打印最優(yōu)n元0-1向量(x1,x2,x3……,xn) for(i=1;i<=n;i++) printf(“%-4d”,x[i]); printf(“n”);} 運(yùn)行結(jié)果：第五篇：0-1背包問(wèn)題c語(yǔ)言程序
![下載2背包問(wèn)題九講之完全背包問(wèn)題[優(yōu)秀范文五篇]word格式文檔](http://static.xiexiebang.com/skin/default/images/icon_word.png){kind=icon}
點(diǎn)擊咨詢 