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

九种背包问题(C++)

0-1背包,背包大小target,占用容积vec[i][0],可以带来的利益是vec[i][1]
一件物品只能取一次,先遍历物品然后遍历背包更新不同容积下最大的利益

int func(vector<vector<int>>&vec,int target){vector<int>dp(target+1,0);for(int i=0;i<vec.size();i++){for(int w=target;w>=vec[i][0];w--){dp[w]=max(dp[w-vec[i][0]]+vec[i][1],dp[w]);}}return dp[w];
}

完全背包,与0-1背包相比差别在于物品可以多次选择了
思路和0-1背包差不多,只不过遍历背包容积时从低到高,每次更新时之前都是包含当前物品最优

int func1(vector<vector<int>>&vec,int target){vector<int>dp(target+1,0);for(int i=0;i<vec.size();i++){for(int w=vec[i][0];w<=target;w++){dp[w]=max(dp[w-vec[i][0]]+vec[i][1],dp[w]);}}return dp[w];
}

多重背包,每种物品有vec[i][j][2]个
思路1,二进制商品拆分(比如:111可以组合成1-6任意数字),转化为0-1背包问题

int func2(vector<vector<int>>&vec,int target){int n=vec.size();vector<pair<int,int>>goods;for(auto&i:vec){for(int j=1;j<=i[2];i*=2){i[2]=i[2]-j;goods.push_back({i[0]*j,i[1]*j});}goods.push_back({i[2]*i[0],i[2]*i[1]});}vector<int>dp(target+1,0);for(int i=0;i<goods.size();i++){for(int j=target;j>=goods[i].first;j--){dp[j]=max(dp[j],dp[j-goods[i].first]+goods[i].second);}}return dp[target];
}

思路2 添加物品数量层遍历

int func3(vector<vector<int>>&vec,int target){vector<int>dp(target+1,0);for(int i=0;i<vec.size();i++){for(int j=target;j>=vec[i][0];j--){for(int k=1;k*vec[i][0]<j&&k<=vec[i][2];k++){dp[j]=max(dp[j],dp[j-k*vec[i][0]]+k*vec[i][1]);}}}return dp[target];
}

混合背包,背包中的物品可以有无限个或者有限个
vec[i][0]重量,vec[i][1]价值,vec[i][2]数量

int func4(vector<vector<int>>&vec,int target){vector<int>dp(target+1,0);for(int i=0;i<vec.size();i++){if(vec[i][2]==0){for(int j=vec[i][0];j<=target;j++){dp[j]=max(dp[j],dp[j-vec[i][0]]+vec[i][1]);}}else {for(int j=target;j>=vec[i][0];j--){for(int k=1;k*vec[i][0]<j&&k<=vec[i][2];k++){dp[j]=max(dp[j],dp[j-k*vec[i][0]]+k*vec[i][1]);}}}}return dp[target];
}

分组背包
商品分组,每组最多只能选一个,vec[i][k][0]重量,vec[i][k][1]价值

