【模板】各種背包問(wèn)題&講解

?背包問(wèn)題集合

　　一般來(lái)說(shuō)，動(dòng)態(tài)規(guī)劃(DP)都是初學(xué)者最難闖過(guò)的一關(guān)，而在這里詳細(xì)解說(shuō)動(dòng)態(tài)規(guī)劃的一種經(jīng)典題型：背包問(wèn)題。

這里介紹的背包分為以下幾種：01背包，完全背包，多重背包，混合背包，二維費(fèi)用的背包。(以后會(huì)持續(xù)更新)

【一：01背包】

首先放上例題：

01背包問(wèn)題

【題目描述】：

一個(gè)旅行者有一個(gè)最多能裝M公斤的背包，現(xiàn)在有n件物品，他們的重量分別是W1，W2…Wn，它們的價(jià)值分別是C1，C2……Cn，求旅行者能夠獲得的最大總價(jià)值。

【輸入格式】：

第一行：兩個(gè)整數(shù)，M，(背包容量，M<=200)和N(物品數(shù)量N<=30)

第2至N+1行，每行兩個(gè)整數(shù)，Wi,Ci,表示每個(gè)物品的重量和價(jià)值。

【輸出格式】：僅一行，一個(gè)數(shù)，表示最大總價(jià)值。

【輸入樣例#1】：

10 4

2 1

3 3

4 5

7 9

【輸出樣例#1】：12

【輸入樣例#2】：

8 4

5 6

4 2

1 2

01背包問(wèn)題可以說(shuō)是最簡(jiǎn)單的背包問(wèn)題，簡(jiǎn)單之處就在：他的每一個(gè)物品都只有一個(gè)。

首先定義一個(gè)f[MAXN][MAXN]數(shù)組，用來(lái)記錄最大價(jià)值。即：f[i][v]表示的就是當(dāng)前i件物品放入一個(gè)容量為v的背包的時(shí)候可以獲得的最大價(jià)值。

01背包的狀態(tài)轉(zhuǎn)移方程式便是：f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i])。

眾所周知DP問(wèn)題最重要的便是狀態(tài)轉(zhuǎn)移方程式了，那么這個(gè)狀態(tài)轉(zhuǎn)移方程式究竟是怎么來(lái)的呢？？

詳解來(lái)啦“！！！

既然說(shuō)了是“將第i件物品放入背包”，那么如果只考慮第i件物品的方式策略，那么就只和第i-1件物品有關(guān)了，如果是放第i件物品，那么問(wèn)題就轉(zhuǎn)化為：“前i-1件物品放入容量為v的背包中”，此時(shí)能夠獲得的最大價(jià)值就是f[i-1][v-w[i]]，也就是第i-1件物品放入容量為v(原來(lái)的總?cè)萘?減去w[i](第i件物品的占容)產(chǎn)生的最優(yōu)價(jià)值，再加上放通過(guò)入第i件物品增加的價(jià)值c[i]。

那么放入第i件物品產(chǎn)生的最大價(jià)值就是要在”放“，或者是”不放“中選擇了，”不放“的話，產(chǎn)生的價(jià)值就是f[i-1][v]，”放“的話，產(chǎn)生的最大價(jià)值就是,f[i-1][v-w[i]]+c[i])。那么我們應(yīng)該怎么選擇呢，很簡(jiǎn)單，取最大的，就是產(chǎn)生的最大價(jià)值啦。

若物品數(shù)量為n，背包總?cè)萘繛閙，那么循環(huán)到最后，答案也就是f[n][m]啦。

那么附上代碼：：：

