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

算法【有依赖的背包】

有依赖的背包是指多个物品变成一个复合物品(互斥),每件复合物品不要和怎么要多种可能性展开。时间复杂度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;
}

相关文章:

算法【有依赖的背包】

有依赖的背包是指多个物品变成一个复合物品&#xff08;互斥&#xff09;&#xff0c;每件复合物品不要和怎么要多种可能性展开。时间复杂度O(物品个数 * 背包容量)&#xff0c;额外空间复杂度O(背包容量)。 下面通过题目加深理解。 题目一 测试链接&#xff1a;[NOIP2006 提…...

A7. Jenkins Pipeline自动化构建过程,可灵活配置多项目、多模块服务实战

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

飞牛NAS新增虚拟机功能,如果使用虚拟机网卡直通安装ikuai软路由(如何解决OVS网桥绑定失败以及打开ovs后无法访问飞牛nas等问题)

文章目录 📖 介绍 📖🏡 演示环境 🏡📒 飞牛NAS虚拟机安装爱快教程 📒🛠️ 前期准备🌐 网络要求💾 下载爱快镜像🚀 开始安装💻 开启IOMMU直通🌐 配置网络🚨 解决OVS网桥绑定失败以及打开ovs后无法访问飞牛nas等问题➕ 创建虚拟机🎯 安装ikuai💻 进…...

蓝桥杯例题四

每个人都有无限潜能&#xff0c;只要你敢于去追求&#xff0c;你就能超越自己&#xff0c;实现梦想。人生的道路上会有困难和挑战&#xff0c;但这些都是成长的机会。不要被过去的失败所束缚&#xff0c;要相信自己的能力&#xff0c;坚持不懈地努力奋斗。成功需要付出汗水和努…...

八股——Java基础(四)

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

CVE-2023-38831 漏洞复现:win10 压缩包挂马攻击剖析

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

【自然语言处理(NLP)】深度循环神经网络(Deep Recurrent Neural Network,DRNN)原理和实现

文章目录 介绍深度循环神经网络&#xff08;DRNN&#xff09;原理和实现结构特点工作原理符号含义公式含义 应用领域优势与挑战DRNN 代码实现 个人主页&#xff1a;道友老李 欢迎加入社区&#xff1a;道友老李的学习社区 介绍 **自然语言处理&#xff08;Natural Language Pr…...

Linux 命令之技巧(Tips for Linux Commands)

Linux 命令之技巧 简介 Linux ‌是一种免费使用和自由传播的类Unix操作系统&#xff0c;其内核由林纳斯本纳第克特托瓦兹&#xff08;Linus Benedict Torvalds&#xff09;于1991年10月5日首次发布。Linux继承了Unix以网络为核心的设计思想&#xff0c;是一个性能稳定的多用户…...

【文星索引】搜索引擎项目测试报告

目录 一、项目背景二、 项目功能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 用户界面测试方面 一、项目背…...

低代码系统-产品架构案例介绍、轻流(九)

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

二叉树(补充)

二叉树 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、进入某个模式&#xff08;数据库,因达梦数据库没有库的概念&#xff0c;只有模式&#xff0c;可以将模式等同于库&#xff09; set schema 库名&#xff1b; 3、查表结构&#xff1b; SELECT COLUMN_NAM…...

CRM 微服务

文章目录 项目地址一、项目地址 教程作者:教程地址:代码仓库地址:所用到的框架和插件:dbt airflow一、 用户与认证服务 主要功能: 用户注册、登录、注销。 认证(OAuth、JWT 等)。 权限和角色管理(RBAC/ABAC)。 单点登录(SSO)。 技术亮点: 集成第三方身份认证(如 …...

AI软件外包需要注意什么 外包开发AI软件的关键因素是什么 如何选择AI外包开发语言

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

DBSyncer开源数据同步中间件

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

< OS 有关 > 阿里云 几个小时前 使用密钥替换 SSH 密码认证后, 发现主机正在被“攻击” 分析与应对

信息来源&#xff1a; 文件&#xff1a;/var/log/auth.log 因为在 sshd_config 配置文件中&#xff0c;已经定义 LogLevel INFO 部分内容&#xff1a; 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.主要内容 工作台待办 实现思路&#xff1a; 1&#xff0c;待办list由后端返回&#xff0c;固定需要的字段有id(查详细)、type(本条待办的类型)&#xff0c;还可能需要时间&#xff0c;状态等 2&#xff0c;一个集中处理待办中转路由页&#xff0c;所有待办都跳转到这个页面…...

1. Java-MarkDown文件创建-工具类

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

全连接神经网络(前馈神经网络)

一、全连接神经网络介绍 在多层神经网络中&#xff0c; 第 N 层的每个神经元都分别与第 N-1 层的神经元相互连接。 1、神经元 这个神经元接收的输入信号为向量 &#xff0c; 向量为输入向量的组合权重&#xff0c; 为偏置项&#xff0c; 是一个标量。 神经元的作用是对输入向…...

【llm对话系统】什么是 LLM?大语言模型新手入门指南

什么是 LLM&#xff1f;大语言模型新手入门指南 大家好&#xff01;欢迎来到 LLM 的奇妙世界&#xff01;如果你对人工智能 (AI) 的最新进展&#xff0c;特别是那些能像人类一样阅读、写作甚至进行对话的 AI 感兴趣&#xff0c;那么你来对地方了。这篇文章将带你认识 LLM 的基…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

linux之kylin系统nginx的安装

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

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...