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

【算法】动态规划专题⑩ —— 混合背包问题 python

news 来源：原创 2025/5/21 4:23:26

前置知识

【算法】动态规划专题⑤ —— 0-1背包问题 + 滚动数组优化
【算法】动态规划专题⑥ —— 完全背包问题 python
【算法】动态规划专题⑦ —— 多重背包问题 + 二进制分解优化 python

混合背包结合了三种不同类型的背包问题：0/1背包、完全背包和多重背包

进入正题

混合背包问题 https://www.acwing.com/problem/content/description/7/

题目描述

有 $N$ 种物品和一个容量是 $V$ 的背包。

物品一共有三类：

第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 $s_i$ 次（多重背包）；

每种体积是 $v_i$ ，价值是 $w_i$ 。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数， $N ， V$ ，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行三个整数 $v_i, w_i, s_i$ ，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。

$s_i = -1$ 表示第 $i$ 种物品只能用1次；
$s_i = 0$ 表示第 $i$ 种物品可以用无限次；
$s_i >0$ 表示第 $i$ 种物品可以使用 $s_i$ 次；

输出格式

输出一个整数，表示最大价值。

数据范围

$\lt N, V \le 1000$
$\lt v_i, w_i \le 1000$
$\le s_i \le 1000$

输入样例

输出样例：

code：

n, v = map(int, input().split())
dp = [0] * (v + 1)
for i in range(1, n + 1):vi, wi, si = map(int, input().split())if si == 0:  # 完全背包for j in range(vi, v + 1):dp[j] = max(dp[j], dp[j - vi] + wi)elif si == -1:  # 0-1背包for j in range(v, vi - 1, -1):dp[j] = max(dp[j], dp[j - vi] + wi)else:  # 多重背包group = []k = 1while si >= k:group.append((vi * k, wi * k))si -= kk *= 2if si > 0:group.append((vi * si, wi * si))for vi, wi in group:for j in range(v, vi - 1, -1):dp[j] = max(dp[j], dp[j - vi] + wi)
print(dp[v])

总结

这是背包问题篇的最后一节内容，相信你已经完全掌握了相关内容。~~完结撒花~~

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注谢谢

【算法】动态规划专题⑩ —— 混合背包问题 python

目录前置知识进入正题总结前置知识【算法】动态规划专题⑤ —— 0-1背包问题滚动数组优化【算法】动态规划专题⑥ —— 完全背包问题 python 【算法】动态规划专题⑦ —— 多重背包问题二进制分解优化 python 混合背包结合了三种不同类型的背包问题：0/1背包…...

编程日记 2025/5/21 4:23:26

Java高频面试之SE-20

hello啊，各位观众姥爷们！！！本baby今天又来了！哈哈哈哈哈嗝🐶 Java的泛型是什么？ Java 泛型（Generics） 是 Java 5 引入的一项重要特性，用于增强代码的类型安…...

编程日记 2025/5/20 21:59:52

springboot 事务管理

在Spring Boot中，事务管理是通过Spring框架的事务管理模块来实现的。Spring提供了声明式事务管理和编程式事务管理两种方式。通常，我们使用声明式事务管理，因为它更简洁且易于维护。 1. 声明式事务管理声明式事务管理是通过注解来实现的。…...

编程日记 2025/5/21 4:21:36

opentelemetry-collector 配置elasticsearch

一、修改otelcol-config.yaml receivers:otlp:protocols:grpc:endpoint: 0.0.0.0:4317http:endpoint: 0.0.0.0:4318 exporters:debug:verbosity: detailedotlp/jaeger: # Jaeger supports OTLP directlyendpoint: 192.168.31.161:4317tls:insecure: trueotlphttp/prometheus: …...

编程日记 2025/5/19 23:16:00

IDEA关联Tomcat，部署JavaWeb项目

将IDEA与Tomcat关联创建JavaWeb项目创建Demo项目将Tomcat作为依赖引入到Demo中添加 Web Application 编写前端和后端代码配置Tomcat server，并运行...

编程日记 2025/5/19 12:26:44

位图与位运算的深度联系：从图像处理到高效数据结构的C++实现与优化

在学习优选算法课程的时候，博主学习位运算了解到位运算的这个概念，之前没有接触过，就查找了相关的资料，丰富一下自身，当作课外知识来了解一下。位图（Bitmap）： 在计算机科学中有两种…...

编程日记 2025/5/18 11:07:58

运维_Mac环境单体服务Docker部署实战手册

