引子

~ 我們都有一個家，名字叫背包 ~

背包DP

顧名思義，背包DP是用來解決背包最值問題的。題目會給出背包的容量，以及幾個物品的屬性，比如重量，價值，限額等等，具體是什么看題目。

01背包

01背包就是每個物品只能選擇拿還是不拿。怎么實現呢？我們設$dp[i]$表示當背包容量為$i$是可以獲得的最值，那么答案就是$dp[w]$，其中$w$代表背包容量。

首先，我們枚舉每一個物品，然后再枚舉背包容量，看目前的背包裝不裝的下這個物品，如果裝得下，那么用裝這個物品之前剩余的背包的容量的最值加上這個物品的價值更新目前的$dp[j]$，動態轉移方程 $dp[j]=max(dp[j],dp[j?w[i]]+q[i])$。

洛谷 P1048 采藥

辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師。為此，他想拜附近最有威望的醫師為師。醫師為了判斷他的資質，給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大。”

如果你是辰辰，你能完成這個任務嗎？

當然不能啦01背包的模板，真沒啥好說的，動態轉移方程都出了。

時間復雜度$O(nt)$

#include<bits/stdc++.h>
using namespace std;
struct cy{int t,j;
}a[105];
int dp[1005];
int main(){int t,n;cin>>t>>n;for(int i=1;i<=n;i++){cin>>a[i].t>>a[i].j;}for(int i=1;i<=n;i++){for(int j=t;j>=0;j--){if(j>=a[i].t){dp[j]=max(dp[j],dp[j-a[i].t]+a[i].j);}}}cout<<dp[t];return 0;
}

完全背包

完全背包就是每個物品可以拿無數個。基本和01背包一致，只是背包容量要從小到大枚舉。為什么呢？

個人認為，從大到小枚舉，因為背包容量更大的只可能被背包容量更小的更新，而且是先更新背包容量更大的，所以一個物品只會被拿一次。

相反，從小到大枚舉，因為背包容量更小的可以更新背包容量更大的，而且是先更新背包容量更小的，所以一個物品會被拿很多次。

洛谷 P1616 瘋狂的采藥

LiYuxiang 是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師。為此，他想拜附近最有威望的醫師為師。醫師為了判斷他的資質，給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同種類的草藥，采每一種都需要一些時間，每一種也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大。”

如果你是 LiYuxiang，你能完成這個任務嗎？

此題和原題的不同點：

1. 每種草藥可以無限制地瘋狂采摘。
2. 藥的種類眼花繚亂，采藥時間好長好長啊！師傅等得菊花都謝了！

當然不能啦完全背包的模板，稍微注意一下要開long long。

時間復雜度$O(nt)$

#include<bits/stdc++.h>
using namespace std;
struct cy{long long t,j;
}a[10005];
long long b[10000005];
int main(){int t,n;cin>>t>>n;for(int i=1;i<=n;i++){cin>>a[i].t>>a[i].j;} for(int i=1;i<=n;i++){for(int j=0;j<=t;j++){if(j>=a[i].t){b[j]=max(b[j],b[j-a[i].t]+a[i].j);}}}cout<<b[t];return 0;
}

多重背包

多重背包就是第i個物品最多可以拿p[i]次，大小為w[i]，價值為q[i]。一種做法，把多重背包轉換成01背包來寫。