int func5(vector<vector<vector<int>>>&vec,int target){vector<int>dp(target+1,0);for(int i=0;i<vec.size();i++){for(int j=target;j>=0;j--){//遍历背包容积for(int k=0;k<vec[i].size();k++){//遍历商品组内商品if(j>=vec[i][k][0]) dp[j]=max(dp[j],dp[j-vec[i][k][0]]+vec[i][k][1]);}}}return dp[target];
}

二维背包
约束条件增加,vec[i][0]价值,vec[i][1]是第一个约束条件,vec[i][2]是第二个约束条件

int func6(vector<vector<int>>&vec,int target1,int target2){vector<vector<int>>dp(target1+1,vector<int>(target2+1,0));for(int i=0;i<vec.size();i++){for(int j=target1;j>=vec[i][1];j--){for(int k=target2;k>=vec[i][2];k--){dp[j][k]=max(dp[j][k],dp[j-vec[i][1]][k-vec[i][2]]+vec[i][0]);}}}return dp[target1][target2];
}

树状背包
买一件物品前必须买另一件
map键值是编号,first负重,second价值,买d[i][0]前必须买d[i][1],d[i][1]=0时表示没有依赖
思路,回溯思想自底向上遍历,每一层子树作为一个临时的商品组,根节点必须买,根节点买不了时更新为0
原理是把一棵树分为整合为前缀和组,实现起来保证每种情况更新到且在回溯前更新完即可
注意更新的数据所在的层级

int func7(unordered_map<int,pair<int,int>>&map,vector<vector<int>>&d,int target){int n=map.size();vector<vector<int>>tree(n+1);vector<vector<int>>dp(n+1,vector<int>(target+1));for(auto i:d){tree[i[1]].push_back(i[0]);}function<void(int)>dfs=[&](int root){for(int i=0;i<tree[root].size();i++){//遍历商品组int son=tree[root][i];dfs(son);for(int j=target-map[root].first;j>=map[son].first;j--){//商品组内不应该包含根节点,所以需要保留for(int k=0;k<=j;k++){//对商品的抽象,直接抽象为了对应的大小,不存在时为0dp[root][j]=max(dp[root][j],dp[root][j-k]+dp[son][k]);}}}for(int j=target;j>=map[root].first;j--)//根节点必须买 dp[root][j]=dp[root][j-map[root].first]+map[root].second;for(int j=0;j<map[root].first;j++) //根节点买不了的话gdp[root][j]=0;};dfs(0);return dp[0][target];
}

小数/分数背包,贪心
物品可以选择部分
vec[i][0]重量,vec[i][1]价值

int func8(vector<int>&vec,int target){sort(vec.begin(),vec.end(),[](vector<int>&v1,vector<int>&v2){return v1[1]*1.0/v1[0]>v2[1]*1.0/v2[0];});int value=0;for(int i=0;i<vec.size()&&target;i++){if(target>vec[i][0]){target-=vec[i][0];value+=vec[i][1];}else {value+=target*vec[i][1]*1.0/vec[i][0];target=0;}}return value;
}

泛化背包问题
没有固定代价和价值

int value(int index){...}
int weight(int index){...}
int func9(int size,int target){vector<int>dp(target+1,0);for(int i=0;i<size;i++){for(int w=target;w>=weight(i);w--){dp[w]=max(dp[w],dp[w-weight(i)]+value(i));}}return dp[target];
}

相关文章:

九种背包问题(C++)

0-1背包&#xff0c;背包大小target&#xff0c;占用容积vec[i][0]&#xff0c;可以带来的利益是vec[i][1] 一件物品只能取一次,先遍历物品然后遍历背包更新不同容积下最大的利益 int func(vector<vector<int>>&vec,int target){vector<int>dp(target1,…...

008:安装Docker

安装Docker 如果不太熟悉Linux命令&#xff0c;不想学习Linux命令&#xff0c;可以直接看文末NAS面板章节&#xff0c;通过面板&#xff0c;像使用Window一样操作NAS。 一、安装 Docker 1.安装 Docker wget -qO- https://get.docker.com/ | sh2.启动 Docker 服务 sudo sys…...

STM32第九节(中级篇):RCC(第一节)——时钟树讲解

目录 前言 STM32第九节&#xff08;中级篇&#xff09;&#xff1a;RCC——时钟树讲解 时钟树主系统时钟讲解 HSE时钟 HSI时钟 锁相环时钟 系统时钟 SW位控制 HCLK时钟 PCLKI时钟 PCLK2时钟 RTC时钟 MCO时钟输出 6.2.7时钟安全系统(CSS&#xff09; 小结 前言 从…...

Web核心,HTTP,tomcat,Servlet

1&#xff0c;JavaWeb技术栈 B/S架构:Browser/Server&#xff0c;浏览器/服务器架构模式&#xff0c;它的特点是&#xff0c;客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务器端。浏览器只需要请求服务器&#xff0c;获取Web资源&#xff0c;服务器把Web资源…...

空间(Space)概念:元素、集合、空间和数学对象

摘要&#xff1a; 在数学中&#xff0c;一个空间&#xff08;Space&#xff09;是一种特殊类型的数学对象。它通常是一个集合&#xff0c;但不仅仅是一个普通的集合&#xff0c;而是具有某种附加的结构和定义在其上的运算规则。这些额外的结构使得空间能够反映现实世界中的几何…...

【Datawhale组队学习:Sora原理与技术实战】训练一个 sora 模型的准备工作,video caption 和算力评估

训练 Sora 模型 在 Sora 的技术报告中&#xff0c;Sora 使用视频压缩网络将各种大小的视频压缩为潜在空间中的时空 patches sequence&#xff0c;然后使用 Diffusion Transformer 进行去噪&#xff0c;最后解码生成视频。 Open-Sora 在下图中总结了 Sora 可能使用的训练流程。…...

Kafka-生产者报错javax.management.InstanceAlreadyExistsException

生产者发送消息到 kafka 中,然后控制台报错 然后根据日志查看 kafka 的源码发现了问题原因 说的是MBean已经注册了,然后报异常了,这样就会导致生产者的kafka注册失败, 原因是项目上生产者没有配置clientId,默认都是空导致的, 多个生产者(项目)注册到kafka集群中的 id 都相同。 …...

Java常见问题:编辑tomcat运行环境、部署若伊系统

文章目录 引言I Eclipse1.1 编辑tomcat运行环境II JDK2.1 驱动程序无法通过使用安全套接字层(SSL)加密与 SQL Server 建立安全连接2.2 restriction on required library2.3 The type javax.servlet.http.HttpServletRequest cannot be resolved.的解决方法III npm3.1 npm报错:…...

阿里云免费证书改为3个月,应对方法很简单

情商高点的说法是 Google 积极推进90天免费证书&#xff0c;各服务商积极响应。 情商低点的话&#xff0c;就是钱的问题。 现在基本各大服务商都在2024年停止签发1年期的免费SSL证书产品&#xff0c;有效期都缩短至3个月。 目前腾讯云倒还是一年期。 如果是一年期的话&#x…...

安装Pytorch——CPU版本

安装Pytorch——CPU版本 1. 打开pytorch官网2. 选择pip安装pytorch-cpu3.复制安装命令4. 在cmd命令窗口&#xff0c;进入你的虚拟环境4.1 创建虚拟环境4.2 进行安装 5. 安装成功6. 进行测试——如下面步骤&#xff0c;如图6.1 输入 python6.2 输入 import torch6.2 输入 print …...

MySQL中出现‘max_allowed_packet‘ variable.如何解决

默认情况下&#xff0c;MySQL的max_allowed_packet参数可能设置得相对较小&#xff0c;这对于大多数常规操作来说足够了。但是&#xff0c;当你尝试执行包含大量数据的操作&#xff08;如大批量插入或大型查询&#xff09;时&#xff0c;可能会超过这个限制&#xff0c;从而导致…...

PHP 生成图片

1.先确认是否有GD库 echo phpinfo(); // 创建一个真彩色图像 $image imagecreatetruecolor(120, 50);// 分配颜色 $bgColor imagecolorallocate($image, 255, 255, 255); // 白色背景 $textColor imagecolorallocate($image, 230, 230, 230); // 黑色文字// 填充背景 image…...

【Spring Boot 3】【JSON】读取JSON文件

【Spring Boot 3】【JSON】读取JSON文件 背景介绍开发环境开发步骤及源码工程目录结构总结背景 软件开发是一门实践性科学,对大多数人来说,学习一种新技术不是一开始就去深究其原理,而是先从做出一个可工作的DEMO入手。但在我个人学习和工作经历中,每次学习新技术总是要花…...

网络学习:邻居发现协议NDP

目录 前言&#xff1a; 一、报文内容 二、地址解析----NS/NA 目标的被请求组播IP地址 邻居不可达性检测&#xff1a; 重复地址检测 路由器发现 地址自动配置 默认路由器优先级和路由信息发现 重定向 前言&#xff1a; 邻居发现协议NDP&#xff08;Neighbor Discovery…...

Spring事务传播行为总结

事务传播行为介绍 Spring中的7个事务传播行为: ​ 事务行为说明特点PROPAGATION_REQUIRED支持当前事务&#xff0c;假设当前没有事务。就新建一个事务父事务与子事务要么都成功&#xff0c;要么都失败PROPAGATION_SUPPORTS支持当前事务&#xff0c;假设当前没有事务&#xff0…...

AWTK slider_circle 控件发布

slider_circle 控件。 主要特色&#xff1a; 支持正向和反向支持设置滑块的半径支持背景线宽和颜色支持前景线宽和颜色支持设置是否显示值的文本支持设置起始角度和结束角度支持设置格式化值的格式字符串支持使用图片填充背景和前景 界面效果&#xff1a; 注意&#xff1a; …...

BitMap 和 HyperLogLog

目录 BitMap 常用命令 应用场景 日活统计 用户签到 HyperLogLog 什么是基数? 常用命令 应用场景 BitMap 问: "有10亿个不重复的无序的正数&#xff0c;如果快速排序&#xff1f;" 这看上去很简单&#xff0c;就是一个排序而已&#xff0c;但是大部分排序算…...

德人合科技 | 公司办公终端、电脑文件资料 \ 数据透明加密防泄密管理软件系统

天锐绿盾是一款全面的企业级数据安全解决方案&#xff0c;它专注于为企业办公终端、电脑文件资料提供数据透明加密防泄密管理。 首页 德人合科技——www.drhchina.com 这款软件系统的主要功能特点包括&#xff1a; 1. **透明加密技术**&#xff1a; 天锐绿盾采用了透明加密技…...

0基础 三个月掌握C语言(11)

字符函数和字符串函数 为了方便操作字符和字符串 C语言标准库中提供了一系列库函数 接下来我们学习一下这些函数 字符分类函数 C语言提供了一系列用于字符分类的函数&#xff0c;这些函数定义在ctype.h头文件中。这些函数通常用于检查字符是否属于特定的类别&#xff0c;例如…...

【Linux】基础 IO(文件描述符)-- 详解

一、前言 1、文件的宏观理解 文件在哪呢&#xff1f; 从广义上理解&#xff0c;键盘、显示器、网卡、声卡、显卡、磁盘等几乎所有的外设都可以称之为文件&#xff0c;因为 “Linux 下&#xff0c;一切皆文件”。 从狭义上的理解&#xff0c;文件在磁盘&#xff08;硬件&#…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...