处理为泛化物品的一个做法(未实现)求大佬过目

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

张奕涵 @ 2017-08-09 20:13:06

看了九讲的泛化物品之后想出的一个做法，不能说完全理解，但还是有这样的一点个人看法吧。

1，按照物品组处理为多个泛化物品

既然有主件和附件之分，选附件必须要选主件，那么也就是说，可以把整个物品组看成一个泛化物品，当分配给它的价值小于主件所需价值时，反馈价值为0。当超过主件价值时，反馈价值至少为主件的反馈价值。而在分配价值逐渐上升的时候，会发现达到主件加上某个附件的价值，继续上升就出现了矛盾，到底选择哪个附件才是最优方案？只需取当前价值下的max即可。分配价值不断上升而不因前面被置成不同物品而不同。

【举个栗子】

有这样一个物品组：（v,p）

主件：200 4 附件1:100 3 附件2:150 3

设f[i]表示分配给这个物品组i价值时能得到的最大反馈。

那么显然，f[0..199]=0,f[200..299]=800,f[300..349]=1100,f[350..449]=1250,f[450..n]=1550。

2，计算所有泛化物品的和

弱弱的说一句具体我也并不很懂

由于两个泛化物品的和为：“如果给定了两个泛化物品 h 和 l ，要用一定的费用从这两个泛化物品中得到最大的价值，这个问题怎么求呢？事实上，对于一个给定的费用 v ，只需枚举将这个费用如何分配给两个泛化物品就可以了。同样的，对于 0...V 中的每一个整数 v ，可以求得费用 v 分配到 h 和 l 中的最大价值 f(v) 。也即

f(v) = max {h(k) + l(v − k) | 0 ≤ k ≤ v}”（引自背包九讲O(v2)，这里讲的很清楚，我自己写肯定讲不清楚orz）

那么只需要不断地累加这些泛化物品（可以用一个ans，从1到物品组数去加，最后输出），就可以求出这个问题最后的答案。这样的话，面对附件更多的问题就可以有这样一个通用的解法，而不用去枚举方案。

以上皆为个人观点，欢迎大佬们批评指正！如果有什么讲的不明白的地方也欢迎留言交流！

by panda_2134 @ 2017-08-10 11:14:26

我记得背包九讲上面说了这个题目的一般情况的。。。

实际上这里泛化物品的处理没必要暴力求解泛化物品，01+分组背包可以解决。

对于一个主件-附件组，假设主件的价值为w_0，体积为v_0，附件的价值为w_i，v_i的话，那么对于给定体积V的泛化物品的话，如果不能装下主件，反馈价值一定为0，如果装的下主件，就考虑在V-v_0的体积中去装附件。这里用01背包可以处理出这个泛化物品的反馈价值。显然对于同一个给定的泛化物品体积V，反馈价值越大越好。

然后把体积为v_0一直到v_0+\sum v_i的这些泛化物品看作在同一个物品组里面。由于分组背包每组最多取一个，在这个物品组里面跑分组背包就行。

本人蒟蒻，说错了欢迎吐槽orz

by panda_2134 @ 2017-08-12 19:41:37

这里是本蒟蒻的50pts代码，泛化背包写的，不知道哪里错了qwq

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
const int MAXN = 60, MAXV = 32000, INF = 0x3f3f3f3f;
int V,N,w[MAXN+10],c[MAXN+10],dep[MAXN+10][10],genItem[MAXV+10],opt[MAXV+10];
int main(){
    scanf("%d%d",&V,&N);
    V/=10;
    for(int i=1; i<=N; i++) {
        static int v,p,q;
        scanf("%d%d%d",&v,&p,&q);
        c[i]=v/10;w[i]=v*p;
        dep[q][++dep[q][0]]=i;
    }
    for(int i=1; i<=dep[0][0]; i++) {
        static int mainItem,subItem;
        mainItem=dep[0][i];
        for(int j=V; j>=0; j--) 
            if(j>=c[mainItem])
                genItem[j]=w[mainItem];
            else
                genItem[j]=-INF; 
        for(int j=1; j<=dep[mainItem][0]; j++) {
            subItem=dep[mainItem][j];
            for(int k=V; k>=c[mainItem]+c[subItem]; k--) 
                genItem[k]=max(genItem[k],genItem[k-c[subItem]]+w[subItem]);
        }
        for(int j=V; j>=c[mainItem]; j--)
            for(int k=c[mainItem]; k<=j; k++)
                 opt[j]=max(opt[j],opt[j-k]+genItem[k]);
    }
    printf("%d\n",opt[V]);
}

by joyemang33 @ 2017-08-12 20:15:43

您想说的是不是，对于附件没有从属主件的情况，可以把一个主件以及它的所有附件看成一组，然后对于每一组做一次背包，求出给这一组分配某一体积的最大价值，然后对于再对所有组做一次背包算出总贡献

实际上对于附件依赖主件件的情况，可以把之前说到的分成一组更具体的构成一棵树，表示子节点依赖父亲，对每一颗树进行一次树形DP，F[i][j]表示对第i个节点以及其子树分配 j 空间的贡献，对于每一组分配j的贡献实际上就是改组的树的根节点u的F[u][j]，然后再做一次正常的DP就可以求出解了，不是很明白和泛化物品有什么太大的关系Orz

by panda_2134 @ 2017-08-21 10:57:34

@mangoyang 讲道理树上背包就是求解泛化物品啊

by panda_2134 @ 2017-08-21 12:03:25

@jn15张奕涵好的我知道我上面那个泛化背包哪里错了

数组开小了。。。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#define max(x,y) ((x)>(y)?(x):(y))

using namespace std;
const int MAXN = 60, MAXV = 32000, INF = 0x3f3f3f3f;
int V,N,w[MAXN+10],c[MAXN+10],dep[MAXN+10][MAXN+10],genItem[MAXV+10],opt[MAXV+10];

int main(){
    scanf("%d%d",&V,&N);
    V/=10;
    for(int i=1; i<=N; ++i) {
        static int v,p,q;
        scanf("%d%d%d",&v,&p,&q);
        c[i]=v/10;w[i]=v*p;
        dep[q][++dep[q][0]]=i;
    }
    for(register int i=1; i<=dep[0][0]; ++i) {
        register int mainItem,subItem;
        mainItem=dep[0][i];
        for(register int j=V; j>=c[mainItem]; j--)
            genItem[j]=w[mainItem];
        for(register int j=c[mainItem]-1; j>=0; j--)
                genItem[j]=-INF; 
        for(register int j=1; j<=dep[mainItem][0]; ++j) {
            subItem=dep[mainItem][j];
            for(register int k=V; k>=c[mainItem]+c[subItem]; --k) 
                genItem[k]=max(genItem[k],genItem[k-c[subItem]]+w[subItem]);
        }
        for(register int j=V; j>=c[mainItem]; j--)
            for(register int k=c[mainItem]; k<=j; ++k)
                 opt[j]=max(opt[j],opt[j-k]+genItem[k]);
    }
    printf("%d\n",opt[V]);
}

by panda_2134 @ 2017-08-21 12:03:48

以及泛化背包最后一组数据有点卡常数?

by 张奕涵 @ 2017-08-23 12:31:47

大佬。。。大佬。。。