首页 > 其他分享 >背包DP——依赖背包

背包DP——依赖背包

时间:2024-07-02 15:46:16浏览次数:14  
标签:背包 要么 依赖 分组 物品 DP

依赖背包

部分物品对其他物品有依赖性,即在拥有b前,必须拥有a;

其本质是分组背包,不过具有特殊性,即依赖条件

先来看简单依赖(存在b依赖a,但不存在c依赖b)

在选择时,要么只选a,要么选a和依赖a的部分/全部

解法,对每个选的集合分组,组内冲突(只能选一个),重新构造01背包的数据

对于小依赖,直接枚举选法
例题

https://www.luogu.com.cn/problem/P1064
题目数据的一个物品最多只有2个被依赖物品,直接暴力套分组背包

标签:背包,要么,依赖,分组,物品,DP
From: https://www.cnblogs.com/uanQ/p/18279960

相关文章

  • 如何更改Wordpress语言为中文
    在使用WordPress的时候,一般安装默认语言是英文,可以在后台设置里面直接修改站点语言为简体中文,当后台没有语言选项框的这一栏,如下图所示,该怎么办呢? 这个时候我们可以找到文件wp-config.php文件,添加一行代码  define('WPLANG','zh_CN');  保存后,然后我们回到后台到设置......
  • QOJ2376 Game on a Tree (树形 dp)
    QOJ2376GameonaTree树形dp因为题目限制对于两个人等价,所以朴素的,考虑将\(u\)与祖先和后代连边,构成一个新的无向图。那么题目就变成:在无向图中选一点,每一次操作就是走一步到新的点,谁先不能走,那么另一个人获胜。先说结论:当无向图有完美匹配时,后手胜,反之先手胜。证明:若有......
  • python中对于redis依赖的一些版本记录
    一、redis不同版本对于集群和单节点的区别:1.在redis版本高于等于4.1.0支持集群方式链接(官网实例:https://redis-py.readthedocs.io/en/stable/clustering.html)推荐只使用redis官方依赖该与4.1.0的稳定版本进行支持 2.如果使用redis-py-cluster,进行对redis集群的连接,安装依赖时......
  • 解决TensorFlow中的FailedPreconditionError:未初始化的变量
    解决TensorFlow中的FailedPreconditionError:未初始化的变量......
  • 【面试题】网络UDP协议(第五篇)
    1.UDP如何实现可靠?UDP协议是面向无连接的、不可靠的传输层协议,可以通过在应用层添加一些机制来实现UDP的可靠传输。序列号和确认应答机制:为每个发送的数据包分配一个唯一的序列号,并且要求接收方发送确认应答来确认已经收到数据包。重传机制:在数据发出后,如果超过某个时间没......
  • WordPress 5.5+ 如何自定义XML 站点地图功能
    关键要点在WordPress5.5中,WordPress将导出一个站点地图索引文件/wp-sitemap.xml。这是主要的XML文件,其中包含WordPress网站公开的所有站点地图页面的列表。该站点地图索引最多可容纳50000个站点地图,单个站点地图最多可容纳2000个条目(可过滤)。默认情况下,将为所有公开和可公开查......
  • 通过依赖倒置,将子类数据传递给父类
    1、不管是父类调用子类的方法,还是获取子类的属性,道理都是一样的,依赖倒置只是其中一个方法publicclassChild:Parent{ publicstringDefault{get;set;} publicChild() { Default="默认值"; }}我现在父类需要拿到子类的Default1、增加一个接口IChild,将接口当做参数......
  • 玄机——第四章 windows实战-wordpress wp
    文章目录一、前言二、概览简介三、参考文章四、步骤(解析)准备阶段1.01.1请提交攻击者攻击成功的第一时间,格式:flag{YY:MM:DDhh:mm:ss}1.2请提交攻击者的浏览器版本flag{Firgfox/2200}1.3请提交攻击者目录扫描所使用的工具名称1.4找到攻击者写入的恶意后门文件,提交文......
  • Python离线下载并安装包及其依赖
    1,安装pipdeptree:PSD:\test>pipinstallpipdeptree2,假如想在内网安装flask,先在外网下载安装:PSD:\test>pipinstallflask3,使用pipdeptree查看并生成requirements.txtPSD:\test>pipdeptree-f-pflaskFlask==1.1.2click==7.1.2itsdangerous==1.1.0Jinja2==2.11.2......
  • Android Gradle 开发与应用 (三): 依赖管理与版本控制
    目录1.依赖管理的重要性1.1依赖的类型1.2Gradle中的依赖声明2.版本控制的策略2.1固定版本与动态版本2.2版本冲突的解决3.Gradle插件的使用3.1常用的Gradle插件3.2自定义插件4.多模块项目中的依赖管理4.1模块间依赖4.2公共依赖5.依赖版本管理的最......