01背包問(wèn)題：

1.遞歸思想

0- 1 背包問(wèn)題如果采用遞歸算法來(lái)描述則非常清楚明白, 它的算法根本思想是假設(shè)用布爾函數(shù)
knap( s, n) 表示n 件物品放入可容質(zhì)量為s 的背包中是否有解( 當(dāng)knap 函數(shù)的值為真時(shí)

說(shuō)明問(wèn)題有解,其值為假時(shí)無(wú)解) . 我們可以通過(guò)輸入s 和n 的值, 根據(jù)它們的值可分為以下幾種情況討論:

( 1) 當(dāng)s= 0時(shí)可知問(wèn)題有解, 即函數(shù)knap( s, n) 的值為true; ( 2) 當(dāng)s< 0 時(shí)這時(shí)不可能,

所以函數(shù)值為false; ( 3) 當(dāng)輸入的s> 0 且n< 1 時(shí)即總物品的件數(shù)不足1, 這時(shí)函數(shù)值為false,

只有s> 0 且n \1 時(shí)才符合實(shí)際情況,這時(shí)又分為兩種情況: ( 1) 選擇的一組物體中不包括Wn

則knap( s, n) 的解就是knap( s, n- 1) 的解. ( 2) 選擇的一組物體中包括Wn 則knap( s, n) 的解

就是knap( s- Wn, n- 1) 的解. 這樣一組Wn 的值就是問(wèn)題的最佳解. 這樣就將規(guī)模為n 的問(wèn)題轉(zhuǎn)化為

規(guī)模為n- 1 的問(wèn)題. 綜上所述0- 1 背包問(wèn)題的遞歸函數(shù)定義為:
knap( s, n) =∕true, s= 0
???????????? ︳false, s< 0
???????????? ︳false, s> 0 且n< 1
????????????? \knap( s, n- 1) 或knap( s- Wn, n- 1) , s> 0 且n>= 1
采用此法求解0- 1 背包問(wèn)題的時(shí)間復(fù)雜度為O( n) . 上述算法對(duì)于所有物品中的某幾件恰能裝滿(mǎn)背包
時(shí)能準(zhǔn)確求出最佳解. 但一般情況是對(duì)于某一些物品無(wú)論怎么裝都不能裝滿(mǎn)背包, 必須要按背包的最大
容量來(lái)裝. 如物品件數(shù)為4, 其質(zhì)量分別為: 10, 2, 5, 4, 背包的容量為20, 則這四件物品無(wú)論怎么放都不
能恰好裝滿(mǎn)背包, 但應(yīng)能最大限度裝, 即必須裝下10, 5, 4 這三件物品, 這樣就能得到最大質(zhì)量19. 對(duì)于
這種裝不滿(mǎn)的背包它的解決辦法是這樣的: 按所有物品的組合質(zhì)量最大的方法裝背包, 如果還裝不滿(mǎn),
則我們可以考慮剩余空間能否裝下所有物品中最小的那件, 如果連最小的都裝不下了則說(shuō)明這樣得到
的解是最佳解, 問(wèn)題解決. 這樣我們必須先找出所有n 件物品中質(zhì)量最小的那件( 它的質(zhì)量為Min) , 但
是為了問(wèn)題的解決我們不能增加運(yùn)算次數(shù)太多, 并且必須運(yùn)用上述遞歸函數(shù). 那么我們可通過(guò)修改s 的
值即背包的容量, 從背包容量s 中減去k( 它的值是從0 到Min- 1 之間的一個(gè)整數(shù)值) , 再調(diào)用遞歸函
數(shù). 當(dāng)k= 0 時(shí)即能裝滿(mǎn)背包, 其它值也能保證背包能最大限度裝滿(mǎn), 這樣所有問(wèn)題都解決了.

?

①例題一：

?

簡(jiǎn)單背包問(wèn)題
Time Limit:?? 1000MS?????? Memory Limit:?? 65535KB?
Submissions:?? 2217?????? Accepted:?? 408

?

Description?
設(shè)有一個(gè)背包可以放入的物品重量為S，現(xiàn)有n件物品，重量分別是w1，w2，w3，…wn。?
問(wèn)能否從這n件物品中選擇若干件放入背包中，使得放入的重量之和正好為S。?
如果有滿(mǎn)足條件的選擇，則此背包有解，否則此背包問(wèn)題無(wú)解。
??
Input輸入數(shù)據(jù)有多行，包括放入的物品重量為s，物品的件數(shù)n，以及每件物品的重量（輸入數(shù)據(jù)均為正整數(shù)）
多組測(cè)試數(shù)據(jù)。?
Output對(duì)于每個(gè)測(cè)試實(shí)例，若滿(mǎn)足條件則輸出“YES”，若不滿(mǎn)足則輸出“NO“?
Sample Input
20 5
1 3 5 7 9
Sample Output
YES