#include#define MAXN 0x7ffusing namespace std;int m,n,w[MAXN],c[MAXN];int f[MAXN][MAXN],i,j;//f[i][v]表示第i件物品放入容量為v的背包所能產(chǎn)生的最大價(jià)值。 int maxn(int x,int y)//比較，輸出最大值 {if(x>y)return x;else return y;
}int main()
{
cin>>m>>n; for(i=1;i<=n;i++)
cin>>w[i]>>c[i];//輸入不解釋 for(i=1;i<=n;i++)for(j=m;j>0;j--)
{if(w[i]<=j)
f[i][j]=maxn(f[i-1][j],f[i-1][j-w[i]]+c[i]);//狀態(tài)轉(zhuǎn)移方程式。 else f[i][j]=f[i-1][j];
}
cout<<f[n][m];return 0;
}

好了以上就是最簡(jiǎn)單的01背包模板了qwq。

【二：完全背包問(wèn)題】

還是例題打頭陣。

完全背包問(wèn)題

【題目描述】

設(shè)有n種物品，每種物品有一個(gè)價(jià)值，但每種物品的數(shù)量是無(wú)限的，同時(shí)有一個(gè)背包，最大承載量微m，今從n種物品中選取若干件，(同一種物品可以多次選舉)使其重量的和小于等于m，而且價(jià)值的和最大。

【輸入】共N+1行

第一行：兩個(gè)整數(shù)：M(背包容量M<=200)和N(物品數(shù)量，N<=30)；

第二行至第N+1行，每行兩個(gè)整數(shù)，Wi，Ci，表示每個(gè)物品的重量和價(jià)值。

【輸出】

近一行：一個(gè)數(shù)，表示最大的價(jià)值；

【輸入樣例】

10 4

2 1

3 3

4 5

7 9

【輸出樣例】

12

有的小伙伴們可能一看到例題就會(huì)發(fā)現(xiàn)一個(gè)與01背包不同的地方：每種物品的數(shù)量是無(wú)限多的。沒(méi)錯(cuò)，這就是完全背包問(wèn)題。其實(shí)這個(gè)問(wèn)題沒(méi)有比01背包難多少，只是不是很好想。

既然每種物品所取的數(shù)量可能是1,2,3.......，所以與它相關(guān)的策略便不是取或者不取的問(wèn)題了，而是，取不取，取多少的問(wèn)題了。既然同樣是背包問(wèn)題，那么我們可不可以考慮延續(xù)01背包的方法來(lái)做呢，答案是Yes。其實(shí)與01背包不同的地方就是只有放進(jìn)去的每種物品的件數(shù)不一定是1就是了，那么只要多一重關(guān)于每種物品取多少的循環(huán)不就可以了嗎。相對(duì)的，其狀態(tài)轉(zhuǎn)移方程式也要略有改動(dòng)，變?yōu)?#xff1a;f[i][v]=max(f[i-1][v-k*w[i]]+k*c[i],f[i-1][v])，可見(jiàn)就是比01背包多了一個(gè)k而已，而這個(gè)k就是循環(huán)的這第i種物品取的件數(shù)。

現(xiàn)在解釋一下原因：首先我們想一下為甚么在上題中的01背包代碼中第二重循環(huán)是for(int j=m;j>=0;j--)而不是for(int j=1;j~~~)

Because~因?yàn)?#xff1a;要保證第i次循環(huán)里的狀態(tài)f[i][v]是由狀態(tài)f[i][[v-w[i]]遞推而來(lái)的，也就是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時(shí)，依據(jù)的是一個(gè)絕不可能選入第i種物品的子結(jié)果f[i][v-w[i]]。如果如果還不是很明白，大家可以畫(huà)一個(gè)表格來(lái)自己推一下，看看逆序和正序時(shí)得到的結(jié)果有什么不同。。。。。。

好了重點(diǎn)來(lái)了！！?： 現(xiàn)在大家已經(jīng)知道了01背包的順序，那么現(xiàn)在問(wèn)題來(lái)了：完全背包的順序呢？？

