引子

~ 我们都有一个家，名字叫背包 ~

背包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\ast w[i]]+k\ast 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\ast 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;
}