[数据结构与算法]有依赖的背包，狭义(二进制枚举)，广义(树形dp)

[NOIP2006 提高组] 金明的预算方案

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 $n$ 元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 $0$ 个、$1$ 个或 $2$ 个附件。每个附件对应一个主件，附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的 $n$ 元。于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1～5$ 表示，第 $5$ 等最重要。他还从因特网上查到了每件物品的价格（都是 $10$ 元的整数倍）。他希望在不超过 $n$ 元的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第 $j$ 件物品的价格为 $v_j$，重要度为$w_j$，共选中了 $k$ 件物品，编号依次为 $j_1,j_2,\dots ,j_k$，则所求的总和为：

$v_{j_1}\times w_{j_1}+v_{j_2}\times w_{j_2}+?+v_{j_k}\times w_{j_k}$。

请你帮助金明设计一个满足要求的购物单。

输入格式

第一行有两个整数，分别表示总钱数 $n$ 和希望购买的物品个数 $m$。

第 $2$ 到第 $(m+1)$ 行，每行三个整数，第 $(i+1)$ 行的整数 $v_i$，$p_i$，$q_i$ 分别表示第 $i$ 件物品的价格、重要度以及它对应的的主件。如果 $q_i=0$，表示该物品本身是主件。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

样例输出 #1

2200

提示

数据规模与约定

对于全部的测试点，保证 $1\le n\le 3.2\times 10^4$，$1\le m\le 60$，$0\le v_i\le 10^4$，$1\le p_i\le 5$，$0\le q_i\le m$，答案不超过 $2\times 10^5$。

有依赖的背包简单版，或者直接叫做分组背包。

你能发现下边的代码哪里错了吗

时间复杂度 $O(nm)$

int n,m;
struct good{
    int v,w;
};
vector<good>g[70];
int f[40010];
void solve(){
    cin>>m>>n;
    fo(i,1,n){
        int v,w,s;cin>>v>>w>>s;
        if(!s){
            g[i].pb({v,w});
        }
        else{
            g[s].pb({v,w});
        }
    }
    for(int j=m;j>=0;j--){
        for(int i=1;i<=n;i++){
        	if(!g[i].size())continue;
            auto p = *g[i].begin();
            // debug(p.v);
            for(int k=0;k<((g[i].size()-1)<<1);k++){
            	// debug(k);
                if(!k){
                    if(j-p.v>=0)
                        f[j] = max(f[j],f[j-p.v]+p.w*p.v);
                }
                else if(k==1 || k==2){
                    auto x = g[i][k];
                    if(j-x.v-p.v>=0)
                        f[j] = max(f[j],f[j-x.v-p.v]+x.w*x.v+p.w*p.v);
                }
                else{
                    auto x = g[i][1];
                    auto y = g[i][2];
                    if(j-x.v-y.v-p.v>=0)
                        f[j] = max(f[j],f[j-x.v-y.v-p.v]+x.w*x.v+y.w*y.v+p.w*p.v);
                }
            }
        }
    }
    cout<<f[m]<<endl;
}

int main(){
    solve();
    return 0;
}

解密：

if(!k){
    if(j-p.v>=0)
        f[j] = max(f[j],f[j-p.v]+p.w*p.v);
}
这句需要放到外边，不然循环不到qwq

有依赖的背包问题,树上背包

一个讲得非常不错的连接

抽象出模型，类比树形dp， $f[u][j]$ 表示以 $u$ 节点为根节点，花费 $j$ 所能得到的最大价值。

考虑每个儿子选还是不选，考虑到儿子的儿子的体积一定是 $1$ 的倍数，所以对 $u$ 节点的所有儿子做分组背包。

先 dfs 进去，回溯的时候做分组背包。

注意初始化

for(int i=v[u];i<=m;i++){
    f[u][i] = w[u];
}

int n,m;
int h[110],e[210],ne[210],idx;
int v[110],w[110];
int f[110][110];// f[u][j] 表示 u 为根的子树花费 j 取得的最大值
int root;
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

void dfs(int u,int fa){
    for(int i=v[u];i<=m;i++){
        f[u][i] = w[u];
    }
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        dfs(j,u);
        for(int k=m;k>=v[u];k--){
            for(int l=0;l<=k-v[u];l++){
                f[u][k] = max(f[u][k],f[u][k-l]+f[j][l]);
            }
        }
    }
}

void solve(){
    memset(h,-1,sizeof(h));
    cin>>n>>m;
    fo(i,1,n){
        int x;
        cin>>v[i]>>w[i]>>x;
        if(x!=-1){
            add(x,i);
            add(i,x);
        }
        else root = i;
    }
    dfs(root,-1);
    cout<<f[root][m]<<endl;
}

int main(){
    solve();
    return 0;
}