【动态规划】详解混合背包问题
目录
- 1. 前置文章
- 2. 题目
- 3. 小结
1. 前置文章
本文前置文章:
- 【动态规划】详解 0-1背包问题
- 【动态规划】详解完全背包问题
- 【动态规划】详解分组背包问题
- 【动态规划】详解多重背包问题
下面是三种背包模式的区别:
0 - 1 背包
是说:有 n 个物品和一个重量为 t 的背包,这 n 个物品中第 i 个物品的重量为 w[i],价值为 v[i],那么这个背包能装下的物品最大价值是多少,注意一个物品只能选一次。完全背包
是说:有 n 个物品和一个重量为 t 的背包,这 n 个物品中第 i 个物品的重量为 w[i],价值为 v[i],那么这个背包能装下的物品最大价值是多少,注意一个物品可以选无数次。分组背包
是说:有 n 组物品和一个重量为 t 的背包,每个物品都有自己的体积,价值和组号,代表这个物品属于哪一组,要求在不超过背包容量的前提下,从每组物品中最多选择一个物品,使得背包中物品的总价值最大。多重背包
是说:有 n 个物品和一个重量为 t 的背包,这 n 个物品中第 i 个物品的重量为 w[i],价值为 v[i],数量为 c[i],那么这个背包能装下的物品最大价值是多少,注意一个物品可以选择的次数限制为 c[i]。
2. 题目
因为混合背包其实就是一道题中包括了 0-1 背包,完全背包,多重背包,这里直接看一道题:
- coins
这道题目意思是:题目输入 n, m,并且给出了这 n 个硬币的价值和个数,问通过这些硬币能够构成 [1,m] 这个价值范围里面的哪些价值。
举个例子:假设 m = 5,现在给了两种硬币,硬币1 价值 1 个数2,硬币2 价值 4 个数 1,问 [1,5] 这个范围里面有多少个价值能够被这些硬币凑出来。
- 首先 1 肯定是可以的,因为价值为1 的硬币有 2 个
- 同理 2 也是可以的
- 3 不可以,因为硬币1 和 硬币2 凑不出来价值 3
- 4 可以,只需要一个硬币2 就行了
- 5 也可以,只需要一个硬币2 和一个硬币 1
所以最终答案就是 5。
这道题就是混合背包的题目了,同样外层遍历物品,内层遍历背包。
- 当
物品个数为 1
,就是 0-1 背包了。 - 当
物品个数 * 价值 > m
,就说明此时这些物品总价值已经超过了上限 m,是完全背包模板。 - 当
物品个数 * 价值 <= m
,就按多重背包来算。
import java.util.Arrays;
import java.util.Scanner;public class Main {public static int MAXN = 101;public static int MAXM = 100001;public static int[] v = new int[MAXN];public static int[] c = new int[MAXN];public static boolean[] dp = new boolean[MAXM];public static int n, m = 0;public static void main(String[] args) {Scanner scan = new Scanner(System.in);while (scan.hasNext()) {n = scan.nextInt();m = scan.nextInt();if (n != 0 || m != 0) {for (int i = 1; i <= n; i++) {v[i] = scan.nextInt();}for (int i = 1; i <= n; i++) {c[i] = scan.nextInt();}}System.out.println(compute());}}/*** 有 n 个硬币, 给了出 n 个硬币的价值和个数, 价值相当于重量了* 再给一个数字 m,求 [1, m] 这个区间内有多少是能够被这些硬币拼凑出来** @return*/public static int compute() {// 每次求之前都初始化一下Arrays.fill(dp, false);dp[0] = true;for (int i = 1; i <= n; i++) {if (c[i] == 1) {// 物品只有一个,01 背包for (int j = m; j >= v[i]; j--) {if (dp[j - v[i]]) {dp[j] = true;}}} else if (v[i] * c[i] > m) {// 完全背包for (int j = v[i]; j <= m; j++) {if (dp[j - v[i]]) {dp[j] = true;}}} else {// 多重背包: v[i] * c[i] < m// 因为这里我们需要标记 dp 里面 1~m 哪个是 true,所以单调队列就用一个变量表示 true 的个数就行了for (int mod = 0; mod <= Math.min(m, v[i] - 1); mod++) {int trueCount = 0;int count = 1;for (int j = m - mod; j >= 0 && count <= c[i]; j -= v[i], count++) {trueCount += dp[j] ? 1 : 0;}for (int j = m - mod, last = j - c[i] * v[i]; j >= 0; j -= v[i], last -= v[i]) {if (last >= 0) {trueCount += dp[last] ? 1 : 0;}if (dp[j]) {// 如果已经是 true 了,那么相当于直接删除单调队列里面的过期元素trueCount--;} else {if(trueCount > 0){dp[j] = true;}}}}}}int ans = 0;for (int i = 1; i < dp.length; i++) {if (dp[i]) {ans++;}}return ans;}}
上面计算多重背包的时候用了 trueCount
代替单调队列,因为我们不需要记录最大值,只需要记录当前 dp[j] 能不能变成 true,只要依赖的几个有一个为 true 那么 dp[j] 就能变成 true。
当然如果 dp[j] 已经是 true 了,那么 j 继续往前遍历,这种情况下 j 下标的值就过期了,所以需要 trueCount--
。
3. 小结
这道题就是混合背包,里面涉及到了 0-1 背包,完全背包,多重背包的流程,还是一样,参考视频:算法讲解075【必备】背包dp-多重背包、混合背包。
如有错误,欢迎指出!!!
相关文章:
【动态规划】详解混合背包问题
目录 1. 前置文章2. 题目3. 小结 1. 前置文章 本文前置文章: 【动态规划】详解 0-1背包问题【动态规划】详解完全背包问题【动态规划】详解分组背包问题【动态规划】详解多重背包问题 下面是三种背包模式的区别: 0 - 1 背包 是说:有 n 个…...
Nodejs 项目打包部署方式
方式一:PM2 一、准备工作 确保服务器上已安装 Node.js 环境建议使用 PM2 进行进程管理(需要额外安装) 二、部署步骤 1.首先在服务器上安装 PM2(推荐): npm install -g pm22.将项目代码上传到服务器&…...
银河麒麟操作系统的上下游版本判断
以下内容摘自《银河麒麟操作系统进阶应用》一书。 几百款Linux发行版之间并不是完全独立的,绝大多数Linux发行版可以追溯到几个关键的“祖先”发行版,其中最为人熟知的包括Debian、Fedora、Slackware和Arch Linux。这些“祖先”发行版又称“原始”发行版…...
Retrofit中scalars转换html为字符串
简介 在Retrofit中,如果你想直接获取HTML或其他文本格式的响应内容而不是将其映射到一个模型类,ScalarsConverterFactory 就派上用场了。ScalarsConverterFactory 是一个转换器工厂,它能够将响应体转换为Java基本类型如String、Integer或Byte…...
Java基础面试题学习
转换成自已的语言来回答,来源小林coding、沉默王二以及其它资源和自已改编。 1、概念 1、说一下Java的特点 我认为Java有很多特点 首先是平台无关性:Java可以实现一次编译到处运行,因为Java的编译器将源代码编译成字节码,使得该…...
# [RPA] 使用八爪鱼进行高效网页数据采集
在许多行业中,数据是核心资产。然而,虽然许多网站的文本内容可以免费访问,但手动一条一条采集,不仅耗时耗力,还容易出错。这种情况下,使用自动化工具来提高采集效率就显得尤为重要。本文将介绍 八爪鱼 这一…...
【工具变量】全国地级市地方ZF债务数据集(2014-2023年)
地方ZF债务是地方财政运作的重要组成部分,主要用于基础设施建设、公共服务及经济发展,是衡量地方财政健康状况的重要指标。近年来,我国地级市的地方ZF债务规模不断变化,涉及一般债务和专项债务等多个方面,对金融市场、…...
6.5840 Lab 3: Raft
论文很重要 raft-zh_cn/raft-zh_cn.md at master maemual/raft-zh_cn GitHub Part 3A: leader election (moderate) 十次test都过了 实现 Raft 的领导者选举和心跳机制(AppendEntries RPC,无日志条目)。第 3A 部分的目标是实现以下功能&am…...
DCDC36V同步降压 输出可调 2A电流恒压芯片SL1588H 替换LV3842
在当今电子设备飞速发展的时代,电源管理芯片的性能优劣直接关乎设备的稳定性与高效运行。对于诸多需要将 36V 电压进行同步降压、输出电压可调且稳定输出 2A 电流的应用场景,一款卓越的恒压芯片不可或缺。SL1588H 正凭借其领先的技术和出色的性能&#x…...
AH4953A双PMOS管深度解析:无线充系统的“高效开关”设计实践
AH4953 30v5A双PMOS管深度解析:无线充系统的“高效开关”设计实践 1. 产品定位与基础特性 AH4953A双通道P沟道MOSFET,专为无线充电、电源管理等高频开关场景优化。其核心优势体现在: • 高耐压低损耗:30V漏源电压(Vd…...
图数据库Neo4j和JDK安装与配置教程(超详细)
目录 前言 一、Java环境配置 (一)JDK的下载与安装 (二)JDK环境配置 (三)检测JDK17是否配置成功 二、Neo4j的安装与配置 (一)Neo4j的下载与安装 (二)N…...
现代美学工业风品牌海报徽标设计PSAI无衬线英文字体安装包 Moldin – Condensed Sans Serif Font
现代几何工业风品牌海报徽标设计无衬线英文字体安装包 Moldin — Condensed Sans Serif Font Moldin 是一个粗体浓缩的无衬线字体系列,旨在为显示和标题提供最大的影响。Moldin 有 6 种粗细可供选择,从常规到黑色,提供静态和可变格式&#x…...
Excel(函数进阶篇):FILTER函数全解读、XLOOKUP函数全解读、UNIQUE函数、数组与数组公式
目录 数组与数组函数office365中VLOOKUP函数的加强数组中的多条件判断FILTER函数详解用法概述函数语法 基础筛选多条件筛选进阶技巧结合动态数组 高级函数整合错误处理注意事项FILTER经典问题:一对多查询 XLOOKUP函数XLOOKUP基础用法XLOOKUP函数多条件匹配和双向查询…...
django入门教程之request和reponse【二】
接上节:入门【一】 再创建一个orders子应用,python manager.py startapp orders,orders目录中新建一个urls.py文件。结构如图: 通过上节课,我们知道在views.py文件中编写函数时,有一个默认入参request&…...
第十五次CCF-CSP认证(含C++源码)
第十五次CCF-CSP认证 小明上学满分思路 数据中心满分思路 小明放学满分题解 小明上学 题目链接 满分思路 其实题目看着长,但是做起来是非常好写的,其实主要原因在于,他的红绿灯的变化规律是一定的,而且小明路上的每次红绿灯情况…...
Excel处理控件Spire.XLS系列教程:C# 在 Excel 中添加或删除单元格边框
单元格边框是指在单元格或单元格区域周围添加的线条。它们可用于不同的目的,如分隔工作表中的部分、吸引读者注意重要的单元格或使工作表看起来更美观。本文将介绍如何使用 Spire.XLS for .NET 在 C# 中添加或删除 Excel 单元格边框。 安装 Spire.XLS for .NET E-…...
混合精度-基于torch内部
定义 混合精度训练是一种在深度学习模型训练过程中,同时使用不同精度数据类型(主要是单精度 FP32 和半精度 FP16)来进行计算和存储的技术。以下是具体介绍: 数据类型: 单精度(FP32)࿱…...
Ubuntu16.04网卡ens33找不到异常修复
重启网络 systemctl stop NetworkManager systemctl restart networking允许网络可用 连接网络 验证网络...
C++编译流程
编译器其实就是一个翻译器,把我们的文件内容翻译成机器能够看懂的指令,但如何合理翻译是核心。 C语言编译 需要经过以下几步: 词法分析:扫描代码,确定单词类型,比如是变量还是函数,是标识符还…...
人工智能:企业RAG方案
一、LangChain FAISS、Milvus / Weaviate介绍 在企业 RAG (Retrieval-Augmented Generation)方案中,LangChain FAISS 和 Milvus / Weaviate 都是用于向量检索(Vector Search)的核心工具。两者的核心区别在于 存储方…...
【Git流程最佳实践】 开发较大功能时应使用project branch
目录 背景和失败经验名词定义曾经使用project branch犯的错 建立project branch的必要性正确的使用project branch的方法 背景和失败经验 我们曾经使用过project branch,但是后来放弃了 名词定义 特性branch(特性分支): 在开发跨越新特性的时候会从主…...
线程的概念
目录 线程的概念 创建线程快速验证 物理内存管理 再谈页表 今天我们学习线程的概念 线程的概念 进程是一个指向起来的程序,进程内核数据结构代码和数据,线程称为指向流,执行粒度比进程要更细,是进程内部的一个执行分支&…...
firefly经典蓝牙和QProcess、QFileSystemWatcher记录
QProcess 默认不会启动一个 shell 来解析命令,而是直接调用操作系统的系统调用来启动外部程序。也就是通过fork一个子线程或者exec一个子进程来执行命令。 QProcess的参数模式 QProcess 需要明确指定命令的可执行文件路径或参数列表。 如果命令是一个可执行文件的路径…...
北斗设备启动流程与时长解析
北斗卫星导航系统作为我国自主研发的全球卫星导航系统,广泛应用于交通、通信、农业等多个领域。今天,我们就来详细探讨一下北斗设备的启动流程以及不同启动方式下的时长。 一、北斗设备的启动流程 北斗设备的启动流程可以分为以下几个关键步骤…...
PyTorch分布式训练中各节点如何通信
深度学习 文章目录 深度学习前言pytorch如何初始化分布式训练怎么知道要使用哪几台机器进行训练的如何根据标识进行初始化(init_method)如何获取进程的唯一标识rank如何实现数据如何分发 前言 同学们在处理分布式训练时经常会遇到以下几个疑问ÿ…...
又双叒叕Scrapy爬虫相关的面试题及详细解答
Scrapy是Python开发的一个快速、高层次的网络爬虫框架,专注于高效抓取网页并提取结构化数据。其核心设计基于异步处理机制,适合大规模数据采集任务。 文章目录 基础概念1. Scrapy框架的核心组件有哪些?架构与流程2. 描述Scrapy的工作流程核心组件详解3. 如何自定义Item Pipe…...
Docker与K8S是什么该怎么选?
用了很久的容器化,最近突然看到一个问题问: docker和K8S究竟有什么区别,到底该怎么选?我认真思考了一会,发现一时间还真说不明白,于是就研究了一段时间发布今天的博文! Docker vs Kubernetes&a…...
FPGA中串行执行方式之计数器控制
FPGA中串行执行方式之计数器控制 使用计数器控制的方式实现状态机是一种简单且直观的方法。它通过计数器的值来控制状态的变化,从而实现顺序逻辑。计数器的方式特别适合状态较少且状态转移是固定的场景。 基本原理 计数器控制的状态机 例程1:简单的顺序状态机 以下是一个…...
尝试使用tauri2+Django+React的项目
前言 使用Tauri2前端,本质是进程间的通信。并非前后端。 而想使用nw,先后端打包exe,再和前端打包成exe,并没有完成成功。 而笔者从Tauri中看到这种可能性。很有可能成功基于SeaORMMySQLTauri2ViteReact等的CRUD交互项目-CSDN博…...
用@keyframes-animation来实现动画效果
一、使用规则 keyframes 用于定义动画的关键帧。 animation属性 用于将keyframes动画用于元素上。 二、基本语法 keyframes keyframes xuanZhuan { /*xuanZhuan是动画名字,实现旋转*/0%{transform: rotate(0deg);}50%{transform: rotate(180deg);}100%{transform: rotate(…...
kernel中外部传递参数使用方法
在 Linux 内核模块开发中,module_param(rpc_tdebug, uint, 0600); 表示定义一个可通过外部传递参数进行配置的模块级变量,具体解析如下: 参数名称 rpc_tdebug 是模块参数的变量名,该变量需在代码中提前声明为静态全局变量&…...
AI赋能流域生态评估:从多源数据融合到服务价值预测的技术突破
流域生态系统服务评价是生态学与地理信息科学的交叉前沿,传统方法受限于数据碎片化与模型解释力不足。本文以随机森林-时空图卷积联合模型(RF-STGCN)为核心,结合2022年长江中游实际监测数据,详解AI技术在服务评价中…...
SZU软件工程大学生涯 2022~2026
用于个人面试前自我介绍,防止忘记或谈吐不流利。 面试官您好,我是来自深圳大学计算机与软件学院的软件工程专业的王雅贤。在校期间,我修读了程序设计基础、面向对象程序设计、数据结构、算法分析与设计、操作系统等核心课程,系统…...
如何设计一个合理的库存系统
库存管理系统是电商、供应链管理、仓储管理等核心系统之一。一个合理的库存系统需要同时满足高并发、数据一致性、实时性、扩展性等要求,以确保在各种业务场景下都能稳定运行。 本文将探讨如何设计一个合理的库存系统,包括库存模型设计、数据一致性策略…...
数据人的进阶之路:四年数仓实践与成长思考
前言 在数据仓库开发的过程中,常常会遇到很多值得思考的问题,它们不仅关乎技术的深度,也涉及业务理解、个人的成长,甚至是数据行业未来的价值。回顾过去的经历,有很多问题反复出现,甚至成为绕不开的课题&am…...
数据库原理及应用mysql版陈业斌实验一
🏝️专栏:Mysql_猫咪-9527的博客-CSDN博客 🌅主页:猫咪-9527-CSDN博客 “欲穷千里目,更上一层楼。会当凌绝顶,一览众山小。” 目录 实验一:数据库与数据表的定义和数据操作 1.实验数据如下 …...
Linux环境变量:深入解析与实用指南
目录 一、环境变量概述 二、环境变量的作用 三、环境变量的类型 3.1系统环境变量 3.2用户环境变量 四、环境变量的操作 4.1查看环境变量 4.2设置环境变量 4.3删除环境变量 五、环境变量的配置文件 六、环境变量的最佳实践 七、总结 环境变量是Linux系统中至关重要的…...
大数据 Spark 技术简介
Apache Spark 是一种快速、通用、可扩展的大数据处理引擎,最初由加州大学伯克利分校开发。它提供了一种高效的数据处理框架,可以处理大规模数据集,并在分布式计算集群上进行并行处理。 Apache Spark 的基本概念包括以下几个要点:…...
Go语言的基础类型
一基础数据类型 一、布尔型(Bool) 定义:表示逻辑真 / 假,仅有两个值:true 和 false内存占用:1 字节使用场景:条件判断、逻辑运算 二、数值型(Numeric) 1. 整数类型&…...
面试复习-基础网络+运维知识
一、TCP/IP模型及每层对应通信协议 1.1第一层-应用层 作用:服务及应用程序 HTTP --- 超文本传输协议--- 获取网页信息---80(TCP 80) HTTPS --- HTTP SSL(安全传输协议)/TLS ---443(TCP 443) …...
大屏设计新纪元:定制视觉盛宴
当城市天际线的巨型LED幕墙与元宇宙中的虚拟场景无缝交织,当博物馆的数字藏品在8K曲面屏上焕发新生,一个属于大屏设计的全新纪元已悄然降临。这场视觉革命不仅重构了信息传播的维度,更将“定制化体验”推向了前所未有的高度——每一寸屏幕都成…...
JavaIO流的使用和修饰器模式(直击心灵版)
系列文章目录 JavaIO流的使用和修饰器模式 文章目录 系列文章目录前言一、字节流: 1.FileInputStream(读取文件)2.FileOutputStream(写入文件) 二、字符流: 1..基础字符流:2.处理流:3.对象处理流:4.转换流: 三、修饰器…...
10-STL、位运算、常用函数库
1-STL vector vector是变长数组 //定义vector vector<int>a;//第一维长233,第二维长度动态变化 vector<int>b[233];//自定义的结构体类型也可以保存在vector中 struct res{...}; vector<rec>c;//函数 a.size();//返回vector的实际长度…...
【Ratis】Ratis Streaming概览
看了Tsz-Wo Nicholas Sze博士的一个关于Ratis的share,在share里提到了raits做的一个性能优化:客户端流。比较感兴趣,特此记录一下。如果想看原始分享的,可以搜关键词:Apache Ratis - A High Performance Raft Library 关于Ratis Stream的pdf介绍,在这个PR的附件里: [Ra…...
Python Seaborn面试题及参考答案
目录 如何用 stripplot () 绘制带随机偏移的分类散点图?如何控制 jitter 参数? swarmplot () 如何避免散点重叠?适用场景与数据量限制是什么? 使用 catplot () 绘制箱线图时,如何通过 kind 参数切换图表类型? 如何通过 hue 参数在分类图中添加第三个维度(如性别)? …...
linux下基本命令和扩展命令(安装和登录命令、文件处理命令、系统管理相关命令、网络操作命令、系统安全相关命令、其他命令)欢迎补充噢
基本命令 ls: 列出目录内容 ls:列出当前目录内容ls -l:以长格式列出(显示详细信息)ls -a:显示隐藏文件ls -lh:以易读格式显示文件大小 pwd: 显示当前工作目录 pwd:显示当前目录的绝对路径 cd:…...
K8S学习之基础四十:K8S配置altermanager发送告警到钉钉群
配置altermanager发送告警到钉钉群 创建钉钉群,设置机器人助手(必须是管理员才能设置),获取webhook webhook: https://oapi.dingtalk.com/robot/send?access_token25bed933a52d69f192347b5be4b2193bc0b257a6d9ae68d81619e3ae3d93f7c6…...
实用工具--OfficeAI 助手 v0.3.20(长期免费,2025-03-18 本地支持WPSWord联动)
软件简介 OfficeAI助手,作为Microsoft Office与WPS的得力智能插件,集文档自动生成、内容精准校对与润色、公式智能推荐等多功能于一体。它凭借强大的数据分析能力,深度融入Office/WPS办公生态,一键简化复杂流程,让办公…...
Android 关于compose的一些坑和理解
** 1.如何在 WindowManager.addView 中使用 Jetpack Compose** 一、引出问题 Android 开发中,很常见的一个场景,通过 WindowManager.addView() 添加一个 View 到屏幕上。Android 最新的视图框架 Jetpack Compose,如何应用进来。这个被添加的…...
ref setState 合成事件
ref & setState & 合成事件 受控组件的概念:数据改变视图的叫受控组件;通过dom操作改变的叫非受控。 语法:给refxxx赋一个值,然后通过this.refs.xxx就可以获取到相应dom元素,通过你这个名字存储的值就是这个do…...