算法课的小作业，写了挺多就发掉吧，应该写的挺详细的（。
浅谈背包问题
定义：背包问题是运筹学中的一个经典的优化难题，是一个 NP-完全问题，但其有 着广泛的实际应用背景，是从生活中一个常见的问题出发展开的： 一个背包，和很多件物品，要在背包中放一些物品，以达到一定的目标。
(摘自《2008年国家集训队论文——浅谈几类背包问题（徐持衡）》)
0-1背包
0-1 背包问题：给定 n 件物品和一个背包。物品 i 的价值是 Wi ，其体积为 Vi，背包 的容量为 C。可以任意选择装入背包中的物品，求装入背包中物品的最大总价值。
在选择装入背包的物品时，对每件物品 i ，要么装入背包，要么不装入背包。 不能将物品 i 多次装入背包，也不能只装入部分物品 i （分割物品 i）。因此，该问题称为 0-1 背包问题。
设 DP 状态dp[i] [j]为在只能放前i个物品的情况下，容量为j的背包所能达到的最大总价值。
考虑转移。假设当前已经处理好了前i-1个物品的所有状态，那么对于第i个物品，当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为dp[i-1] [j]；当其放入背包时，背包的剩余容量会减小Wi，背包中物品的总价值会增大Vi，故这种情况的最大价值为dp[i-1] [j-Wi]+Vi。
由此可以得出状态转移方程：
?dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);但是我们注意到这里如果直接采用二维数组对状态进行记录，空间上会有很多浪费，因为我要计算当前的状态的话只需要只要上一个状态即可，没有必要把所有的状态都保存，这样可能会出现MLE的情况。因此我们可以考虑改用滚动数组的形式来优化。
?dp[i%2][j]=max(dp[(i-1)%2][j],dp[(i-1)%2][j-w[i]]+v[i]);但是这样就够了吗？我们还想继续优化，能不能只用一维进行处理？我们注意到对于某一个状态来说我只需要上一个状态中体积比当前体积-w[i]小的那些状态，因此我们考虑对于当前的这个物品，我先更新大体积的时候的状态，这样就保证了那些将来会被用于转移的小体积的状态的正确性。
所以该转移方程缩小到一维就是：
?dp[j] = max(dp[j], dp[j - w[i]] + v[i]);完整核心代码：
?for (int i = 1; i <= n; i++){
? ? ?for (int j = c; j >= w[i]; j--){
? ? dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
? ? }
?}复杂度分析：对于每一个物品我们都要看它能不能转移上一次的每一个背包的状态，因此复杂度是O(nm)（n是物品个数，m是背包容量）
然而现在我们又会注意到一个问题，如果这个背包容量特别大的话怎么办？假设现在我这个背包的容量是1e9，一维数组都开不下怎么办（超大背包问题）？
首先，如果n<50，那么我们不用dp，直接整体二分双向爆搜然后合并答案即可。
如果n<100呢？整体二分也会t，那我们只能去dp了，注意到我们保存的状态中其实有很多是没有作用的，比如当dp[2] [4]=10，dp[2] [5]=8时，花费5的重量得到的价值反而比花费4的重量的小，那么此时我这个dp[2] [5]就是一个无效状态，完全没有必要保存，因为我能从dp[2] [5]转移过去的一定不如从dp[2] [4]转移过去。不仅如此，如果我们把状态定的严格一点：dp[i] [j]代表考虑前i个物品且刚好重量为j的情况，因为如果找我前面的写法我的状态中其实是隐含了一些重量任意，价值为0的物品用来凑状态的（因为这样好写），但如果按照这个严格定义的话，状态中就会存在一些你根本凑不出来的重量，那么这样的状态也是没有必要保存下来的，所以我们考虑用map把重量这个维度离散化，然后维护这个离散后的状态的单调性，保证j增加时val一定递增即可。
但是数据再开放一些的话就成了一个np问题。。。
例题：[USACO07DEC]Charm Bracelet S - 洛谷
ac代码：
?//https://www.luogu.com.cn/problem/P2871
??
?#include <bits/stdc++.h>
?using namespace std;
?#define visit _visit
?#define next _next
?#define pb push_back
?#define fi first
?#define se second
?#define endl '\n'
?#define fast ios::sync_with_stdio(0), cin.tie(0)
?#define int long long
?#define ll long long
?#define pint pair<int,int>
??
?const int mod = 998244353;
?const int maxn = 200001;
?const int INF = 1e18;
??
?void read(int &x){
? int f=1;x=0;char s=getchar();
? while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
? while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
? x*=f;
?}
?ll quick_pow(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
?ll inv(ll x) {return quick_pow(x, mod-2);}
?//----------------------------------------------------------------------------------------------------------------------//
?int dp[maxn];
?int v[maxn],w[maxn];
?void solve(){
? int n,m;
? cin>>n>>m;
? for(int i=1;i<=n;i++){
? cin>>w[i]>>v[i];
? }
? for(int i=1;i<=n;i++){
? for(int j=m;j>=w[i];j--){
? dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
? }
? }
? cout<<dp[m]<<endl;
?}
??
?signed main(){
? fast;
? int t=1;
? //cin>>t;
? while(t--){
? solve();
? }
? return 0;
?}完全背包
完全背包问题：与0-1背包问题类似，唯一不同的就是一个物品可以选取无限次，而并非一次。
我们依旧设 DP 状态dp[i] [j]为在只能放前i个物品的情况下，容量为j的背包所能达到的最大总价值。
首先因为上面已经说过了0-1背包，所以自然能想到一个算法就是我把每个物品看作C/w[i]个一模一样的物品，每个物品只有选和不选两种选择，这样就转化成了0-1背包问题。但是这样的算法复杂度太高了，自然是不行的，但是它的思想可以帮助我们找到正确的转移方程。
注意到在0-1背包压到一维的过程中，为了防止一个物品被重复加入背包多次，我们从保证每次转移的时候的状态都是从一个未更新的状态转移来的，那么现在我们只需要让一个已经更新过的状态再进行更新，就相当于在已经考虑把这个物品放入背包的时候再考虑是不是能再放一个。即更改0-1背包的转移顺序即可.
核心代码：
?for (int i = 1; i <= n; i++){
? ? ?for (int j = w[i]; j <=C; j++){
? ? dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
? ? }
?}例题：疯狂的采药 - 洛谷
ac代码：
//https://www.luogu.com.cn/problem/P1616
??
?#include <bits/stdc++.h>
?using namespace std;
?#define visit _visit
?#define next _next
?#define pb push_back
?#define fi first
?#define se second
?#define endl '\n'
?#define fast ios::sync_with_stdio(0), cin.tie(0)
?#define int long long
?#define ll long long
?#define pint pair<int,int>
??
?const int mod = 998244353;
?const int maxn = 200001;
?const int INF = 1e18;
??
?void read(int &x){
? int f=1;x=0;char s=getchar();
? while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
? while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
? x*=f;
?}
?ll quick_pow(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
?ll inv(ll x) {return quick_pow(x, mod-2);}
?//----------------------------------------------------------------------------------------------------------------------//
?int dp[(int)1e7+10];
?int v[maxn],w[maxn];
?void solve(){
? int n,m;
? cin>>m>>n;
? for(int i=1;i<=n;i++){
? cin>>w[i]>>v[i];
? }
? for(int i=1;i<=n;i++){
? for(int j=w[i];j<=m;j++){
? dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
? }
? }
? cout<<dp[m]<<endl;
?}
??
?signed main(){
? fast;
? int t=1;
? //cin>>t;
? while(t--){
? solve();
? }
? return 0;
?}多重背包
多重背包问题：类似0-1背包，只不过每个物品有ki个。
类似完全背包我们可以想到把每个物品拆分成ki个一模一样的只有选和不选的物品，然后进行0-1背包即可，但是还是那个问题，复杂度太高了。所以我们需要优化，具体来说常见的优化方式有两种：二进制拆分和单调队列dp优化
二进制分组优化
所谓二进制分组优化，字如其名就是利用二进制的思想，对于每一个数显然我可以拆成A个2的n次方的和，那么换句话说就是我可以用logn个物品去拼出一个大小未n的物品，可是这样只拆成二进制数的话有可能会有某个二进制数我可以使用多次的情况，这又变成了多重背包了，所以我们考虑把这个数拆成1，2，4，8，16，等2的完全次方的和加上一个剩下的数，例如，8=1+2+4+1，18=1+2+4+8+3，利用一种捆绑的思想，把大小为n的物品表示成logn个单个捆绑物品，最后剩下的那个用于补足。这样一来就转化成了0-1背包问题
下面证明这样拆分一定可以满足所有的约束条件：
（1）1+2+4+...+2^(k-1)+n[i]-2^k+1=n[i]。所以这样拆分不会导致总数变多
（2）1,2,4,8...2^(k-1)可以凑出2^k-1的所有整数，再加上n[i]-2^k+1即得证这样拆分可以组合出所有的2^k-1的整数
例题：宝物筛选 - 洛谷
ac代码：
?//https://www.luogu.com.cn/problem/P1776
??
?#include <bits/stdc++.h>
?using namespace std;
?#define visit _visit
?#define next _next
?#define pb push_back
?#define fi first
?#define se second
?#define endl '\n'
?#define fast ios::sync_with_stdio(0), cin.tie(0)
?#define int long long
?#define ll long long
?#define pint pair<int,int>
??
?const int mod = 998244353;
?const int maxn = 2000001;
?const int INF = 1e18;
??
?void read(int &x){
? int f=1;x=0;char s=getchar();
? while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
? while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
? x*=f;
?}
?ll quick_pow(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
?ll inv(ll x) {return quick_pow(x, mod-2);}
?//----------------------------------------------------------------------------------------------------------------------//
?int v[maxn],w[maxn];
?int dp[maxn];
?void solve(){
? int n,W;
? cin>>W>>n;
? int cnt=0;
? for(int i=1;i<=n;i++){
? int a,b,m,c=1;
? cin>>a>>b>>m;
? while(m>c){
? v[++cnt]=c*a;
? w[cnt]=c*b;
? m-=c;
? c*=2;
? }
? v[++cnt]=m*a;
? w[cnt]=m*b;
? }
? for(int i=1;i<=cnt;i++){
? for(int j=W;j>=w[i];j--){
? dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
? }
? }
? cout<<dp[W]<<endl;
?}
??
?signed main(){
? fast;
? int t=1;
? //cin>>t;
? while(t--){
? solve();
? }
? return 0;
?}这样时间复杂度就被优化到了
这样的复杂度已经足够优秀可以解决不少的问题了，但是到此为止了吗，当然还有进一步的能将复杂度优化到线性的算法，就是下面的单调队列优化
单调队列优化
单调队列就是我们用一个队列去实时维护一个区间最值，复杂度是O(n)，用于解决滑动窗口的问题，那仔细想一想我们的多重背包的状态转移方程其实就是找到前面最优的解然后去转移，所以我们考虑怎么把单调队列用于多重背包问题。
我们设j=u+k*(w[i])，那么转移方程就可以写成：
dp[u+k*w[i]]=max(dp[u+k*w[i]],dp[u]+k*v[i]);也就是说dp[j]是由[0-j]的状态中与j相差k*w[i]转移过来的，然后我们做个递推：
?dp[j]=dp[j];
?dp[j+w]=max(dp[j]+v,dp[j+w]);
?dp[j+2*w]=max({dp[j]+2*v,dp[j+w]+v,dp[j+2*w]});
?dp[j+3*w]=max({dp[j]+3*v,dp[j+w]+2*v,dp[j+2*w]+v,dp[j+3*w]})
?......通过这个递推式可以发现，想要转移出dp[j+kw]，我们只需要维护max({dp[j]+kv，dp[j+w]+(k-1)v，......dp[j+(k-1)w]+v})即可，这下我们就可以先枚举u然后快乐地上单调队列了。
例题：宝物筛选 - 洛谷
?//https://www.luogu.com.cn/problem/P1776
??
?#include <bits/stdc++.h>
?using namespace std;
?#define visit _visit
?#define next _next
?#define pb push_back
?#define fi first
?#define se second
?#define endl '\n'
?#define fast ios::sync_with_stdio(0), cin.tie(0)
?#define int long long
?#define ll long long
?#define pint pair<int,int>
??
?const int mod = 998244353;
?const int maxn = 400001;
?const int INF = 1e18;
??
?void read(int &x){
? int f=1;x=0;char s=getchar();
? while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
? while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
? x*=f;
?}
?ll quick_pow(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
?ll inv(ll x) {return quick_pow(x, mod-2);}
?//----------------------------------------------------------------------------------------------------------------------//
?int dp[maxn],que[maxn],num[maxn];
?void solve(){
? int n,C;
? int ans=0,tmp=0;
? cin>>n>>C;
? ? ?for(int i=1;i<=n;i++){
? ? ? ? ?int v,w,m;
? ? ? ? ?cin>>v>>w>>m;
? ? ? ? ?//避免除数为0的情况,重量为0肯定无脑加
? ? ? ? ?if(w==0){
? ans+=m*v;
? continue;
? }
? ? ? ? ?int ma=min(m,C/w);
? ? ? ? ?//枚举每一个余数
? ? ? ? ?for(int j=0;j<w;j++){
? ? ? ? ? ? ?int sum=(C-j)/w;
? ? ? ? ? ? ?//这里因为要重置队列所以用手写队列，deque和queue的清空太慢了
? int head=1,tail=0;
? ? ? ? ? ? ?for(int k=0;k<=sum;k++){
? ? ? ? ? ? ? ? ?int now=dp[j+k*w]-k*v;
? ? ? ? ? ? ? ? ?//单调队列维护队列取最大
? ? ? ? ? ? ? ? ?while(head<=tail&&now>=que[tail]){
? tail--;
? }
? ? ? ? ? ? ? ? ?que[++tail]=now;
? ? ? ? ? ? ? ? ?num[tail]=k;
? ? ? ? ? ? ? ? ?while(head<=tail&&num[head]+ma<k){
? head++;
? }
? ? ? ? ? ? ? ? ?dp[j+k*w]=max(dp[j+k*w],que[head]+k*v);
? ? ? ? ? ? ? ? ?tmp=max(tmp,dp[j+k*w]);
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? ?cout<<tmp+ans<<endl;
?}
??
?signed main(){
? fast;
? int t=1;
? //cin>>t;
? while(t--){
? solve();
? }
? return 0;
?}复杂度分析：由于我们用单调队列可以均摊O(m)地求出区间最值，而一共有n个物品，所以总复杂度是O(nm)，比二进制拆分又优秀了一些。
混合背包
混合背包问题：有些物品只能取一次，有些能取无限次，有些能取k次。
其实没有区别，我们只要对于每个物品的类型分别用对应的转移方程去进行状态转移即可。
伪代码如下：
?for (循环物品种类) {
? ?if (是 0 - 1 背包)
? ? ?套用 0 - 1 背包代码;
? ?else if (是完全背包)
? ? ?套用完全背包代码;
? ?else if (是多重背包)
? ? ?套用多重背包代码;
?}emm，这个找不到好的题目，所以没有完整代码呜呜呜。
二维费用背包
二维费用背包问题：即选取一个物品需要消耗两种价值（如花费，时间）。
稍微扩展了一下，多了一个价值消耗我们就多加一个维度去代表每个价值即可，因为dp的本质就是要将一个状态中可能影响到将来的信息都保存下来（有后效性的信息），然后去进行状态转移。
ac代码：
?//https://www.luogu.com.cn/problem/P1855
??
?#include <bits/stdc++.h>
?using namespace std;
?#define visit _visit
?#define next _next
?#define pb push_back
?#define fi first
?#define se second
?#define endl '\n'
?#define fast ios::sync_with_stdio(0), cin.tie(0)
?#define int long long
?#define ll long long
?#define pint pair<int,int>
??
?const int mod = 998244353;
?const int maxn = 200001;
?const int INF = 1e18;
??
?void read(int &x){
? int f=1;x=0;char s=getchar();
? while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
? while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
? x*=f;
?}
?ll quick_pow(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
?ll inv(ll x) {return quick_pow(x, mod-2);}
?//----------------------------------------------------------------------------------------------------------------------//
?int c1[maxn],c2[maxn],v[maxn];
?int dp[300][300];
?void solve(){
? int n,C1,C2;
? cin>>n>>C1>>C2;
? for(int i=1;i<=n;i++){
? cin>>c1[i];
? cin>>c2[i];
? v[i]=1;
? }
? for(int k=1;k<=n;k++){
? for(int i=C1;i>=c1[k];i--){
? for(int j=C2;j>=c2[k];j--){
? dp[i][j]=max(dp[i][j],dp[i-c1[k]][j-c2[k]]+v[k]);
? }
? }
? }
? cout<<dp[C1][C2]<<endl;
?}
??
?signed main(){
? fast;
? int t=1;
? //cin>>t;
? while(t--){
? solve();
? }
? return 0;
?}分组背包
分组背包问题：当前这些物品被分成了若干组，每一组最多只能选一个放入背包
仔细想一想就会发现这就是个01背包，只是从之前的每个物品要么选要么不选变成了这一组里要么不选要么选一个，所以我们对每一组进行0-1背包的转移即可。
核心代码：
?for(int idx=1;idx<=n;idx++){
? ? ?for(int j=m;j>=0;j--){
? ? ? ? ?for(int i=0;i<v[idx].size();i++){
? ? ? ? ? ? ?if(j-w[idx][i]<0){
? ? ? ? ? ? ? ? ?continue;
? ? ? ? ? ? }
? ? ? ? ? ? ?dp[j]=max(dp[j],dp[j-w[idx][i]]+v[idx][i]);
? ? ? ? }
? ? }
?}这里先枚举容量j再枚举物品就保证了只会选择一个物品进入背包，因为我是先把容量给定下来然后再去看对于当前这个容量我用这每一个去转移看看，就是说每个状态最多只会包含这一组的一个物品。但是如果循环顺序颠倒就会出现同一组的多个物品出现在一个状态里，就变成普通0-1背包了
例题：通天之分组背包 - 洛谷
ac代码：
?//https://www.luogu.com.cn/problem/P1757
??
?#include <bits/stdc++.h>
?using namespace std;
?#define visit _visit
?#define next _next
?#define pb push_back
?#define fi first
?#define se second
?#define endl '\n'
?#define fast ios::sync_with_stdio(0), cin.tie(0)
?#define int long long
?#define ll long long
?#define pint pair<int,int>
??
?const int mod = 998244353;
?const int maxn = 1001;
?const int INF = 1e18;
??
?void read(int &x){
? int f=1;x=0;char s=getchar();
? while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
? while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
? x*=f;
?}
?ll quick_pow(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
?ll inv(ll x) {return quick_pow(x, mod-2);}
?//----------------------------------------------------------------------------------------------------------------------//
?int dp[maxn];
?vector<int> v[maxn], w[maxn];
?void solve(){
? int n,m;
? cin>>m>>n;
? for(int i=1;i<=n;i++){
? int a,b,c;
? cin>>a>>b>>c;
? w[c].pb(a);
? v[c].pb(b);
? }
? for(int idx=1;idx<=n;idx++){
? for(int j=m;j>=0;j--){
? for(int i=0;i<v[idx].size();i++){
? if(j-w[idx][i]<0){
? continue;
? }
? dp[j]=max(dp[j],dp[j-w[idx][i]]+v[idx][i]);
? }
? }
? }
? cout<<dp[m]<<endl;
?}
??
?signed main(){
? fast;
? int t=1;
? //cin>>t;
? while(t--){
? solve();
? }
? return 0;
?}依赖背包
依赖背包问题：如果我想要选第i件物品，那我就必须选第j个物品。
有时候这个依赖关系会很多，甚至有可能会有循环依赖，我们先简化问题，考虑每个物品最多只依赖于一个物品（即依赖关系是一棵树）没有循环依赖的情况：
对于一个主件（不依赖于别人的）和若干个附件（依赖于主件）来说，有以下几种状态：不选主键，那么附件也不能选。选主件，再从附件里选一件。选主件，再从附件里选两件......注意到对于这一个集合来说其实就是一个选主件时的01背包问题+不选主件的一个额外状态，因此我们只需要在树型dp的过程中套上一个树上背包即可。
那如果出现了循环依赖该怎么办呢？对于那些循环依赖的集合，我们要么都选要么都不选，即可以把他们看作一个点，所以我们建图后跑一个tarjan缩点（因为是有向图，所以强连通分量就是环），然后重新建图再树型dp+背包即可。
还有一个小问题，如果这张图不连通怎么办？很简单，我们像网络流那样搞一个超级源点，把每个连通块内入度为0的点连到超级源上即可。
ac代码：
?//https://www.luogu.com.cn/problem/P2515
??
?#include <bits/stdc++.h>
?using namespace std;
?#define visit _visit
?#define next _next
?#define pb push_back
?#define fi first
?#define se second
?#define endl '\n'
?#define fast ios::sync_with_stdio(0), cin.tie(0)
?#define int long long
?#define ll long long
?#define pint pair<int,int>
??
?const int mod = 998244353;
?const int maxn = 110;
?const int INF = 1e18;
??
?void read(int &x){
? int f=1;x=0;char s=getchar();
? while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
? while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
? x*=f;
?}
?ll quick_pow(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
?ll inv(ll x) {return quick_pow(x, mod-2);}
?//----------------------------------------------------------------------------------------------------------------------//
?struct node{
? int ne,to;
?};
?node edge[maxn<<1];
?int head[maxn];
?int cnt=0;
?void addedge(int a,int b){
? edge[cnt].to=b;
? edge[cnt].ne=head[a];
? head[a]=cnt++;
?}
?node n_edge[maxn<<1];
?int n_head[maxn];
?int n_cnt=0;
?void n_addedge(int a,int b){
? n_edge[n_cnt].to=b;
? n_edge[n_cnt].ne=n_head[a];
? n_head[a]=n_cnt++;
?}
?int n,m;
?int w[maxn],v[maxn];
?int n_w[maxn],n_v[maxn];
?int dp[maxn][501];
?int vis[maxn],dfn[maxn],low[maxn],color[maxn],dn,c;
?stack<int>s;
?void tarjan(int x){
? low[x]=dfn[x]=++dn;
? vis[x]=1;
? s.push(x);
? for(int i=head[x];i!=-1;i=edge[i].ne){
? int son=edge[i].to;
? if(dfn[son]==0){
? tarjan(son);
? low[x]=min(low[x],low[son]);
? }else if(vis[son]==1){
? low[x]=min(low[x],dfn[son]);
? }
? }
? if(low[x]==dfn[x]){
? c++;
? while(1){
? int t=s.top();
? s.pop();
? vis[t]=0;
? color[t]=c;
? n_w[c]+=w[t];
? n_v[c]+=v[t];
? if(x==t){
? break;
? }
? }
? }
?}
?int ans;
?int ru[maxn];
?void dfs(int x){
? ? ?for(int i=n_w[x];i<=m;i++){
? ? dp[x][i]=n_v[x];
? }
? ? ?for(int i=n_head[x];i!=-1;i=n_edge[i].ne){
? ? ? ? ?dfs(n_edge[i].to);
? ? ? ? ?for(int j=m-n_w[x];j>=0;j--){
? ? ? ? ? ? ?for(int q=0;q<=j;q++){
? ? ? ? ? ? ? ? ?dp[x][j+n_w[x]]=max(dp[x][j+n_w[x]],dp[x][j+n_w[x]-q]+dp[n_edge[i].to][q]);
? ? ? ? ? ? }
? ? ? ? }
? ? }
?}
?void solve(){
? memset(head,-1,sizeof(head));
? memset(n_head,-1,sizeof(n_head));
? cin>>n>>m;
? for(int i=1;i<=n;i++){
? cin>>w[i];
? }
? for(int i=1;i<=n;i++){
? cin>>v[i];
? }
? for(int i=1;i<=n;i++){
? int fa;
? cin>>fa;
? if(fa==0){
? continue;
? }
? addedge(i,fa);
? }
? for(int i=1;i<=n;i++){
? if(dfn[i]==0){
? tarjan(i);
? }
? }
? for(int i=1;i<=n;i++){
? for(int j=head[i];j!=-1;j=edge[j].ne){
? int son=edge[j].to;
? if(color[son]==color[i]){
? continue;
? }
? n_addedge(color[son],color[i]);
? ru[color[i]]++;
? }
? }
? ? ?for(int i=1;i<=c;i++){
? ? ? ? ?if(ru[i]==0){
? ? ? ? ? ? ?n_addedge(c+1,i);
? ? ? ? }
? ? }
? dfs(c+1);
? cout<<dp[c+1][m]<<endl;
?}
??
?signed main(){
? fast;
? int t=1;
? //cin>>t;
? while(t--){
? solve();
? }
? return 0;
?}但是如果一个物品不止依赖一个父亲呢？emm，没找到题目，口胡一下：缩点+拓扑序dp。
本文仅介绍了部分背包问题，比较经典的还有双背包，状态背包+bitset优化，严格k优解等等，大家感兴趣的可以去自行了解哈。
