当前位置: 首页 > news >正文

树上背包问题动态规划

目录

树状动态规划概述

示例 

求解思路 


树状动态规划概述

树状动态规划(Tree DP)是一种在树结构上进行动态规划的方法。在树状DP中,我们利用树的特殊结构性质,通过递归地向下更新子节点的状态,最终得到整个树的最优解或其他需要的信息。

树状DP通常包含以下步骤:

  1. 定义状态:根据问题的要求,定义每个节点的状态。这可以是一个数值、一个数组、一个结构体等,取决于问题的具体情况。
  2. 设计转移方程:根据问题的要求,确定每个节点的状态如何从其子节点的状态转移而来。这通常通过遍历节点的子节点,并利用子节点的状态来更新当前节点的状态来实现。
  3. 确定初始状态:确定叶节点的初始状态,这是递归的终止条件。
  4. 递归地进行状态转移:从树的顶部开始,递归地向下进行状态转移,直到所有节点的状态都被计算出来。

示例 

问题描述: 给定一棵有根树,每个节点有两个属性:权重和价值。节点的权重表示该节点所需要的空间,节点的价值表示该节点的价值。现在有一个给定的背包容量,要求选择一些节点放入背包中,使得总权重不超过背包容量,同时总价值最大。

输入:

  • 一棵树的节点数
  • 每个节点的权重和价值
  • 背包容量

输出:

  • 最大的总价值

求解思路 

这个例子是一个经典的背包问题在树结构中的应用。我们需要在给定的一棵有根树中,选择一些节点放入背包中,使得总权重不超过背包容量,同时总价值最大。

为了解决这个问题,我们可以使用动态规划的方法。具体思路如下:

  1. 定义状态:我们定义dp[i][j]表示以节点i为根节点的子树中,在背包容量为j的情况下,可以获得的最大总价值。

  2. 状态转移方程:对于节点i的每个孩子节点child,我们需要考虑两种情况:

    • 不选择child节点:此时dp[i][j]不变。
    • 选择child节点:此时需要从剩余容量j减去child节点的权重,即j - tree[child].weight,并从子问题dp[child][j - tree[child].weight]中得到最大价值,再加上child节点的价值tree[child].value。整体来看,选择child节点后的最大总价值为dp[child][j - tree[child].weight] + tree[child].value。

    综合考虑上述两种情况,我们可以得到状态转移方程:

    dp[i][j] = max(dp[i][j], dp[child][j - tree[child].weight] + tree[child].value)

    其中,child为节点i的孩子节点。

  3. 初始化:我们将dp数组初始化为0,表示初始时没有选择任何节点。

  4. 从根节点开始进行深度优先搜索(DFS),按照上述状态转移方程更新dp数组中的值。最终,dp[1][背包容量]即为所求的最大总价值。

下面是代码中主要部分的解释:

 
void dfs(int node) {for (int child : tree[node].children) {// 对每个孩子节点进行深度优先搜索dfs(child);// 更新dp数组for (int i = dp[node].size() - 1; i >= tree[node].weight; i--) {dp[node][i] = max(dp[node][i], dp[child][i - tree[node].weight] + tree[child].value);}}
}

在dfs函数中,我们首先对当前节点的每个孩子节点进行深度优先搜索。然后,通过一个循环,从dp[node]的最后一个元素开始向前更新dp[node]的值。这里使用了倒序循环的方式,是因为我们需要保证在更新dp[node][i]时,dp[child][i - tree[node].weight]已经被计算过(即在dp[node]的前面位置)。同时,我们需要确保总权重不超过背包容量,所以我们从tree[node].weight开始遍历。

最后,在主函数中,我们输入节点数和每个节点的权重、价值信息,构建树结构,并调用dfs函数进行求解。最终结果存储在dp[1][背包容量]中。

希望以上详细解释能够帮助你理解这个树状动态规划问题的解决方法。如有任何疑问,请随时提出。

示例:

输入:
节点数 = 5
节点 1: 权重 = 2, 价值 = 3
节点 2: 权重 = 1, 价值 = 2
节点 3: 权重 = 3, 价值 = 4
节点 4: 权重 = 2, 价值 = 2
节点 5: 权重 = 1, 价值 = 1
背包容量 = 5输出:
最大总价值 = 9

C++代码实现:

#include <iostream>
#include <vector>
using namespace std;struct Node {int weight;int value;vector<int> children;
};vector<Node> tree;  // 存储树节点的信息
vector<vector<int>> dp;  // 存储动态规划的结果void dfs(int node) {for (int child : tree[node].children) {dfs(child);for (int i = dp[node].size() - 1; i >= tree[node].weight; i--) {dp[node][i] = max(dp[node][i], dp[child][i - tree[node].weight] + tree[child].value);}}
}int main() {int n;  // 节点数cin >> n;tree.resize(n + 1);  // 从编号1开始存储节点信息dp.resize(n + 1, vector<int>(n + 1, 0));  // 初始化动规数组for (int i = 1; i <= n; i++) {cin >> tree[i].weight >> tree[i].value;}// 构建树结构for (int i = 2; i <= n; i++) {int parent;cin >> parent;tree[parent].children.push_back(i);}dfs(1);  // 从根节点开始进行深度优先搜索cout << "最大总价值 = " << dp[1][n] << endl;return 0;
}

