NOIP2006 金明的预算 - 依赖背包

链接：LUOGU 1064
难度 普及+
Description
金明有元钱，有个想买的物品。这些物品分为两类：主件与附件。如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有个、个或个附件。附件不再有从属于自己的附件。
金明想买的东西很多，于是对于每件物品规定了一个重要度，用整数表示。他还从网上查到了每件物品的价格（都是10的整数倍）。
他希望在花费不超过N的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第件物品的价格为​，重要度为，共选中了件物品，编号依次为，则所求的总和为：
请你帮助金明设计方案。

Input Format
第1行，两个用空格隔开正整数，分别表示总钱数和希望购买的物品总件数。
第2行到第m+1行，第行代表编号为的物品，每行3个非负整数，分别表示该物品的价格该物品的重要度和表示该物品所依附的主件。特别的，若，则表示该物品是主件。

Output Format
一行一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值。

Sample Input

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

Sample Output

2200

Constraints
对于%的数据，。

CCYOS
没想到这又是一道我做过的题目。
因为限定了附件的个数小于等于2，所以可以直接对主件dp：

取0个附件，取1个附件，取2个附件。

代码不放了。
更改一下题目的条件：

每个主件可以有个附件，满足。

这个时候就可以光明正大地写依赖背包了。

前置技能

• 01背包
• 分组背包
  有件物品和一个容量为的背包。第件物品的费用是，价值是 。这些物品被划分为组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
• 泛化物品理解

1. 不难看出，第一优先级的是主件，然后才是附件。若选择该主件，附件可选可不选；若不选该主件，则附件必不选。
   在树形依赖的背包问题中，我们将每颗子树作为一个泛化物品来看。同样，我们可以对每个主件的附件集合进行处理，合成一个新的泛化物品。即对每个主件的附件集合做一次01背包，得到，表示该附件集合在分配体积为的情况下该附件总和的最优值。
   也可以这么理解：我们得到了一组新的物品，体积分别为，对应总和这组物品之间互相冲突，在进行选择时只能选取其中一个。
2. 问题转化成了分组背包问题。（其实也是求泛化物品的和）
   枚举组别、体积和组别内的物品，更新答案。
3. 本题还涉及严格背包，即数组下标和达到该数组总和的花费严格相等。若不相等，则会导致答生成的新的物品组数量太多而TLE。

我的第一次代码

开启O2和不开启O2

using namespace std;

int n,m,co[65],va[65],dp[65][32005],F[32005];
vector<int> q[65];

inline int read(){
    char c = getchar();
    int fl = 1,ret = 0;
    for(;!isdigit(c) && c != '-';c = getchar())if(c == '-')fl = 0;
    for(;isdigit(c);c = getchar())ret = (ret << 3) + (ret << 1) + c - 48;
    return fl ? ret : -ret;
}


int main(){
    n = read();m = read();
    for(int i = 1;i <= m;++i){
        co[i] = read();va[i] = read();
        int fa = read();
        q[fa].push_back(i);
    }
    int nu = q[0].size();
    
    for(int i = 0;i < nu;++i){
        int num = q[q[0][i]].size();
        int now = q[0][i];
        dp[i + 1][co[now]] = co[now] * va[now]; 
        for(int j = 0;j < num;++j){
            for(int v = n;v >= co[q[now][j]] + co[now];--v){
                    dp[i + 1][v] = max(dp[i + 1][v],dp[i + 1][v - co[q[now][j]]] + co[q[now][j]] * va[q[now][j]]);
            }
        }
    }
    for(int i = 1;i <= nu;++i)
        for(int j = n;j;--j)
            for(int v = 1;v <= j;++v){
                F[j] = max(F[j],F[j - v] + dp[i][v]);
            }
    printf("%d\n",F[n]);
    return 0;
}

没有采用严格背包，而且没有单独存储新的物品组，T得非常惨。
code

#include<bits/stdc++.h>
using namespace std;

int n,m;
int t[65]/*表示第i个物品有多少个附件*/,cnt[65]/*表示第i个物品01背包后产生的物品组的物品数量*/,V[65][32005],/*新物品组的对应体积*/P[65][32005]/*新物品组的对应总和*/,f[32005]/*可重复利用*/;
struct stu{
    int co,va,fa;
}th[65],fj[62][62];//输入物品和附件存储。

inline int read(){
    char c = getchar();
    int fl = 1,ret = 0;
    for(;!isdigit(c) && c != '-';c = getchar())if(c == '-')fl = 0;
    for(;isdigit(c);c = getchar())ret = (ret << 3) + (ret << 1) + c - 48;
    return fl ? ret : -ret;
}

int main(){
    n = read();m = read();
    for(int i = 1;i <= m;++i){
        th[i].co = read();th[i].va = read();th[i].fa = read();
        if(th[i].fa){
            ++t[th[i].fa];
            fj[th[i].fa][t[th[i].fa]] = th[i];
        }
    }
    for(int i = 1;i <= m;++i){
        if(t[i]){//是带有附件的主件
            memset(f,-1,sizeof f);//严格背包的预处理
            f[0] = 0;
            for(int j = 1;j <= t[i];++j)
                for(int v = n - th[i].co;v >= fj[i][j].co;--v)
                if(f[v] < f[v - fj[i][j].co] + fj[i][j].co * fj[i][j].va && f[v - fj[i][j].co] != -1)//严格背包判断
                f[v] = f[v - fj[i][j].co] + fj[i][j].co * fj[i][j].va;
            for(int j = 0;j <= n - th[i].co;++j)//把物品组更新到数组中去，注意添加该主件的体积和总和
                if(f[j] != -1){
                    ++cnt[i];
                    V[i][cnt[i]] = j + th[i].co;//+主件体积！！！
                    P[i][cnt[i]] = f[j] + th[i].co * th[i].va;
                }
        }
        if(!th[i].fa){//考虑单独买主件
            ++cnt[i];
            V[i][cnt[i]] = th[i].co;
            P[i][cnt[i]] = th[i].co * th[i].va;
        }
    }
    memset(f,0,sizeof f);
    for(int i = 1;i <= m;++i)
        for(int j = n;j;--j)
            for(int k = 1;k <= cnt[i];++k){
                if(j >= V[i][k])//注意是>=否则答案会偏小
                    f[j] = max(f[j],f[j - V[i][k]] + P[i][k]);
            }//分组背包
    int ans = 0;
    for(int i = 1;i <= n;++i)ans = max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}

最后，作为树形依赖的一种“特殊情况”，本题可以用树形依赖的思想解题。

参考：

• 背包九讲