Docker部署本小节，讲解如何将前端后端项目，使用 Docker 容器，部署到 dev 开发环境下的一台 Mac 电脑上。 1 环境准备需要安装如下环境： Docker：容器MySQL：数据库Redis：缓存Nginx&#x…...

编程日记 2025/5/20 6:15:48

DeepSeek-V3 论文解读：大语言模型领域的创新先锋与性能强者

论文链接：DeepSeek-V3 Technical Report 目录一、引言二、模型架构：创新驱动性能提升（一）基本架构（Basic Architecture）（二）多令牌预测（Multi-Token Prediction&#xf…...

编程日记 2025/5/21 2:41:08

react使用if判断

1、第一种 function Dade(req:any){console.log(req)if(req.data.id 1){return <span>66666</span>}return <span style{{color:"red"}}>8888</span>}2、使用 {win.map((req,index) > ( <> <Dade data{req}/>{req.id 1 ?…...

编程日记 2025/5/21 2:33:15

opencv:基于暗通道先验（DCP）的内窥镜图像去雾

目录项目大体情况暗通道先验（Dark Channel Prior, DCP）原理项目代码解析该项目是由我和我导师与舟山某医院合作开发的一个基于暗通道先验（Dark Channel Prior，DCP）的内窥镜图像去雾方法。具体来说，…...

编程日记 2025/5/21 2:11:47

2025年物联网相关专业毕业论文选题参考，文末联系，选题相关资料提供

一、智能穿戴解决方案研究方向序号解决方案论文选题论文研究方向1智能腰带健康监测基于SpringBoot和Vue的智能腰带健康监测数据可视化平台开发研究如何利用SpringBoot和Vue技术栈开发一个数据可视化平台，用于展示智能腰带健康监测采集的数据，如心率、血…...

编程日记 2025/5/16 2:17:44

npm无法加载文件因为此系统禁止运行脚本

安装nodejs后遇到问题： 在项目里【node -v】可以打印出来，【npm -v】打印不出来，显示npm无法加载文件因为此系统禁止运行脚本。但是在winr，cmd里【node -v】,【npm -v】都也可打印出来。解决方法： cmd里可以打印出…...

编程日记 2025/5/21 3:12:58

使用PyCharm创建项目以及如何注释代码

创建好项目后会出现如下图所示的画面，我们可以通过在项目文件夹上点击鼠标右键，选择“New”菜单下的“Python File”来创建一个 Python 文件，在给文件命名时建议使用英文字母和下划线的组合，创建好的 Python 文件会自动打开&#…...

编程日记 2025/5/18 21:12:42

Qt中QFile文件读写操作和QFileInfo文件信息读取方法（详细图文教程）

💪 图像算法工程师，专业从事且热爱图像处理，图像处理专栏更新如下👇： 📝《图像去噪》 📝《超分辨率重建》 📝《语义分割》 📝《风格迁移》 📝《目标检测》 &a…...

编程日记 2025/5/21 2:57:27

CF998A Balloons 构造

Balloons 算法：构造 rating : 1000 思路： 分情况讨论： 1. 当只有一个气球包时，肯定不行 2.当有两个气球包时，若两个气球包的气球个数相同则不行 3.其余的情况都是可以的，题目问给格里高利的气球包数…...

编程日记 2025/5/21 3:37:53

python基础入门：3.5实战：词频统计工具

Python词频统计终极指南：字典与排序的完美结合 import re from collections import defaultdictdef word_frequency_analysis(file_path, top_n10):"""完整的词频统计解决方案:param file_path: 文本文件路径:param top_n: 显示前N个高频词:return:…...

编程日记 2025/5/21 3:29:07

面试准备——Java理论高级【笔试，面试的核心重点】

集合框架 Java集合框架是面试中的重中之重，尤其是对List、Set、Map的实现类及其底层原理的考察。 1. List ArrayList： 底层是动态数组，支持随机访问（通过索引），时间复杂度为O(1)。插入和删除元素时&#…...

编程日记 2025/5/21 3:26:51

Docker 部署 verdaccio 搭建 npm 私服

一、镜像获取 # 获取 verdaccio 镜像 docker pull verdaccio/verdaccio 二、修改配置文件 cd /wwwroot/opt/docker/verdaccio/conf vim config.yaml config.yaml 配置文件如下，可以根据自己的需要进行修改 # # This is the default configuration file. It all…...

编程日记 2025/5/20 13:40:17

每日一题--数组中只出现一次的两个数字

数组中只出现一次的两个数字题目描述数据范围提示示例示例1示例2 题解解题思路位运算方法步骤： 代码实现代码解析时间与空间复杂度按位与操作获取最小位1的原理为什么选择最低有效的 1 位而不是其他位？ 题目描述一个整型数组里除了两个数字只出现一次…...

编程日记 2025/5/18 16:31:13

蓝耘智算平台与DeepSeek R1模型：推动深度学习发展

公主请阅前言何为DeepSeek R1DeepSeek R1 的特点DeepSeek R1 的应用领域DeepSeek R1 与其他模型的对比何为蓝耘智算平台使用蓝耘智算平台深度使用DeepSeek R1代码解释：处理示例输入：输出结果： 前言在深度学习领域，创新迭代日新…...

编程日记 2025/5/21 3:08:48

数据中台是什么？：架构演进、业务整合、方向演进

文章目录 1. 引言2. 数据中台的概念与沿革2.1 概念定义2.2 历史沿革 3. 数据中台的架构组成与关键技术要素解析3.1 架构组成3.2 关键技术要素 4. 数据中台与其他平台的对比详细解析 5. 综合案例：金融行业数据中台落地实践5.1 背景5.2 解决方案5.3 成果与价值 6. 方向…...

编程日记 2025/5/20 8:03:20

告别2023～2024

时间过得真快，距离上次写作2年多了。2023年～2024年的这两年时光里经历太多人生大事： 房贷，提前还贷买车，全款拿下租房搬家媳妇怀孕，独自照顾，……老人离世开盲盒喜提千金，百岁宴&am…...

编程日记 2025/5/20 0:48:57

PMO项目管理规范标准

这份文档是一份关于 PMO 项目管理规范标准的 V3.0 版本。以下是该文档的主要内容： 1. 立项管理 - 立项标准、级别划分和管理：定义了立项管理的标准、级别划分和管理，包括立项的审批流程、产品可行性分析、立项建议书、产品需求文档等。 - 立项…...

编程日记 2025/5/20 21:43:09

通过类加载和初始化的一些题目理解Java类加载过程

通过题目重点理解：Class加载流程和运行时区域目录子类和父类static变量父子类加载顺序2class.forName初始化子类和父类static变量 class Parent {static int a 1;static int b 2;static int c;static {c 3;System.out.println("parent static block&quo…...

编程日记 2025/5/21 3:56:04

【人工智能】解码语言之谜：使用Python构建神经机器翻译系统

《Python OpenCV从菜鸟到高手》带你进入图像处理与计算机视觉的大门！解锁Python编程的无限可能：《奇妙的Python》带你漫游代码世界神经机器翻译（NMT）是近年来机器翻译领域的一项重大突破。它利用深度学习模型，特别是循环神经网络（RNN）和Transformer网络，以端到端的…...

编程日记 2025/5/21 0:14:49

瑞芯微 Rockchip 系列 RK3588 主流深度学习框架模型转成 rknn 模型教程

前言在瑞芯微 Rockchip 芯片上进行 NPU 推理，需要先将模型文件转换成 rknn 模型文件，才能执行各种推理任务。本文将介绍如何安装各种工具，并最终实现将各种深度学习框架的模型文件转换成 rknn 文件。本教程不仅适合 RK3588 平台&#xff…...

编程日记 2025/5/18 15:38:00

51单片机俄罗斯方块计分函数

/************************************************************************************************************** * 名称：scoring * 功能：计分 * 参数：NULL * 返回：NULL * 备注：采用非阻塞延时 ****************…...

编程日记 2025/5/18 8:05:31

C++线程池

使用线程情况比较频繁的地方，由于线程的创建及销毁都会产生对资源的占用及性能的损耗。为了优化性能，提升效率，在这种场景中，就应该使用线程池来处理任务。线程池创建的关键点： 装载线程的容器，在C中使用…...

编程日记 2025/5/17 13:44:13

Golang GORM系列：定义GORM模型及关系指南

使用GORM进行数据库管理的核心是定义模型的技能。模型是程序的面向对象结构和数据库的关系世界之间的纽带。本文深入研究了在GORM中创建成功模型的艺术，研究了如何设计结构化的Go结构，用标记注释字段，以及开发跨模型的链接，以便最…...

编程日记 2025/5/19 3:48:22

ssm校园二手交易平台小程序

博主介绍：✌程序猿徐师兄、8年大厂程序员经历。全网粉丝15w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取源码联系🍅 👇🏻 精彩专栏推荐订阅👇…...

编程日记 2025/5/20 7:15:32

【虚幻引擎UE】AOI算法介绍与实现案例

【虚幻引擎UE】AOI算法介绍与实现一、AOI算法介绍AOI算法的典型应用场景二、AOI相关算法1. 边界框法（Bounding Box Method）2. 动态AOI算法3. 布尔运算（Boolean Operations）4. 四叉树（Quadtree）5. R树（R-Tree）6. 圆形AOI算法7. 网格分割（Grid Partitioning）8. 多边形…...

编程日记 2025/5/19 13:59:51

JavaScript 基础语法：变量、数据类型、运算符、条件语句、循环

JavaScript 是一种动态类型的脚本语言，广泛用于前端开发。以下是 JavaScript 基础语法的核心内容，包括变量、数据类型、运算符、条件语句和循环。 --- ### 1. 变量变量用于存储数据。JavaScript 中有三种声明变量的方式： - **var**&…...

编程日记 2025/5/19 7:40:41

ASP.NET Core 如何使用 C# 从端点发出 GET 请求

使用 C#，从 REST API 端点获取 JSON；如何从 REST API 接收 JSON 数据。本文需要 ASP .NET Core，并兼容 .NET Core 3.1、.NET 6和.NET 8。要将数据发布到端点，请参阅本文。使用 . 从端点发布 GET 数据非常容易HttpClient&…...

编程日记 2025/5/20 15:09:20

Docker 部署 MinIO | 国内阿里镜像

一、导读 Minio 是个基于 Golang 编写的开源对象存储套件，基于Apache License v2.0开源协议，虽然轻量，却拥有着不错的性能。它兼容亚马逊S3云存储服务接口。可以很简单的和其他应用结合使用，例如 NodeJS、Redis、MySQL等。二、…...

编程日记 2025/5/18 18:01:57

量化交易数据获取：xtquant库的高效应用

量化交易数据获取：xtquant库的高效应用在量化交易领域，历史行情数据的重要性不言而喻。它不仅为策略回测提供基础，也是实时交易决策的重要参考。本文将介绍如何使用xtquant库来高效获取和处理历史行情数据。技术背景与应用场景对于量化…...

编程日记 2025/5/20 10:32:17

Mysql中存储引擎各种介绍以及应用场景、优缺点

概述 MySQL 提供了多种存储引擎，每种引擎有不同的特点和适用场景。以下是几种常见的 MySQL 存储引擎的详细介绍，包括它们的底层工作原理、优缺点，以及为什么 MySQL 默认选择某种引擎。 1. InnoDB 底层工作原理： 事务支持&#…...

编程日记 2025/5/17 17:27:32

面试题整理：Java虚拟机 JVM 内存区域、垃圾回收、类加载器

文章目录 JVM虚拟机内存区域1. ⭐JVM的内存区域有哪些？每个区域的作用是什么？2. 堆和栈的区别是什么？3. 堆内存是如何划分的？4. 永久代和元空间是什么关系？5. 对JVM常量池的理解？6. ⭐Java 对象的创建过程&…...

编程日记 2025/5/16 21:55:45

ASP.NET Core 使用 WebClient 从 URL 下载

本文使用 ASP .NET Core 3.1，但它在.NET 5、 .NET 6和.NET 8上也同样适用。如果使用较旧的.NET Framework，请参阅本文，不过，变化不大。如果想要从 URL 下载任何数据类型，请参阅本文：HttpClient 使用WebC…...

编程日记 2025/5/18 23:53:22

第六届MathorCup高校数学建模挑战赛-A题：淡水养殖池塘水华发生及池水自净化研究

目录摘要 1 问题的重述 2 问题的分析 2.1 问题一的分析 2.2 问题二的分析 2.3 问题三的分析 2.4 问题四的分析 2.5 问题五的分析 3. 问题的假设 4. 符号说明 5. 模型的建立与求解 5.1 问题一的建模与求解 5.1.1 分析对象与指标的选取 5.1.2 折线图分析 5.1.3 相关性分析 5.1.4…...

编程日记 2025/5/15 14:40:51

GnuTLS: 在 pull 函数中出错。无法建立 SSL 连接。

提示信息 [root@localhost ~]# wget https://download.docker.com/linux/static/stable/x86_64/docker-27.5.1.tgz --2025-02-06 12:45:34-- https://download.docker.com/linux/static/stable/x86_64/docker-27.5.1.tgz 正在解析主机 download.docker.com (download.docker.…...

编程日记 2025/5/17 20:47:35

OpenAI 实战进阶教程 - 第十二节 : 多模态任务开发（文本、图像、音频）

适用读者与目标适用读者：已经熟悉基础的 OpenAI API 调用方式，对文本生成或数据处理有一定经验的计算机从业人员。目标：在本节中，你将学会如何使用 OpenAI 提供的多模态接口（图像生成、语音转录等）开发更…...

编程日记 2025/5/15 19:50:09

《qt easy3d中添加孔洞填充》

《qt easy3d中添加孔洞填充》效果展示一、创建流程二、核心代码效果展示参考链接Easy3D开发——点云孔洞填充一、创建流程创建动作，并转到槽函数，并将动作放置菜单栏，可以参考前文其中，槽函数on_actionHoleFill_triggered实现如下：...

编程日记 2025/5/15 19:50:08

windows蓝牙驱动开发-蓝牙常见问题解答

Windows 可以支持多少个蓝牙无线电？ Windows 中的蓝牙堆栈仅支持一个蓝牙无线电。此无线电必须符合蓝牙规范和最新的 Windows 硬件认证计划要求。蓝牙和 Wi-Fi 无线电如何有效共存？ 蓝牙和 Wi-Fi 无线电都在 2.4 GHz 频率范围内运行，因此…...

编程日记 2025/5/18 3:19:51

Ubuntu 下 nginx-1.24.0 源码分析 - ngx_ssl_version 函数

定义 event\ngx_event_openssl.h 中： #if (OPENSSL_VERSION_NUMBER > 0x10100001L)#define ngx_ssl_version() OpenSSL_version(OPENSSL_VERSION)#else#define ngx_ssl_version() SSLeay_version(SSLEAY_VERSION)#endif #if (OPENSSL_VERSION_NUMBER…...

编程日记 2025/5/17 10:35:36

提示工程：少样本提示（Few-shot Prompting）

少样本提示（Few-shot Prompting）是一种利用大语言模型从少量示例样本中学习并处理任务的方法。它的核心思想是利用大语言模型的上下文学习能力，通过在提示中增加“示例样本”来启发大语言模型达到举一反三的效果。这种方法避免了重新训练或者…...

编程日记 2025/5/20 12:36:13

从量化投资到AI大模型：DeepSeek创始人梁文锋的创新之路

一、学术的启蒙：学霸的崭露头角梁文锋的成长故事始于1985年，他出生在广东省湛江市的一个普通家庭。从小，梁文锋就展现出对知识的强烈渴望和非凡的学习能力，尤其在数学领域，他总是能够轻松解决复杂的难题，成为学校里备受瞩目的“学霸”。 2002年，年仅17岁的梁文锋以吴川…...

编程日记 2025/5/17 17:38:04

基于lstm+gru+transformer的电池寿命预测健康状态预测-完整数据代码

项目视频讲解：毕业设计：基于lstm+gru+transformer的电池寿命预测健康状态预测_哔哩哔哩_bilibili 数据：实验结果：...

编程日记 2025/5/15 19:50:05

物品匹配问题-25寒假牛客C

登录—专业IT笔试面试备考平台_牛客网这道题看似是在考察位运算,实则考察的是n个物品,每个物品有ai个,最多能够得到多少个物品的配对.观察题目可以得到,只有100,111,010,001(第一位是ci,第二位是ai,第三位是bi)需要进行操作,其它都是已经满足条件的对,可以假设对其中两个不同…...

编程日记 2025/5/21 0:01:12

Pyecharts系列课程05——散点图（Scatter）

本章我们学习Pyecharts中散点图的实现方法，散点图通常用于观察数据的分布和相关性。 1. 基础使用散点图也是数据直角坐标系，与我们之前的直方图、折线图的基本用法是一致的。示例： from pyecharts.charts import Scatterx_data [1, 2, …...

编程日记 2025/5/16 18:46:35

c/c++蓝桥杯经典编程题100道（18）括号匹配

括号匹配 ->返回c/c蓝桥杯经典编程题100道-目录目录括号匹配一、题型解释二、例题问题描述三、C语言实现解法1：栈匹配法（难度★） 解法2：计数器法（仅限单一括号类型，难度★☆） …...

编程日记 2025/5/20 22:00:32

目录

前置知识

进入正题

总结

相关文章：