这段代码首先通过输入构建了一棵树,并使用动态规划方法计算了最大总价值。其中,dfs函数进行了深度优先搜索和动态规划的计算,dp数组用于存储动态规划的结果。

相关文章:

树上背包问题动态规划

目录 树状动态规划概述 示例 求解思路 树状动态规划概述 树状动态规划&#xff08;Tree DP&#xff09;是一种在树结构上进行动态规划的方法。在树状DP中&#xff0c;我们利用树的特殊结构性质&#xff0c;通过递归地向下更新子节点的状态&#xff0c;最终得到整个树的最…...

linux查看进程对应的线程(数)

首先&#xff0c;top或ps查看进程列表&#xff0c;确定要查看的进程pid&#xff0c;如下面40698 查看进程的线程情况 查看进程&#xff1a;top -p 40698 查看线程&#xff1a;top -p 40698 -d 3 -H 其中-d是刷新频率 可看到此进程共211个线程&#xff0c;运行中的是211个。…...

Python中的桌面应用开发库有哪些?

Python中有几个受欢迎的桌面应用开发库。以下是其中一些&#xff1a; Tkinter&#xff1a;这是Python的标准GUI库&#xff0c;它提供了构建简单的桌面应用程序的基本组件和功能。 PyQt&#xff1a;这是一个成熟的、功能强大的跨平台图形用户界面框架&#xff0c;它是Python绑定…...

【大数据】Neo4j 图数据库使用详解

目录 一、图数据库介绍 1.1 什么是图数据库 1.2 为什么需要图数据库 1.3 图数据库应用领域 二、图数据库Neo4j简介 2.1 Neo4j特性 2.2 Neo4j优点 三、Neo4j数据模型 3.1 图论基础 3.2 属性图模型 3.3 Neo4j的构建元素 3.3.1 节点 3.3.2 属性 3.3.3 关系 3.3.4 标…...

Windows11系统C盘用户文件夹下用户文件夹为中文,解决方案

说明&#xff1a; 1. 博主电脑为Windows11操作系统&#xff0c;亲测有效&#xff0c;修改后无任何影响&#xff0c;软件都可以正常运行&#xff01; 2. Windows10系统还不知道可不可行&#xff0c;因为Windows11的计算机管理中没有本地用户和组&#xff0c;博主在csdn上看到很…...

Python正则表达式(re)

正则表达式&#xff0c;又称规则表达式,&#xff08;Regular Expression&#xff0c;在代码中常简写为regex、regexp或RE&#xff09;&#xff0c;是一种文本模式&#xff0c;包括普通字符&#xff08;例如&#xff0c;a 到 z 之间的字母&#xff09;和特殊字符&#xff08;称为…...

【PyTorch 08】如果要手动安装对应的包

例如有时候我们要下载 PyG &#xff0c;但是需要手动下载&#xff0c;需要进行以下步骤&#xff1a; 网站链接&#xff1a;https://data.pyg.org/whl/ 首先查看当前安装好的Pytorch版本和对应的cuda版本 1. pip list&#xff1a;查看torch版本 2. torch.version.cuda&#xf…...

黑马JVM总结(十二)

&#xff08;1&#xff09;五种引用_强软弱 实线箭头表示强引用&#xff0c;虚心线表示软弱虚终结器引用 在平时我们用的引用&#xff0c;基本都为强引用 &#xff0c;比如说创建一个对象通过运算符赋值给了一个变量&#xff0c;那么这个变量呢就强引用了刚刚的对象 强引用的…...

彻底搞懂线程池原理以及创建方式

1. 为什么要使用线程池 在实际使用中&#xff0c;线程是很占用系统资源的&#xff0c;如果对线程管理不善很容易导致系统问题。因此&#xff0c;在大多数并发框架中都会使用线程池来管理线程&#xff0c;使用线程池管理线程主要有如下好处&#xff1a; 降低资源消耗。通过复用…...

