NOIP2006 金明的预算 - 依赖背包

作者: 苏子旃 | 来源:发表于2019-02-12 08:24 被阅读8次

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

设第 $j$ 件物品的价格为 $v_j$ ，重要度为 $w_j$ ，共选中了 $k$ 件物品，编号依次为 $j_1,j_2,…,j_k$ ，则所求的总和为： $v_1·w_1 + v_2 ·w_2 + … + v_k · w_k$
请你帮助金明设计方案。

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

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
对于 $100$ %的数据， $0 < N \leq 32000,0 \leq v \leq 10000,1 \leq p \leq 5,0 \leq q \leq M \leq 60$ 。

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

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

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

每个主件可以有 $l$ 个附件，满足 $0 \leq l \leq 60$ 。

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

前置技能

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

不难看出，第一优先级的是主件，然后才是附件。若选择该主件，附件可选可不选；若不选该主件，则附件必不选。
在树形依赖的背包问题中，我们将每颗子树作为一个泛化物品来看。同样，我们可以对每个主件的附件集合进行处理，合成一个新的泛化物品。即对每个主件的附件集合做一次01背包，得到 $f[j],j \in [0,n-v_i]$ ，表示该附件集合在分配体积为 $j$ 的情况下该附件总和的最优值。
也可以这么理解：我们得到了一组新的物品，体积分别为 $v_1',v_2',…$ ，对应总和 $f[v_1'],f[v_2']……$ 这组物品之间互相冲突，在进行选择时只能选取其中一个。

问题转化成了分组背包问题。（其实也是求泛化物品的和）
枚举组别、体积和组别内的物品，更新答案。

本题还涉及严格背包，即数组下标和达到该数组总和的花费严格相等。若不相等，则会导致答生成的新的物品组数量太多而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;
}

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

参考：

背包九讲

NOIP2006 金明的预算 - 依赖背包

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

动态规划