算法【有依赖的背包】
有依赖的背包是指多个物品变成一个复合物品(互斥),每件复合物品不要和怎么要多种可能性展开。时间复杂度O(物品个数 * 背包容量),额外空间复杂度O(背包容量)。
下面通过题目加深理解。
题目一
测试链接:[NOIP2006 提高组] 金明的预算方案 - 洛谷
分析:对于这道题,可以参考01背包是对每个物品进行可能性的展开,有依赖的背包是对主件进行可能性的展开,所以可能性就比01背包的展开多。对于一个没有附件的主件可能性的展开,就是01背包的展开,即选或不选主件。对于有一个附件的主件可能性的展开,就有三种,选主件、不选主件、主件和附件一起选。对于有两个附件的主件可能性的展开,就有五种,选主件、不选主件、主件和第一个附件一起选、主件和第二个附件一起选、主件和两个附件一起选。对于输入,代码中采用了几个数组结构存储信息,cost数组存储花费代价,value数组存储收益,king数组存储是否是主件,fans数组存储主件有多少个附件,follows数组存储每个主件拥有的附件。下面代码采用计划搜索,并没有去做空间压缩,代码如下。
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int cost[61];
int value[61];
bool king[61];
int fans[61] = {0};
vector<vector<int>> follows;
int dp[61][32001];
int f(int index, int money){if(index == m+1){return 0;}if(dp[index][money] != -1){return dp[index][money];}if(!king[index]){return f(index+1, money);}int ans = f(index+1, money);if(money - cost[index] >= 0){ans = ans > f(index+1, money-cost[index]) + value[index] ?ans : f(index+1, money-cost[index]) + value[index];}if(fans[index] >= 1 && money - cost[index] - cost[follows[index][0]] >= 0){ans = ans > f(index+1, money-cost[index]-cost[follows[index][0]]) + value[index] + value[follows[index][0]] ?ans : f(index+1, money-cost[index]-cost[follows[index][0]]) + value[index] + value[follows[index][0]];}if(fans[index] == 2){if(money - cost[index] - cost[follows[index][1]] >= 0){ans = ans > f(index+1, money-cost[index]-cost[follows[index][1]]) + value[index] + value[follows[index][1]] ?ans : f(index+1, money-cost[index]-cost[follows[index][1]]) + value[index] + value[follows[index][1]];}if(money - cost[index] - cost[follows[index][0]] - cost[follows[index][1]] >= 0){ans = ans > f(index+1, money-cost[index]-cost[follows[index][0]]-cost[follows[index][1]]) + value[index] + value[follows[index][0]] + value[follows[index][1]] ?ans : f(index+1, money-cost[index]-cost[follows[index][0]]-cost[follows[index][1]]) + value[index] + value[follows[index][0]] + value[follows[index][1]];}}dp[index][money] = ans;return ans;
}
int main(void){int v, p, q;scanf("%d%d", &n, &m);vector<int> temp;for(int i = 0;i <= m;++i){follows.push_back(temp);}for(int i = 1;i <= m;++i){scanf("%d%d%d", &v, &p, &q);cost[i] = v;value[i] = v * p;if(q != 0){king[i] = false;fans[q]++;follows[q].push_back(i);}else{king[i] = true;}}for(int i = 1;i < 61;++i){for(int j = 1;j < 32001;++j){dp[i][j] = -1;}}printf("%d", f(1, n));return 0;
}
相关文章:
算法【有依赖的背包】
有依赖的背包是指多个物品变成一个复合物品(互斥),每件复合物品不要和怎么要多种可能性展开。时间复杂度O(物品个数 * 背包容量),额外空间复杂度O(背包容量)。 下面通过题目加深理解。 题目一 测试链接:[NOIP2006 提…...

A7. Jenkins Pipeline自动化构建过程,可灵活配置多项目、多模块服务实战
服务容器化构建的环境配置构建前需要解决什么下面我们带着问题分析构建的过程:1. 如何解决jenkins执行环境与shell脚本执行环境不一致问题?2. 构建之前动态修改项目的环境变量3. 在通过容器打包时避免不了会产生比较多的不可用的镜像资源,这些资源要是不及时删除掉时会导致服…...

飞牛NAS新增虚拟机功能,如果使用虚拟机网卡直通安装ikuai软路由(如何解决OVS网桥绑定失败以及打开ovs后无法访问飞牛nas等问题)
文章目录 📖 介绍 📖🏡 演示环境 🏡📒 飞牛NAS虚拟机安装爱快教程 📒🛠️ 前期准备🌐 网络要求💾 下载爱快镜像🚀 开始安装💻 开启IOMMU直通🌐 配置网络🚨 解决OVS网桥绑定失败以及打开ovs后无法访问飞牛nas等问题➕ 创建虚拟机🎯 安装ikuai💻 进…...
蓝桥杯例题四
每个人都有无限潜能,只要你敢于去追求,你就能超越自己,实现梦想。人生的道路上会有困难和挑战,但这些都是成长的机会。不要被过去的失败所束缚,要相信自己的能力,坚持不懈地努力奋斗。成功需要付出汗水和努…...

八股——Java基础(四)
目录 一、泛型 1. Java中的泛型是什么 ? 2. 使用泛型的好处是什么? 3. Java泛型的原理是什么 ? 什么是类型擦除 ? 4.什么是泛型中的限定通配符和非限定通配符 ? 5. List和List 之间有什么区别 ? 6. 可以把List传递给一个接受List参数的方法吗? 7. Arra…...

CVE-2023-38831 漏洞复现:win10 压缩包挂马攻击剖析
目录 前言 漏洞介绍 漏洞原理 产生条件 影响范围 防御措施 复现步骤 环境准备 具体操作 前言 在网络安全这片没有硝烟的战场上,新型漏洞如同隐匿的暗箭,时刻威胁着我们的数字生活。其中,CVE - 2023 - 38831 这个关联 Win10 压缩包挂…...

【自然语言处理(NLP)】深度循环神经网络(Deep Recurrent Neural Network,DRNN)原理和实现
文章目录 介绍深度循环神经网络(DRNN)原理和实现结构特点工作原理符号含义公式含义 应用领域优势与挑战DRNN 代码实现 个人主页:道友老李 欢迎加入社区:道友老李的学习社区 介绍 **自然语言处理(Natural Language Pr…...
Linux 命令之技巧(Tips for Linux Commands)
Linux 命令之技巧 简介 Linux 是一种免费使用和自由传播的类Unix操作系统,其内核由林纳斯本纳第克特托瓦兹(Linus Benedict Torvalds)于1991年10月5日首次发布。Linux继承了Unix以网络为核心的设计思想,是一个性能稳定的多用户…...

【文星索引】搜索引擎项目测试报告
目录 一、项目背景二、 项目功能2.1 数据收集与索引2.2 API搜索功能2.3 用户体验与界面设计2.4 性能优化与维护 三、测试报告3.1 功能测试3.2 界面测试3.3 性能测试3.4 兼容性测试3.5 自动化测试 四、测试总结4.1 功能测试方面4.2 性能测试方面4.3 用户界面测试方面 一、项目背…...

低代码系统-产品架构案例介绍、轻流(九)
轻流低代码产品定位为零代码产品,试图通过搭建来降低企业成本,提升业务上线效率。 依旧是从下至上,从左至右的顺序 名词概述运维层底层系统运维层,例如上线、部署等基础服务体系内置的系统能力,发消息、组织和权限是必…...

二叉树(补充)
二叉树 1.二叉树的基本特性2.堆2.1.堆的基本概念2.2.堆的实现2.2.1.基本结构2.2.2.堆的初始化 2.2.3.堆的销毁2.2.4.堆的插入2.2.5.取出堆顶的数据2.2.6.堆的删除2.2.7.堆的判空2.2.8.堆的数据个数2.2.9.交换2.2.10.打印堆数据2.2.11.堆的创建2.2.12.堆排序 1.二叉树的基本特性…...
(DM)达梦数据库基本操作(持续更新)
1、连接达梦数据库 ./disql 用户明/"密码"IP端口或者域名 2、进入某个模式(数据库,因达梦数据库没有库的概念,只有模式,可以将模式等同于库) set schema 库名; 3、查表结构; SELECT COLUMN_NAM…...
CRM 微服务
文章目录 项目地址一、项目地址 教程作者:教程地址:代码仓库地址:所用到的框架和插件:dbt airflow一、 用户与认证服务 主要功能: 用户注册、登录、注销。 认证(OAuth、JWT 等)。 权限和角色管理(RBAC/ABAC)。 单点登录(SSO)。 技术亮点: 集成第三方身份认证(如 …...

AI软件外包需要注意什么 外包开发AI软件的关键因素是什么 如何选择AI外包开发语言
1. 定义目标与需求 首先,要明确你希望AI智能体做什么。是自动化任务、数据分析、自然语言处理,还是其他功能?明确目标可以帮助你选择合适的技术和方法。 2. 选择开发平台与工具 开发AI智能体的软件时,你需要选择适合的编程语言、…...

DBSyncer开源数据同步中间件
一、简介 DBSyncer(英[dbsɪŋkɜː(r)],美[dbsɪŋkɜː(r) 简称dbs)是一款开源的数据同步中间件,提供MySQL、Oracle、SqlServer、PostgreSQL、Elasticsearch(ES)、Kafka、File、SQL等同步场景。支持上传插件自定义同步转换业务,提供监控全量…...

< OS 有关 > 阿里云 几个小时前 使用密钥替换 SSH 密码认证后, 发现主机正在被“攻击” 分析与应对
信息来源: 文件:/var/log/auth.log 因为在 sshd_config 配置文件中,已经定义 LogLevel INFO 部分内容: 2025-01-27T18:18:55.68272708:00 jpn sshd[15891]: Received disconnect from 45.194.37.171 port 58954:11: Bye Bye […...

react-bn-面试
1.主要内容 工作台待办 实现思路: 1,待办list由后端返回,固定需要的字段有id(查详细)、type(本条待办的类型),还可能需要时间,状态等 2,一个集中处理待办中转路由页,所有待办都跳转到这个页面…...

1. Java-MarkDown文件创建-工具类
Java-MarkDown文件创建-工具类 1. 思路 根据markdown语法,拼装markdown文本内容 2. 工具类 import java.util.Arrays; import java.util.List;/*** Markdown生成工具类* Author: 20004855* Date: 2021/1/15 16:00*/ public class MarkdownGenerator {private Str…...

全连接神经网络(前馈神经网络)
一、全连接神经网络介绍 在多层神经网络中, 第 N 层的每个神经元都分别与第 N-1 层的神经元相互连接。 1、神经元 这个神经元接收的输入信号为向量 , 向量为输入向量的组合权重, 为偏置项, 是一个标量。 神经元的作用是对输入向…...
【llm对话系统】什么是 LLM?大语言模型新手入门指南
什么是 LLM?大语言模型新手入门指南 大家好!欢迎来到 LLM 的奇妙世界!如果你对人工智能 (AI) 的最新进展,特别是那些能像人类一样阅读、写作甚至进行对话的 AI 感兴趣,那么你来对地方了。这篇文章将带你认识 LLM 的基…...

网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...

el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...

C# 表达式和运算符(求值顺序)
求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如,已知表达式3*52,依照子表达式的求值顺序,有两种可能的结果,如图9-3所示。 如果乘法先执行,结果是17。如果5…...

群晖NAS如何在虚拟机创建飞牛NAS
套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...