FreeSWITCH 1.10.10 简单图形化界面9 - 鼎兴FXO网关SIP中继内网IPPBX落地

FreeSWITCH 1.10.10 简单图形化界面9 - 鼎兴FXO网关SIP中继内网IPPBX落地 0、 界面预览1、创建一个话务台2、创建PBX SIP中继并设置呼入权限3、设置呼出规则4、设置分机呼出权限5、设置FXO 网关相关信息6、设置FXO网关端口组呼入号码7、设置FXO网关的SIP中继8、设置FXO网关呼叫…...

Oracle数据如何迁移导入到MySQL

使用Navicat工具建立数据连接&#xff0c;进行数据传输 1、打开Navicat工具&#xff0c;分别连接Oracle数据库和MySQL数据库。 2、连接源选择你的oracle数据&#xff0c;目标选mysql 即可成功导入...

卡尔曼滤波(Kalman Filter)原理浅析-数学理论推导-1

目录 前言数学理论推导1. 递归算法2. 数学基础结语参考 前言 最近项目需求涉及到目标跟踪部分&#xff0c;准备从 DeepSORT 多目标跟踪算法入手。DeepSORT 中涉及的内容有点多&#xff0c;以前也就对其进行了简单的了解&#xff0c;但是真正去做发现总是存在这样或者那样的困惑…...

Linux 文件创建、查看

touch、cat、more命令 ①touch命令——创建文件 ②cat命令——查看文件内容全部显示 这是txt.txt文件内容 使用cat命令查看 ③more命令——查看文件内容支持翻页 在查看的过程中&#xff0c;通过空格翻页&#xff0c;通过q退出查看...

WPF 如何让xmal的属性换行显示 格式化

WPF 如何让UI的xmal 按照下面的格式化显示 首先格式化显示在VS中的快捷键是 Ctrl &#xff2b;D 然后需要配置&#xff0c;工具 选项 -文本编辑器 -xmal -格式化-间距 更改成如下就可以了...

Linux学习之MySQL主从复制

MySQL配置一主一从 环境准备&#xff1a; 两台服务器&#xff1a; Master&#xff1a;192.168.88.53&#xff0c;Slave&#xff1a;192.168.88.54 在两台服务器上安装mysql-server # 配置主服务器192.168.88.53 # 启用binlog日志 [rootmysql53 ~]# yum -y install mysql-ser…...

【JavaSE笔记】抽象类与接口

一、抽象类 1、概念 在面向对象的概念中&#xff0c;所有的对象都是通过类来描绘的&#xff0c;但是反过来&#xff0c;并不是所有的类都是用来描绘对象的&#xff0c;如果一个类中没有包含足够的信息来描绘一个具体的对象&#xff0c;这样的类就是抽象类。 package demo2…...

详谈操作系统中的内核态和用户态

不知道大家有没有思考过这样一个问题:什么是处理器&#xff08;CPU&#xff09;的状态&#xff1f;&#x1f914; 其实CPU和人一样,没有执行程序的时候,是没有什么状态的,当它执行的程序是用户程序的时候就叫用户态&#xff0c;当执行的程序是操作系统的代码时就叫系统态或者内…...

OpenWrt KernelPackage分析

一. 前言 KernelPackage是OpenWrt用来编译内核模块的函数&#xff0c;其实KernelPackage后面会调用BuildPackage&#xff0c;这里会一块将BuildPackage也顺便分析&#xff0c;本文以gpio-button-hotplug驱动模块为例&#xff0c;讲解整个编译过程。 gpio-button-hotplug驱动编译…...

第 363 场 LeetCode 周赛题解

A 计算 K 置位下标对应元素的和 模拟 class Solution { public:int pop_cnt(int x) {//求x的二进制表示中的1的位数int res 0;for (; x; x >> 1)if (x & 1)res;return res;}int sumIndicesWithKSetBits(vector<int> &nums, int k) {int res 0;for (int i…...

ffplay源码解析-main入口函数

main入口函数 初始化 变量、缓存区、SDL窗口初始化等 int main(int argc, char **argv) {int flags;VideoState *is; // av_log_set_level(AV_LOG_TRACE);init_dynload();av_log_set_flags(AV_LOG_SKIP_REPEATED);parse_loglevel(argc, argv, options);/// av_log_set_le…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

【Linux】自动化构建-Make/Makefile

前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具&#xff1a;make/makfile 1.背景 在一个工程中源文件不计其数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c;mak…...