Acwing.10有依赖的背包问题(树型DP,分组背包)xiaodangao

题目链接：Acwing.10 有依赖的背包问题(树型DP,分组背包)
思路：模板题，从上到下考虑每一个节点，数组f[i][j]第一维表示选择第i个节点，第二维表示体积，然后我们对于一颗子树和他的若干儿子节点这样想，第一步，处理他的儿子节点，由于对于他每一个儿子节点，他只能选择一个体积，所以这就变成了每一个儿子节点为一组的分组背包问题，对于n个儿子节点，分组01背包求Max，最后需要注意的是，由于是必须选择它本身，所以我们f[i][j]最后要加上个w[i];

$Coding:$


#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define bep(i,a,b) for(int i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
const int N = 110;
int n,V;
int v[N],w[N];
int f[N][N];
vector<int>G[N];
void dfs(int id,int t){
    for(auto p:G[id]){
        int maxn = t - v[id];
        dfs(p,maxn);
        bep(i,maxn,0){
            rep(j,0,i){
                f[id][i] = max(f[id][i-j] + f[p][j],f[id][i]);
            }
        }
    }
    bep(i,t,v[id])f[id][i] = f[id][i-v[id]] + w[id];
    rep(i,0,v[id]-1)f[id][i] = 0;
}
void solve(){
    read(n);read(V);
    rep(i,1,n){
        int x,y,z;
        read(x);read(y);read(z);
        if(z == -1){
            G[0].pb(i);
        }
        else G[z].pb(i);
        v[i] = x;w[i] = y;
    }
    dfs(0,V);
    write(f[0][V]);pc('\n');
}
signed main(){
    solve();
    return 0;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。