首先枚舉每一個物品，然后從大到小枚舉背包容量，接著枚舉拿多少個這個物品，判斷目前的背包容量裝不裝的下這么多個物品，裝得下就用裝這幾個物品之前的最值加上這幾個物品的價值更新目前的dp。$dp[j]=max(dp[j],dp[j?k?w[i]]+k?q[i]$。

但是，但是，時間復雜度就是$O(V\Sigma p[i])$了，在一些題目里會超時。怎么辦呢？于是就有了二進制優化。

洛谷 P1776 寶物篩選

終于，破解了千年的難題。小 FF 找到了王室的寶物室，里面堆滿了無數價值連城的寶物。

這下小 FF 可發財了，嘎嘎。但是這里的寶物實在是太多了，小 FF 的采集車似乎裝不下那么多寶物。看來小 FF 只能含淚舍棄其中的一部分寶物了。

小 FF 對洞穴里的寶物進行了整理，他發現每樣寶物都有一件或者多件。他粗略估算了下每樣寶物的價值，之后開始了寶物篩選工作：小 FF 有一個最大載重為$W$ 的采集車，洞穴里總共有$n$種寶物，每種寶物的價值為$v_i?$，重量為$w_i$?，每種寶物有$m_i$件。小 FF 希望在采集車不超載的前提下，選擇一些寶物裝進采集車，使得它們的價值和最大。

多重背包加 二進制 or 單調隊列 優化即可。

時間復雜度$O(nm)$

#include<bits/stdc++.h>//二進制優化多重背包
using namespace std;
int dp[1000005],w[1000005],v[1000005],n,m,ans,cnt=1;
int main(){cin>>n>>m;for(int i=1;i<=n;i++){int a,b,c;cin>>a>>b>>c;for(int j=1;j<=c;j<<=1){v[++cnt]=j*a;w[cnt]=j*b;c-=j;}if(c){v[++cnt]=a*c;w[cnt]=b*c; }}for(int i=1;i<=cnt;i++){for(int j=m;j>=w[i];j--){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}        }cout<<dp[m];return 0;
}

混合背包

太恐怖了混合背包，每一個物品，它可以拿無數次或拿有限次。其實就是把前面三種背包捆起來，枚舉每個物品時判斷一下是可以拿無數次還是可以拿有限次，是無數次就用完全背包，是有限次就用多重背包。

洛谷 P1833 櫻花

愛與愁大神后院里種了$n$棵櫻花樹，每棵都有美學值$C_i(0<C_i\le 200)$。愛與愁大神在每天上學前都會來賞花。愛與愁大神可是生物學霸，他懂得如何欣賞櫻花：一種櫻花樹看一遍過，一種櫻花樹最多看$P_i(0\le P_i\le 100)$遍，一種櫻花樹可以看無數遍。但是看每棵櫻花樹都有一定的時間$T_i(0<T_i\le 100)$。愛與愁大神離去上學的時間只剩下一小會兒了。求解看哪幾棵櫻花樹能使美學值最高且愛與愁大神能準時（或提早）去上學。

混合背包模板題，需要贅述嗎？

時間復雜度$O(nt)$

#include<bits/stdc++.h>
using namespace std;
struct node{int t,c,p;
}a[10005];
long long dp[1005];
int main(){string s1,s2;cin>>s1>>s2;int t1=0,t2=0,t3=0,t4=0;//這只是一些細節，可以直接跳過if(s1.size()==4){t1=s1[0]-48;t2=(s1[2]-48)*10+s1[3]-48;}else{t1=(s1[0]-48)*10+s1[1]-48;t2=(s1[3]-48)*10+s1[4]-48;}if(s2.size()==4){t3=s2[0]-48;t4=(s2[2]-48)*10+s2[3]-48;}else{t3=(s2[0]-48)*10+s2[1]-48;t4=(s2[3]-48)*10+s2[4]-48;}int t=(t3-t1)*60+(t4-t2),n;//到這才算真正開始cin>>n;for(int i=1;i<=n;i++){cin>>a[i].t>>a[i].c>>a[i].p;}for(int j=1;j<=n;j++){if(a[j].p==0){//如果可以拿無數次for(int i=1;i<=t;i++){//完全背包if(i>=a[j].t){dp[i]=max(dp[i],dp[i-a[j].t]+a[j].c);}}}else{//不然就只能拿有限次數for(int i=t;i>=1;i--){//多重背包for(int k=1;k<=a[j].p;k++){if(i>=k*a[j].t){dp[i]=max(dp[i],dp[i-k*a[j].t]+a[j].c*k);}}}            }}cout<<dp[t];return 0;
}

完結撒花就怪了。。。。。。

好多例題

hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh……

咳咳，剛才有些腦抽了，巨佬別**……

洛谷 P1510 精衛填海

本題為改編題。

發鳩之山，其上多柘木。有鳥焉，其狀如烏，文首，白喙，赤足，名曰精衛，其名自詨。是炎帝之少女，名曰女娃。女娃游于東海，溺而不返，故為精衛。常銜西山之木石，以堙于東海。——《山海經》

精衛終于快把東海填平了！只剩下了最后的一小片區域了。同時，西山上的木石也已經不多了。精衛能把東海填平嗎？

事實上，東海未填平的區域還需要至少體積為 v 的木石才可以填平，而西山上的木石還剩下 n 塊，每塊的體積和把它銜到東海需要的體力分別為 k 和 m。精衛已經填海填了這么長時間了，她也很累了，她還剩下的體力為 c。

哇，01背包！看起來好高級啊！

千萬不要想復雜了，其實只要把狀態想清楚了就行了。我的做法是把dp[i]狀態設為體力為i時可以填補的最大體積，那么最后的答案就是 $c$ 減去符合條件 $v\le dp[i]$ 的最小 $i$。

時間復雜度$O(nc)$

#include<bits/stdc++.h>
using namespace std;
int k[10005],m[10005],dp[10005];
int main(){int u,n,c;cin>>u>>n>>c;for(int i=1;i<=n;i++){cin>>k[i]>>m[i];}for(int j=1;j<=n;j++){for(int i=c;i>=0;i--){if(m[j]<=i){dp[i]=max(dp[i],dp[i-m[j]]+k[j]);}}}if(dp[c]<u){cout<<"Impossible";}else if(dp[0]>=u){//可能只需要填0體積或有的木石所需體力為0cout<<c;}else{for(int i=1;i<=c;i++){if(dp[i]>=u){cout<<c-i;return 0;}}}return 0;
}

洛谷 P1455 搭配購買

明天就是母親節了，電腦組的小朋友們在忙碌的課業之余挖空心思想著該送什么禮物來表達自己的心意呢？聽說在某個網站上有賣云朵的，小朋友們決定一同前往去看看這種神奇的商品，這個店里有 n 朵云，云朵已經被老板編號為 1,2,3,…,n，并且每朵云都有一個價值。

但是商店的老板是個很奇怪的人，他會告訴你一些云朵要搭配起來買才賣，也就是說買一朵云則與這朵云有搭配的云都要買。電腦組的你覺得這禮物實在是太新奇了，但是你的錢是有限的，所以你肯定是想用現有的錢買到盡量多價值的云。

非常鬼畜的一道題，但并不難。首先題目告訴我們一些云朵必須一起買，相信你一定想到了并查集，沒錯，就是并查集！好吧，標簽上面就有……

首先我們設好并查集數組的初始值，然后接到m個搭配的時候用并查集函數找到這兩朵云的祖宗，然后讓他們認祖歸宗，完了之后看有幾個祖宗，用一個數組統計起來。

接下來就是強連通分量了，把每個祖宗相同的點連起來，看成一整個點，再用兩個數組記錄這幾個點的總價錢和總價值，然后就套上01背包模板即可得出答案。

時間復雜度$O(cntw)$

#include<bits/stdc++.h>
using namespace std;
int c[10005],d[10005],fa[10005],dp[10005];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);
}
int q[10005],g[10005],gp[10005];
int main(){int n,m,w;cin>>n>>m>>w;for(int i=1;i<=n;i++){cin>>c[i]>>d[i];fa[i]=i;}for(int i=1;i<=m;i++){int u,v;cin>>u>>v;u=find(u),v=find(v);if(u!=v){fa[u]=fa[v];}}for(int i=1;i<=n;i++){if(fa[i]==i){gp[++gp[0]]=i;}}for(int i=1;i<=n;i++){for(int j=1;j<=gp[0];j++){if(find(i)==gp[j]){q[j]+=c[i];g[j]+=d[i];}}}for(int j=1;j<=gp[0];j++){for(int i=w;i>=0;i--){if(i>=q[j]){dp[i]=max(dp[i],dp[i-q[j]]+g[j]);}}}cout<<dp[w];return 0;
}

