依赖背包优化——ural1018

发布时间：2020-12-14 04:49:23 所属栏目：百科来源：网络整理

导读：经典题了，网上博客一大堆O(nCC)的做法，其实是可以将复杂度降到O(nC)的参考依赖背包优化（泛化物品的并）根据背包九讲，求两个泛化物品的和复杂度是O(CC)的，所以依赖背包暴力求解的复杂度是O(nCC) 然后对其进行优化，考虑 F[u][j] 用来表示以结点u为根的

经典题了，网上博客一大堆O(nCC)的做法，其实是可以将复杂度降到O(nC)的

参考依赖背包优化（泛化物品的并）

根据背包九讲，求两个泛化物品的和复杂度是O(CC)的，所以依赖背包暴力求解的复杂度是O(nCC)

然后对其进行优化，考虑 F[u][j] 用来表示以结点u为根的子树(不包括u)体积为j的全局最大价值
枚举u的儿子v，求F[v][j]数组，因为要求以v为根的子树，必须先选v，所以把v强行塞到背包里
即通过F[v][j]=F[u][j]+W[v] (j<=C-V[v])这个赋值来表示j子树的最大体积不会超过C-V[v]，并且已经选了v
然后dfs求出F[v][j]的值，此时按照定义已经得到了一个新的泛化物品，即一定包含v，并且可能包含v子树元素与前面几棵子树元素的背包，
我们拿这个背包和之前的背包(即一定不包含v的子树)进行合并，去更新F[u],F[u][j]=max(F[u][j],F[v][j-V[v]])
即F[u]在体积为j的时候要么保持原来的值，不取v子树的任何物品，要么取一些v子树的物品，那么显然v物品也要被取

即每次处理完一个u的子树v后，我们就得到了一个和当前泛化物品有交集(或者说是严格的后者包含前者，因为加了一整棵v的子树(除了v没加)进去)的新的泛化背包，我们对其求并，复杂度是O(C)，因为对于每个体积，我们只要求两者在该体积下的最大价值即可，当然新的泛化物品因为要强行塞入v，所以最后对应的体积也会偏移V[v]、

加深理解：一整棵子树v是如何逐步加入到决策集合中的。在dfs进入v子树后，会再遍历v的子树w，然后把w强行塞入背包，塞入背包说明前面一定会有一些物品x被挤出必选v的最佳决策集合中，那么回溯的时候我们考虑是选w还是选择x更优，最后回溯到v的时候，整个v的子树已经决策好了。

#include<bits/stdc++.h>
using namespace std;
#define N 205
struct Edge{int to,nxt,w;}e[N<<1];
int head[N],tot,n,q;
void init(){memset(head,-1,sizeof head);tot=0;}
void add(int u,int v,int w){
    e[tot].w=w;e[tot].to=v;e[tot].nxt=head[u];head[u]=tot++;
}
int F[N][N];
void dfs(int u,int pre,int C){
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre)continue;
        for(int j=0;j<=C-1;j++)
            F[v][j]=F[u][j]+e[i].w;
        dfs(v,u,C-1);
        for(int j=1;j<=C;j++)
            F[u][j]=max(F[u][j],F[v][j-1]);
    } 
}

int main(){
    while(cin>>n>>q){
        init();
        for(int i=1;i<n;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(v,w);add(u,w);
        }
        memset(F,0,sizeof F);
        dfs(1,0,q);
        cout<<F[1][q]<<endl;
    }
}

?这个题要加一个虚根，用暴力显然是过不了的。所以要优化后的依赖背包来做

#include<bits/stdc++.h>
using namespace std;
#define N 65
#define M 32005
#define ll long long
struct Edge{int to,nxt;}e[N<<1];
int head[N],tot;
void init(){memset(head,int v){
    e[tot].to=v;e[tot].nxt=head[u];head[u]=tot++;
}

int dp[N][M],V[N],W[N],C;
void dfs(int u,int C){
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre)continue;
        for(int j=0;j<=C-V[v];j++)
            dp[v][j]=dp[u][j]+V[v]*W[v];
        dfs(v,C-V[v]);
        for(int j=V[v];j<=C;j++)
            dp[u][j]=max(dp[u][j],dp[v][j-V[v]]);
    }
}

int main(){
    while(cin>>C>>n){
    init();
    for(int i=1;i<=n;i++){
        int fa;
        scanf("%d%d%d",&V[i],&W[i],&fa);
        add(i,fa);add(fa,i);//增加一个0结点 
    }
    memset(dp,sizeof dp);
    dfs(0,C);
    int ans=0;
    for(int j=0;j<=C;j++)ans=max(ans,dp[0][j]);
    cout<<ans<<endl;
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!