不止一个背包的背包问题_超级背包怎么使用方法

不止一个背包的背包问题_超级背包怎么使用方法有 N 个物品和一个容量是 V 的背包。物品之间具有依赖关系,且依赖关系组成一棵树的形状。如果选择一个物品,则必须选择它的父节点。如下图所示:如果选择物品5,则必须选择物品1和2。这是因为2是5的父节点,1是2的父节点。每件物品的编号是 i,体积是 vi,价值是 wi,依赖的父节点编号是 pi。物品的下标范围是 1…N。求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。输出最大价值。输入格式第一行有两个整数 N,V,用空格隔开,分别表示物品个数和背包容量。接下来有 N

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

有 N 个物品和一个容量是 V 的背包。

物品之间具有依赖关系,且依赖关系组成一棵树的形状。如果选择一个物品,则必须选择它的父节点。

如下图所示:
QQ图片20181018170337.png

如果选择物品5,则必须选择物品1和2。这是因为2是5的父节点,1是2的父节点。

每件物品的编号是 i,体积是 vi,价值是 wi,依赖的父节点编号是 pi。物品的下标范围是 1…N。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

输出最大价值。

输入格式
第一行有两个整数 N,V,用空格隔开,分别表示物品个数和背包容量。

接下来有 N 行数据,每行数据表示一个物品。
第 i 行有三个整数 vi,wi,pi,用空格隔开,分别表示物品的体积、价值和依赖的物品编号。
如果 pi=−1,表示根节点。 数据保证所有物品构成一棵树。

输出格式
输出一个整数,表示最大价值。

数据范围
1≤N,V≤100
1≤vi,wi≤100
父节点编号范围:

内部结点:1≤pi≤N;
根节点 pi=−1;

输入样例
5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2
输出样例:
11
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int M = N;
struct Edge{ 
   
    int v,next;
}edge[M];
int head[N],cnt;
void add(int u,int v){ 
   
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
int v[N],w[N];
int f[N][M];
int n,m,p;
void dfs(int u){ 
   
    for(int i = head[u];~i;i = edge[i].next){ 
   
        int ver = edge[i].v;
        dfs(ver);
        for(int j = m;j >= 0;j --){ 
     
            for(int k = 0;k <= j;k ++){ 
   
                f[u][j] = max(f[u][j],f[u][j - k] + f[ver][k]);
            }
        }
    }
    for(int j = m;j >= v[u];j --)f[u][j] = f[u][j - v[u]] + w[u];
    for(int j = 0;j < v[u];j ++)f[u][j] = 0;
    
}
int main(){ 
   
    cin>>n>>m;
    memset(head,-1,sizeof head);
    int root = -1;
    for(int i = 1;i <= n;i ++){ 
   
        cin>>v[i]>>w[i]>>p;
        if(p == -1)root = i;
        else add(p,i);
    }
    dfs(root);
    cout<<f[root][m];
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169152.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • sql嵌套查询效率_sql嵌套查询返回多个字段

    sql嵌套查询效率_sql嵌套查询返回多个字段文章目录问题解决问题为了查询一个字段,使用了五层嵌套循环,但是花费了约1分钟但是5个表的数据每个最多只有10条,怎么会这么慢呢?解决比如查询语句SELECT*FROMstudet分析器会先看语句的第一个词,如果它发现第一个词是SELECT关键字的时候,它会跳到FROM关键字,然后通过FROM关键字找到表名并把表装入内存。内存中有student表接着是找WHERE关键字,如果找不到则返回到SELECT找字段解析SELECT*FROMstudetWHEREstu_id=1

  • 堆和栈的差别(转过无数次的文章)

    堆和栈的差别(转过无数次的文章)

  • 交叉编译lrzsz

    交叉编译lrzsz参考:https://blog.csdn.net/linucos/article/details/5582979https://blog.csdn.net/wangzhen209/article/details/32713715https://blog.csdn.net/zijie_xiao/article/details/50934279步骤:获取源码:https://www…

  • python读取modis数据

    python读取modis数据本期记录只上干活,废话不多说,主要是后面与HEG配合使用,实现一系列研究与反演操作。python环境:Python3.5.2+Pycharm模块包:pyhdf安装方法(命令行输入):pipinstallpyhdf一、获取hdf数据集:frompyhdf.SDimportSDHDF_FILR_URL=”E:\Persona_project\Py-Pro…

  • python——循环(for循环、while循环)及练习

    python——循环(for循环、while循环)及练习目标程序的三大流程1.while循环的基本使用 2.break和continue 3.while循环嵌套在程序开发中,一共有三种流程方式:顺序:从上向下,顺序执行代码 分支:根据条件判断,决定执行代码的分支 循环:让特定代码重复执行(解决程序员重复工作)一、for循环1、基本用法for循环使用的语法:“”"for变量inrange(10):循环…

  • mapminmax 用法[通俗易懂]

    mapminmax 用法[通俗易懂]mapminmax是MATLAB实现归一化的工具包,默认:(1)将矩阵的每行分别进行归一化;(2)每行的最大值最小值作为每行归一化的xmin和xmax;(3)将数据归一化到[-1,1].若要将数据归一化到0到1之间,即y∈[0,1],使用b=mapminmax(a,0,1);若给与确定的最大值和最小值作为每行的xmin和xmax,使用:b= mapminmax(a,0,1);PS.xmin…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号