CF189A Cut Ribbon

波利卡普有一條長度為n的絲帶。他想按照以下兩個條件切割這條絲帶：

1. 切割后每段絲帶的長度必須是a、b或c
2. 切割后的絲帶段數要盡可能多

請幫助波利卡普計算出滿足條件的切割方式下，最多能得到多少段絲帶。

別想著用分支結構，因為他最多可以分成4000段……

感覺好簡單哪，不就是完全背包嗎？我們設dp[i]為絲帶長度為i時可以分成的最多段數，那么答案就是dp[n]。

所謂物品，在這里就是a,b,c，把它分成幾段，就是拿幾個a，拿幾個b，拿幾個c，那么在枚舉絲帶長度時就可以看減去這一段是否可以分成若干個a,b,c，可以就用$dp[i?a,b,c]+1$更新$dp[i]$。

時間復雜度$O(n)$

#include<bits/stdc++.h>
using namespace std;
long long dp[8005];
int main(){long long n,a,b,c;cin>>n>>a>>b>>c;if(b>c){//注意，為了使分的段數盡量的多，所以我們一定要從長度更小的開始 dpswap(b,c);}if(a>b){swap(a,b);}for(int i=1;i<=n;i++){if(i==a||(dp[i-a+n]&&i>=a)){dp[i+n]=max(dp[i+n],dp[i-a+n]+1);//左移戰術，百戰不殆！}if(i==b||(dp[i-b+n]&&i>=b)){dp[i+n]=max(dp[i+n],dp[i-b+n]+1);}if(i==c||(dp[i-c+n]&&i>=c)){dp[i+n]=max(dp[i+n],dp[i-c+n]+1);}}cout<<dp[n+n];return 0;
}

洛谷 P6771 [USACO05MAR] Space Elevator 太空電梯

奶牛們要去太空了！它們打算用方塊建造一座太空電梯。現在它們有 N 種方塊，第 i 種方塊有一個特定的高度 $h_i$ ，一定的數量 $c_i$ 。為了防止宇宙射線破壞方塊，第 i 種方塊的任何部分不能超過高度 $a_i$ 。請用這些方塊堆出最高的太空電梯。

話說這些奶牛越來越獵奇了……

說白了就是個多重背包嘛，也就套了個太空電梯的殼子，不過這回dp是一個bool數組，也就是dp[i]表示是否可以達到高度 i ，那么當j>=k*h[i]，狀態轉移方程：$dp[j]|=dp[j?k?a[i].h]$。

時間復雜度$O(nk\Sigma a[i])$

#include<bits/stdc++.h>
using namespace std;
struct node{int h,a,c;
}a[405];
bool cmp(node x,node y){return x.a<y.a;
}
bool dp[40005];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i].h>>a[i].a>>a[i].c;}sort(a+1,a+1+n,cmp);//排個序才能更優dp[0]=1;for(int i=1;i<=n;i++){for(int j=a[i].a;j>=a[i].h;j--){for(int k=1;k<=a[i].c;k++){if(j>=k*a[i].h){dp[j]|=dp[j-k*a[i].h];}}}}for(int i=a[n].a;i>=0;i--){if(dp[i]){cout<<i;return 0;}}return 0;
}