前言：

　　背包問(wèn)題所涉及的是經(jīng)典的動(dòng)態(tài)規(guī)劃算法。因?yàn)殚L(zhǎng)時(shí)間不AC了，漸漸感覺(jué)思維也都麻了！本文將基礎(chǔ)的背包問(wèn)題做個(gè)小結(jié)，方便以后翻閱。感興趣的朋友也可以閱讀一下~
------------------------
（1）如何從n個(gè)重量和價(jià)值分別為Vi、Wi的物品中選擇一或多個(gè)放入最大容納量為S的背包使其總價(jià)值最大？

輸入：

5 10 ? （分別表示：n,S）
2 3
7 5
3 1
5 10
2 2

5 6
2 3
7 5
3 1
5 10
2 2

輸出：

15

10

分析：
f[i][j]：表示背包在存放了前i件物品占據(jù)j重量時(shí)的價(jià)值
其中，1<=i<=n,0<=j<=S;

當(dāng)我到達(dá)某一個(gè)狀態(tài)，需要選擇是否將第i件物品放入我的背包時(shí)，必須考慮值不值的問(wèn)題，即：
f[i][j] = max(f[i-1][j],f[i-1]][j-w[i]]+v[i]);

理解了上面的狀態(tài)轉(zhuǎn)移方程之后,就可以方便得出下面的偽代碼了：

　　f[0...n][0...S] <- 0 //初始化
　　for i<-1:n
　　　　for j<-w[i]:S
　　　　　　f[i][j] = max(f[i-1][j],f[i-1]][j-w[i]]+v[i]); //狀態(tài)轉(zhuǎn)移

代碼：

1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=1e3+10; 6 int f[maxn][maxn]; 7 int main(){ 8 //數(shù)據(jù)從文件讀入 9 freopen("datain.txt","r",stdin); 10 int n,S,a,b; 11 while(scanf("%d%d",&n,&S)==2){ 12 memset(f,0,sizeof(f)); 13 for(int i=1;i<=n;i++){ 14 scanf("%d%d",&a,&b); 15 for(int v=1;v<=S;v++){ 16 if(v>=a) //do not neglect 'v<a' 17 f[i][v] = max(f[i-1][v],f[i-1][v-a]+b); 18 else 19 f[i][v] = f[i-1][v]; 20 } 21 } 22 printf("%d\n",f[n][S]); 23 } 24 return 0; 25 }

以上算法的時(shí)間復(fù)雜度、空間復(fù)雜度均為：O(n*S)

f[i][j]的變化過(guò)程：

-----------------------------

| ? 0 3 3 3 3 3 3 3 3 3 ? ? ? ? ? |

| ? 0 3 3 3 3 3 5 5 8 8 ? ? ? ? ? |
| ? 0 3 3 3 4 4 5 5 8 8 ? ? ? ? ? | ?
| ? 0 3 3 3 10 10 13 13 13 14 |
| ? 0 3 3 5 10 10 13 13 15 15 |

-----------------------------

?

在深入理解了狀態(tài)轉(zhuǎn)移方程之后，我們其實(shí)還可以對(duì)空間進(jìn)行優(yōu)化，僅用f[i]表示：背包質(zhì)量達(dá)到i是獲得的價(jià)值。對(duì)應(yīng)的偽代碼如下：

　　f[0...S]<-0
　　for i<-1:n
　　　　for j<-S:w[i] //從右往左更新！
　　　　　　f[j] = max(f[j],f[j-w[i]]+v[i]);

對(duì)空間進(jìn)行優(yōu)化后的代碼：

1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=1e3+10; 6 int f[maxn]; 7 int main(){ 8 freopen("datain.txt","r",stdin); 9 int n,S,a,b; 10 while(scanf("%d%d",&n,&S)==2){ 11 memset(f,0,sizeof(f)); 12 for(int i=0;i<n;i++){ 13 scanf("%d%d",&a,&b); 14 for(int v=S;v>=a;v--){ 15 f[v] = max(f[v],f[v-a]+b); 16 } 17 } 18 printf("%d\n",f[S]); 19 } 20 return 0; 21 }

?

（2）如何從n個(gè)重量和價(jià)值分別為Vi、Wi的物品中選擇一或多個(gè)放入最大容納量為S的背包在背包剛好裝滿情況下，使其總價(jià)值最大？

1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=1e3+10; 6 int f[maxn]; 7 int main(){ 8 freopen("datain.txt","r",stdin); 9 int n,S,a,b; 10 while(scanf("%d%d",&n,&S)==2){ 11 for(int i=1;i<=S;i++) f[i]=-0xfffffff; //最小的int 12 f[0]=0; 13 for(int i=0;i<n;i++){ 14 scanf("%d%d",&a,&b); 15 for(int v=S;v>=a;v--){ 16 f[v] = max(f[v],f[v-a]+b); 17 } 18 } 19 printf("%d\n",f[S]); 20 } 21 return 0; 22 } View Code

輸入：

5 10 ? （分別表示：n,S）
2 3
7 5
3 1
5 10
2 2

輸出：14

（3）如何從n種（每種無(wú)限個(gè)）重量和價(jià)值分別為Vi、Wi的物品中選擇一或多個(gè)放入最大容納量為S的背包使其總價(jià)值最大？

1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=1e3+10; 6 int f[maxn]; 7 int main(){ 8 freopen("datain.txt","r",stdin); 9 int n,S,a,b; 10 while(scanf("%d%d",&n,&S)==2){ 11 memset(f,0,sizeof(f)); 12 for(int i=0;i<n;i++){ 13 scanf("%d%d",&a,&b); 14 for(int v=a;v<=S;v++){ 15 f[v] = max(f[v],f[v-a]+b); 16 } 17 } 18 printf("%d\n",f[S]); 19 } 20 return 0; 21 } View Code

輸入:

5 6
2 3
7 5
3 1
5 10
2 2

輸出:10

（4）如何從n種（每種無(wú)限個(gè)）重量和價(jià)值分別為Vi、Wi的物品中選擇一或多個(gè)放入最大容納量為S的背包在背包剛好裝滿情況下，使其總價(jià)值最大？

1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=1e3+10; 6 int f[maxn]; 7 int main(){ 8 freopen("datain.txt","r",stdin); 9 int n,S,a,b; 10 while(scanf("%d%d",&n,&S)==2){ 11 for(int i=0;i<=S;i++) f[i]=-0xfffffff; 12 f[0]=0; 13 for(int i=0;i<n;i++){ 14 scanf("%d%d",&a,&b); 15 for(int v=a;v<=S;v++){ 16 f[v] = max(f[v],f[v-a]+b); 17 } 18 } 19 printf("%d\n",f[S]); 20 } 21 return 0; 22 } View Code

輸入：

5 6
2 3
7 5
3 1
5 10
2 2

輸出：9

----------------------------------------------
結(jié)語(yǔ)：
本文限于篇幅就只是對(duì)最最基本的01背包問(wèn)題作了個(gè)人的分析，后面的3個(gè)擴(kuò)展只貼代碼，希望感興趣的朋友們可以旁擊側(cè)敲吧~有問(wèn)題或獨(dú)特見解的博友請(qǐng)留言~

轉(zhuǎn)載于:https://www.cnblogs.com/SeaSky0606/p/4743758.html

總結(jié)

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

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