考慮“加選一件第i種物品”這種策略時(shí)，卻正需要一個(gè)可能已經(jīng)選入第i種物品的子結(jié)果f[i][v=w[i]]，所以就可以并且必須采用v=0,.....v的順序循環(huán)，這就是則個(gè)簡(jiǎn)單的程序何以成立的原因啦。

然后給大家附上代碼：： ? ?//不準(zhǔn)抄襲！！? ? ?好吧像我這種蒟蒻代碼有誰(shuí)會(huì)抄呢 呵呵~~

#include
#includeusing namespace std;const int MAXN=31,MAXM=201;int m,n,w[MAXN],c[MAXN],f[MAXN][MAXM];int main()
{scanf("%d%d",&m,&n);for(int i=1;i<=n;i++)
scanf("%d%d",&w[i],&c[i]);for(int i=1;i<=n;i++)for(int v=1;v<=m;v++)if(v1][v];else {if(f[i-1][v]>f[i][v-w[i]]+c[i]) f[i][v]=f[i-1][v];else f[i][v]=f[i][v-w[i]]+c[i];}
printf("%d",f[n][m]); return 0;
}//這個(gè)碼風(fēng)不是很好看，大家看不慣可以改一改......

?【三：多重背包問(wèn)題】

好了依然是看例題：：

模板例題：慶功會(huì)

【題目描述】

設(shè)有n種物品，每種物品有一個(gè)價(jià)值，但每種物品的數(shù)量是有限的，同時(shí)有一個(gè)背包，最大承載量微m，今從n種物品中選取若干件，(同一種物品可以多次選舉)使其重量的和小于等于m，而且價(jià)值的和最大。

【輸入】共N+1行

第一行：兩個(gè)整數(shù)：N(物品數(shù)量，N<=30)和M(背包容量M<=200)

第二行至第N+1行，每行兩個(gè)整數(shù)，Wi，Ci，Si，分別表示每個(gè)物品的重量、價(jià)值、數(shù)量。

【輸出】

近一行：一個(gè)數(shù)，表示最大的價(jià)值；

【輸入樣例】

5 1000

80 20 4

40 50 9

30 50 7

40 30 6

20 20 1

【輸出樣例】

1040

　　這個(gè)題目就又不一樣了，因?yàn)轭}目中說(shuō)的每一件物品的件數(shù)是“有限的”，也就是說(shuō)可以是1、2......但也不是無(wú)限。

這個(gè)看起來(lái)可能就比較e xin，但是如果仔細(xì)想一想，其實(shí)也并不是很難。

(蒟蒻認(rèn)為的)重點(diǎn)詳解：
做法1：和完全背包接軌：完全背包里面有一個(gè)k，用來(lái)表示物品的個(gè)數(shù)，這里面也是一樣的，因?yàn)閷?duì)于第i種物品，我們可以設(shè)置他有n[i]+1種取數(shù)策略，：取0、1.....n[i]件，so我們?cè)俅卧O(shè)置一個(gè)f[i][v]表示前i種物品放入一個(gè)容量為v的背包所能產(chǎn)生的最大價(jià)值，那么：f[i][v]=max(f[i-1)[v-k*w[i]]+k*c[i],f[i-1][v]),那么復(fù)雜度就是O(V*Σn[i])。

? ?顯然，上方做法時(shí)間復(fù)雜度太高。于是就有了第二個(gè)方法。

做法2：和01背包接軌。大家可能都覺(jué)得完全背包比01背包更要高大上一些，但是很不幸，做法2是要遠(yuǎn)遠(yuǎn)優(yōu)于做法1的。先給大家一個(gè)引路思想，第i件物品有n[i]的數(shù)量，那么是不是可以把它轉(zhuǎn)化為n個(gè)數(shù)量只有一個(gè)的物品呢？？看到這里，你恍然大悟：哦，好巧妙。

而事實(shí)上，如果你只想到這里，就開(kāi)始興奮無(wú)腦地開(kāi)始打代碼的話，你就會(huì)呵呵進(jìn)化成神犇了。。。。。你您可以算一算如果這樣做的話時(shí)間復(fù)雜度是多少：O(V*Σn[i]) ?............

