首页 / 算法 / 《算法竞赛进阶指南》0x54树形DP 背包类树形DP Acwing 286选课

《算法竞赛进阶指南》0x54树形DP 背包类树形DP Acwing 286选课

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了《算法竞赛进阶指南》0x54树形DP 背包类树形DP Acwing 286选课，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1051字，纯文字阅读大概需要2分钟。

内容图文

题目链接：https://www.acwing.com/video/472/

给定n门课，存在先修关系，构成一个森林，修一门课之前他的先修课程一定要完成，问在选m门课的情况下最多能获得多少学分？

如果没有先修规则就是一个裸的01背包问题。但这个问题不能用01背包解决。

而是一个分组背包问题，设f[x,j]为x为根的子树中修j门的最大学分数，从结点x出发，子树的数量就是分组的数量，背包的容量从0-j-1，每个分组中第k个物品的体积是k。

在每个点的子树处理完之后都要加上该点的分数，如果是虚拟节点x，选中之后加上的学分是0。在算体积为i时刻的学分数时用的是i-1时刻的最大学分数，所以要倒叙保证在计算i之前i-1没有改变。

代码：
 

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
usingnamespace std;
constint maxn = 310;
int n,m;
int f[maxn][maxn];
int w[maxn];
vector<int> G[maxn];

void dfs(int x){
    for(int i=0;i<G[x].size();i++){//物品 int y=G[x][i];
        dfs(y);
        for(int j=m-1;j>=0;j--)//体积 for(int k=1;k<=j;k++){//决策 
                f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]);
            }
    }
    if(x!=0)
        for(int i=m;i;i--)
            f[x][i]=f[x][i-1]+w[x];//加上必须课程，反向跌代 }
int main(){
    cin>>n>>m;
    int p;
    for(int i=1;i<=n;i++){
        cin>>p>>w[i];
        G[p].push_back(i);
    }
    m++;//加上了虚拟节点0,0也算一个 
    dfs(0);
    cout<<f[0][m]<<endl;
    
    return0;
}

 

原文：https://www.cnblogs.com/randy-lo/p/13405803.html

内容总结

以上是互联网集市为您收集整理的《算法竞赛进阶指南》0x54树形DP 背包类树形DP Acwing 286选课全部内容，希望文章能够帮你解决《算法竞赛进阶指南》0x54树形DP 背包类树形DP Acwing 286选课所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1290285.html

来源：【匿名】