# include<stdio.h> # include<string.h> int date[1005]; int f(int w,int s) {if(w==0) return 1;//正好if(w<0||w>0 &&s==0) return 0;if(f(w-date[s],s-1)) return 1;//退出來(lái)再選下一個(gè) return f(w,s-1);//選擇下一個(gè) }int main() {int i,Weight,n;while(scanf("%d %d",&Weight,&n)!=EOF){memset(date,0,sizeof(date));for(i=1;i<=n;i++)scanf("%d",&date[i]);if(f(Weight,n))printf("YES\n");else printf("NO\n");}return 0; } }

?

2.貪心算法

用貪心法設(shè)計(jì)算法的特點(diǎn)是一步一步地進(jìn)行，根據(jù)某個(gè)優(yōu)化測(cè)度（可能是目標(biāo)函數(shù)，也可能不是目標(biāo)函數(shù)），每一步上都要保證能獲得局部最優(yōu)解。

每一步只考慮一個(gè)數(shù)據(jù)，它的選取應(yīng)滿(mǎn)足局部?jī)?yōu)化條件。若下一個(gè)數(shù)據(jù)與部分最優(yōu)解連在一起不再是可行解時(shí)，就不把該數(shù)據(jù)添加到部分解中，

直到把所有數(shù)據(jù)枚舉完，或者不能再添加為止。

#include<iostream> #include<algorithm> using namespace std; struct good//表示物品的結(jié)構(gòu)體 {double p;//價(jià)值double w;//重量double r;//價(jià)值與重量的比 }; good a[2000]; bool bigger(good a,good b) {if(a.r==b.r)return a.w<b.w;else return a.r>b.r; } int main() { double s,value,m; int i,n;cin>>m>>n;//讀入包的容量和物品個(gè)數(shù)for (i=0;i<n;i++){cin>>a[i].w>>a[i].p;a[i].r=a[i].p/a[i].w;}sort(a,a+n,bigger);//調(diào)用sort排序函數(shù)，按照價(jià)值與重量比和質(zhì)量排序貪心s=0;//包內(nèi)現(xiàn)存貨品的重量value=0;//包內(nèi)現(xiàn)存貨品總價(jià)值for (i=0;i<n;i++)if(s+a[i].w<=m){value+=a[i].p;s+=a[i].w;} cout<<"The total value is "<<value<<endl;//輸出結(jié)果return 0; }

但仔細(xì)想就會(huì)發(fā)現(xiàn)有個(gè)很大的問(wèn)題，
10 4
5 10
8 16
5 5
10 10
就會(huì)出問(wèn)題，被裝進(jìn)去就不會(huì)拿出來(lái)，可見(jiàn)“拿來(lái)主義”行不通！
接下來(lái)介紹另一種算法：動(dòng)規(guī)

?

3.動(dòng)態(tài)規(guī)劃【正解】

有N件物品和一個(gè)容量為V的背包。第i件物品的體積是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。
狀態(tài)轉(zhuǎn)移方程：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}?
這個(gè)方程非常重要，基本上所有跟背包相關(guān)的問(wèn)題的方程都是由它衍生出來(lái)的?
偽碼：
??for i=1..N?
???for v=V..0?
????f[v]=max{f[v],f[v-c[i]]+w[i]};
如果不放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”，
價(jià)值為f[i-1][v]；
如果放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，
此時(shí)能獲得的最大價(jià)值就是f[i-1][v-c[i]]再加上通過(guò)放入第i件物品獲得的價(jià)值w[i]。

②例題二：
采藥

Time Limit:?? 1000MS?????? Memory Limit:?? 65535KB?
Submissions:?? 155?????? Accepted:?? 50

Description辰辰是個(gè)天資聰穎的孩子，他的夢(mèng)想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對(duì)他說(shuō)：“孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大。”
如果你是辰辰，你能完成這個(gè)任務(wù)嗎？??
Input輸入的第一行有兩個(gè)整數(shù)T（1 <= T <= 1000）和M（1 <= M <= 100），用一個(gè)空格隔開(kāi)，T代表總共能夠用來(lái)采藥的時(shí)間，M代表山洞里的草藥的數(shù)目。接下來(lái)的M行每行包括兩個(gè)在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)值。?
Output輸出包括一行，這一行只包含一個(gè)整數(shù)，表示在規(guī)定的時(shí)間內(nèi)，可以采到的草藥的最大總價(jià)值。?
Sample Input
70 3
71 100
69 1
1 2
Sample Output
3

#include<iostream> # include<cstring> # define max(a,b) a>b?a:b using namespace std; int main() {int dp[101][1001],m,T,w[101],val[101],i,j;cin>>T>>m;for(i=1;i<=m;i++)cin>>w[i]>>val[i];memset(dp,0,sizeof(dp));for(i=1;i<=m;i++)for(j=0;j<=T;j++)//j相當(dāng)于上面說(shuō)的V-c[i]{if(j>=w[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+val[i]);//放還是不放的選擇else dp[i][j]=dp[i-1][j];}cout<<dp[m][T]<<endl;return 0; }

這里就測(cè)試一下，
10 4
5 10
8 16
5 5
10 10

轉(zhuǎn)載于:https://www.cnblogs.com/GoAhead/archive/2012/11/02/2751486.html

總結(jié)

以上是生活随笔為你收集整理的01背包问题，动态规划求解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。