好極了，可是我并沒(méi)有在逗你啊。。。。。

那么接下來(lái)就是優(yōu)化了，在這里，我們考慮二進(jìn)制優(yōu)化。

方法：將第i件物品分成若干件物品，每個(gè)物品有一個(gè)系數(shù)l，這件物品的費(fèi)用和價(jià)值軍事原來(lái)的費(fèi)用和價(jià)值乘以l，使這些系數(shù)分別為1,2,4...2^(k-1)余出來(lái)的再拿出來(lái)就是n[i]-2^(k+1),且k是滿足n[i]-2^(k+1)>0的最大整數(shù)。(例：13分為1,2,4,6)。

這樣就將第i件物品分成了O(logn[i)種物品，將時(shí)間復(fù)雜度降低成為了O(V*Σlogn[i])的01背包問(wèn)題，改進(jìn)是不是很大呢？

下面是代碼：

#include
#include#define MAXN 10001#define MAXM 6001using namespace std;int v[MAXN],w[MAXN],f[MAXM];int n,m,n1;int max(int a,int b)
{if(a>b) return a;else return b;
}int main()
{
scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)
{int x,y,s,t=1;
scanf("%d%d%d",&x,&y,&s);while(s>=t)
{
v[++n1]=x*t;
w[n1]=y*t;
s-=t;
t*=2;
}
v[++n1]=x*s;
w[n1]=y*s;
}for(int i=1;i<=n1;i++)for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
printf("%d\n",f[m]); return 0;
}

【四：混合三種背包問(wèn)題】

　　大概很多人一看到這個(gè)就淚奔了，對(duì)，沒(méi)錯(cuò)，就是把01、完全、多重背包混合起來(lái)考你。你可能肯定覺(jué)得很惡心，覺(jué)得難極了，確實(shí)，對(duì)于沒(méi)有學(xué)過(guò)前幾種背包的人來(lái)說(shuō)，這是一個(gè)很大的挑戰(zhàn)，但是不要忘了，我們已經(jīng)學(xué)完了呀!所以，我哦們就可以很輕易地將這一個(gè)難題轉(zhuǎn)化為極個(gè)簡(jiǎn)單的子題了！！

　　其實(shí)也不用怎么解釋了，先判斷該物品是不是屬于完全背包，if(YES)->用完全背包去做，if(NOT)->用混合背包去做(因?yàn)?1背包本身即是多重背包的一個(gè)樣例，用多重背包做完全沒(méi)有問(wèn)題的。)

　　好了下面附上代碼：

#include
#includeusing namespace std;int m,n,w[31],c[31],p[31],f[201];int max(int a,int b)
{if(a>b) return a;else return b;
}int main()
{
scanf("%d%d",&m,&n);for(int i=1;i<=n;i++)
scanf("%d%d%d",&w[i],&c[i],&p[i]);for(int i=1;i<=n;i++)if(p[i]==0)
{for(int j=w[i];j<=m;j++)
f[j]=max(f[j],f[j-w[i]]+c[i]);
}else
{for(int j=1;j

)

for(int k=m;k>=w[i];k--)
f[k]=max(f[k],f[k-w[i]]+c[i]);
}
printf("%d",f[m]);return 0;
}

【五：二維費(fèi)用的背包】

　　這又是一種新的背包問(wèn)題了，顯而易見(jiàn)，他的費(fèi)用是二維的。什么叫二維的呢？先來(lái)看一道例題，你就能明白了。

? ? ? ? ? ? ? ? ? ??? ? ?例題：潛水員

【問(wèn)題描述】

潛水員為了潛水要使用特殊的裝備，他有一個(gè)帶2種氣體的氣缸，一個(gè)為氧氣，一個(gè)為氮?dú)?#xff0c;讓錢(qián)會(huì)員下潛的深度需要各種數(shù)量的氧和氮，潛水員有一定數(shù)量的氣缸，每個(gè)氣缸都有重量和氣體容量，潛水員為了完成她的工作需要特定的數(shù)量的氧和氮，他完成工作需要?dú)飧椎目傊氐淖畹拖薅仁嵌嗌?#xff1f;？

【輸入格式】

第一行：兩個(gè)整數(shù)，m，n，(1<=m<=21,1<=n<=79)。他們表示氧，氮各自需要的量。

第二行：為整數(shù)k(1<=k<=1000)表示氣缸的個(gè)數(shù)。

此后的k行每行包括一個(gè)ai,bi,ci，(1<=ai<=21,1<=bi<=79,c<=ci<=800)三個(gè)整數(shù)，分別表示第i個(gè)氣缸里的氧的容量，氮的容量，以及氣缸重量。

【輸出格式】

僅一行，包含一個(gè)整數(shù)，為重量和的最低值。

【輸入樣例】

5 60

5

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

【輸出樣例】

249

好的，我覺(jué)得大多數(shù)人可能都已經(jīng)明白了什么叫二維了，在這個(gè)例題中，每一個(gè)氣缸油兩種不同的費(fèi)用，選擇這件物品必須同時(shí)付出這兩種代價(jià)，對(duì)于每一種代價(jià)有一個(gè)背包容量，問(wèn)怎么樣選擇物品可以得到最大的價(jià)值。

接下來(lái)不只針對(duì)例題，而是對(duì)于大多數(shù)二維背包題：

　　我們可以定義第i種物品的代價(jià)分別為a[i]和b[i],兩種背包容量分別為V和U，第i件物品的價(jià)值為c[i]。

那么顯而易見(jiàn)，我們的算法需要增加一維，那么就將我們的f再增加一維即可，那么就有了狀態(tài)轉(zhuǎn)移方程式：：

f[i][v][u]=max)f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+c[i])，當(dāng)然，當(dāng)物品只取一次是的時(shí)候變量v和u采取逆序循環(huán)。

但有的時(shí)候，很多良心的題經(jīng)常是將二維背包以一種有一點(diǎn)隱晦的方式表示出來(lái)，例如：最多只能取M件物品，此時(shí)就又多了一個(gè)“件數(shù)”的費(fèi)用，設(shè)f[v][m]表示付出費(fèi)用v，最多選m件的時(shí)候可以得到的最大收入。之后便可以針對(duì)01、完全、多重背包采用不同的方式進(jìn)行運(yùn)算了。最后，在f[0 -> V][1 -> M]范圍內(nèi)尋找答案。

然后，附上【潛水員】例題的代碼。

#include
#include
#include#define MAXN 1001#define MAXM 101using namespace std;int v,u,k;int a[MAXN],b[MAXN],c[MAXN];int f[MAXM][MAXM];int main()
{
memset(f,127,sizeof(f));
f[0][0]=0;
scanf("%d%d%d",&v,&u,&k);for(int i=1;i<=k;i++)
scanf("%d%d%d",&a[i],&b[i],&c[i]);for(int i=1;i<=k;i++)for(int j=v;j>=0;j--)for(int l=u;l>=0;l--)
{ int t1=j+a[i],t2=l+b[i];;if(t1>v) t1=v;if(t2>u) t2=u;if(f[t1][t2]>f[j][l]+c[i]) f[t1][t2]=f[j][l]+c[i];
}
printf("%d",f[v][u]);return 0;
}

好了，關(guān)于背包問(wèn)題就先說(shuō)到這里(持續(xù)更新。。。)，如果有不明白個(gè)或者錯(cuò)誤的地方可以給我留言。。。

標(biāo)簽:?背包

2

總結(jié)

以上是生活随笔為你收集整理的c++ 多重背包状态转移方程_【模板】各种背包问题amp;讲解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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