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

【动态规划】混合背包模板

news 来源：原创 2025/9/6 19:08:40

混合背包问题题解

题目传送门：AcWing 7. 混合背包问题

一、题目描述

有 N 种物品和一个容量是 V 的背包。物品分为三类：

01背包：只能用1次（si = -1）
完全背包：可以用无限次（si = 0）
多重背包：最多只能用 si 次（si > 0）

每种物品有体积 vi 和价值 wi。求解如何装入物品，使得总体积不超过背包容量，且总价值最大。

二、题目分析

本题是 01背包、完全背包和多重背包 的混合问题，需要根据 si 的值选择不同的处理方式：

si = -1：转化为 01背包（即 si = 1 的多重背包）
si = 0：按 完全背包 处理
si > 0：按 多重背包 处理（采用二进制优化）

三、问题思考（算法分析）

01背包：每个物品只能选或不选（si = 1）。
完全背包：每个物品可以选无限次，从小到大枚举体积。
多重背包：每个物品最多选 si 次，采用 二进制优化 拆分为若干 01背包 问题。

四、动态规划思路

a. 状态表示

f[j]：背包容量为 j 时的最大价值。

b. 初始化

f[0…V] = 0：初始时背包为空，价值为0。

c. 状态转移推导

完全背包（si = 0）：
- 从小到大枚举体积 j，确保物品可重复选：
```
for (int j = v; j <= m; j++)f[j] = max(f[j], f[j - v] + w);
```

01背包和多重背包（si ≠ 0）：

si = -1 时，转化为 si = 1。

采用 二进制优化 拆分物品，转化为 01背包：

for (int k = 1; k <= s; k *= 2) {for (int j = m; j >= k * v; j--)f[j] = max(f[j], f[j - k * v] + k * w);s -= k;
}
if (s) {for (int j = m; j >= s * v; j--)f[j] = max(f[j], f[j - s * v] + s * w);
}

d. 最终结果

f[m]：容量为 m 时的最大价值。

五、代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int f[N];void solve() {cin >> n >> m;for (int i = 1; i <= n; i++) {int v, w, s;cin >> v >> w >> s;// 完全背包（从小到大枚举体积）if (s == 0) {for (int j = v; j <= m; j++) {f[j] = max(f[j], f[j - v] + w);}}// 01背包和多重背包（二进制优化）else {if (s == -1) s = 1; // 01背包是特殊的多重背包（si=1）// 二进制拆分for (int k = 1; k <= s; k *= 2) {for (int j = m; j >= k * v; j--)f[j] = max(f[j], f[j - k * v] + k * w);s -= k;}if (s) {for (int j = m; j >= s * v; j--)f[j] = max(f[j], f[j - s * v] + s * w);}}}cout << f[m];
}signed main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

六、重点细节

完全背包 vs 01背包：
- 完全背包从小到大枚举 j，允许重复选。
- 01背包从大到小枚举 j，防止重复选。
二进制优化：
- 将 si 拆分为 1, 2, 4, …, 剩余部分，转化为多个 01背包 问题。
si = -1 的处理：
- 直接视为 si = 1 的多重背包。

七、复杂度分析

时间复杂度：O(NV log S)，其中 S 是物品数量的最大值（二进制优化后）。
空间复杂度：O(V)，使用一维数组优化。

八、总结

本题是 背包问题的综合应用，关键在于：

分类处理：根据 si 的值选择不同的背包模型。
二进制优化：高效处理多重背包问题。
空间优化：使用 一维数组 减少空间消耗。

熟练掌握 01背包、完全背包和多重背包 的核心思想，即可灵活解决此类问题。

【动态规划】混合背包模板

混合背包问题题解题目传送门：AcWing 7. 混合背包问题一、题目描述有 N 种物品和一个容量是 V 的背包。物品分为三类： 01背包：只能用1次（si -1）完全背包：可以用无限次（si 0）多…...

编程日记 2025/9/6 19:08:40

Linux 线程1-线程的概念、线程与进程区别、线程的创建、线程的调度机制、线程函数传参

目录 1.线程概念 1.1 线程的核心特点 1.2‌线程的工作模型‌ 1‌.3线程的潜在问题‌ ‌ 1.4 进程和线程区别 1.4.1‌执行与调度‌ ‌ 1.4.2进程和线程区别对比表 1.4.3应用场景‌ ‌ 1.4.4总结 2.线程的创建 2.1验证进程结束后，进程中所有的线程都会强制…...

编程日记 2025/8/29 12:01:17

Python 助力人工智能与机器学习的深度融合

技术革新的 “源动力” 在当今数字化时代，人工智能（AI）与机器学习（ML）无疑是最具影响力的技术领域，它们如同强大的引擎，推动着各个行业的变革与发展。Python 凭借其简洁易读的语法、丰富的库和…...

编程日记 2025/9/3 4:33:25

【GPT写代码】动作视频切截图研究器

目录背景源代码 end 背景用python写一个windows环境运行的动作视频切截图研究器，用路径浏览的方式指定待处理的视频文件，然后点击分析按钮，再预览区域显示视频预览画面，然后拖动时间轴，可以在预览区域刷新显示相应的…...

编程日记 2025/8/29 15:08:04

从0到神谕：GPT系列的进化狂想曲——用AI之眼见证人类语言的终极形态

开始：语言模型的星际跃迁在人工智能的浩瀚星海中，GPT系列如同光年加速器，推动人类语言的理解与生成突破维度限制。从2018年GPT-1的初试啼声，到2025年GPT-4o的全模态智慧，这场进化狂想曲不仅是技术的迭代史&#xff0c…...

编程日记 2025/9/2 16:48:47

Go并发编程终极指南：深入内核与工程实践

Go并发编程终极指南：深入内核与工程实践 Go并发编程终极指南：深入内核与工程实践 Go并发编程终极指南：深入内核与工程实践一、Goroutine调度器深度解构1.1 调度器演进史1.2 调度器源码级解析1.3 调度器可视化诊断二、Channel底层实现揭秘2.1…...

编程日记 2025/8/27 18:31:52

Neo4j数据库操作语法使用的数据库版本 (终端查询) >neo4j --version 2025.03.0批量上传数据 UNWIND [{name: Alice, age: 30},{name: Bob, age: 25} ] AS person CREATE (p:Person) SET p.name = person.name, p.age = person.age RETURN p;查询结点总数 MATCH (n) RETU…...

编程日记 2025/9/5 11:21:30

DHCP之中继 Relay-snooping及配置命令

随着网络规模的不断扩大，网络设备不断增多，企业内不同的用户可能分布在不同的网段，一台 DHCP 服务器在正常情况下无法满足多个网段的地址分配需求。如果还需要通过 DHCP 服务器分配 IP 地址，则需要跨网段发送 DHCP 报文 DHCP Rel…...

编程日记 2025/9/2 15:19:06

小迪安全110-tp框架，版本缺陷，不安全写法，路由访问，利用链

入口文件前端页面显示文件就是这串代码让我们看到前端的笑脸图不用入口文件我们要访问这个文件就要按照开发手册的url访问模式那就是index.php/index/index/index 对应的就是模块，控制器，操作，函数名如果想要创建新模块，和操…...

编程日记 2025/9/4 6:41:14

Vanna：用检索增强生成（RAG）技术革新自然语言转SQL

引言：为什么我们需要更智能的SQL生成？ 在数据驱动的业务环境中，SQL 仍然是数据分析的核心工具。然而，编写正确的 SQL 查询需要专业知识，而大型语言模型（LLM）直接生成的 SQL 往往存在**幻觉&…...

编程日记 2025/8/31 22:59:09

大语言模型应用和训练（人工智能）

RAG（Retrieval Augmented Generation，检索增强生成） 定义：是一种将外部知识检索与语言模型生成能力相结合的技术。在传统的大语言模型中，模型的知识是在预训练阶段学到的，可能存在知识过时或不完整的问题。…...

编程日记 2025/9/4 17:44:05

NLP高频面试题（三十五）——LLaMA / ChatGLM / BLOOM的区别

一、LLaMA 训练数据 LLaMA由Meta开发，拥有多个参数规模的版本：7B、13B、33B和65B。其中，较小的7B和13B版本采用了约1万亿tokens进行训练，而更大的33B和65B版本使用了约1.4万亿tokens进行训练。模型结构特点 LLaMA采用与GPT类似的causal decoder-only Transformer结构，…...

编程日记 2025/9/4 13:24:44

【Python Cookbook】字符串和文本（五）：递归下降分析器

目录案例目录案例字符串和文本（一）1.使用多个界定符分割字符串2.字符串开头或结尾匹配3.用 Shell 通配符匹配字符串4.字符串匹配和搜索5.字符串搜索和替换字符串和文本（三）11.删除字符串中不需要的字符12.审查清理文本字符串1…...

编程日记 2025/9/4 11:47:12

专为零基础初学者设计的最简前端学习路线，聚焦核心内容，避免过度扩展，帮你快速入门并建立信心！

第一阶段：HTML CSS（2-3周） 目标：能写出静态网页，理解盒子模型和布局。 HTML基础常用标签：<div>, <p>, <img>, <a>, <ul>, <form> 语义化标签：<head…...

编程日记 2025/8/31 13:53:56

大模型-爬虫prompt

爬虫怎么写prompt 以下基于deepseek r1 总结： 以下是为大模型设计的结构化Prompt模板，用于生成专业级网络爬虫Python脚本。此Prompt包含技术约束、反检测策略和数据处理要求，可根据具体需求调整参数： 爬虫脚本生成Prompt模板1 …...

编程日记 2025/9/4 14:30:52

PyTorch深度实践：基于累积最大值的注意力机制设计与性能优化

引言：注意力机制的创新与挑战在自然语言处理和序列建模中，注意力机制（Attention）是提升模型性能的关键技术。传统基于 softmax 的注意力机制虽然成熟，但在计算效率和长序列建模中存在局限。本文将介绍一种创新的注意…...

编程日记 2025/9/4 16:03:13

编程bug001：off by one （差一错误）

为什么看似简单的编码错误可能造成大灾难？ Off-by-One Error（简称OBOE），即由于边界条件处理不当，导致循环、计数或索引时多算一次或少算一次的错误。这是非常常见的编程bug类型，尤其在处理数组、字符串或范…...

编程日记 2025/9/4 0:09:05

JavaScript 中常见的鼠标事件及应用

JavaScript 中常见的鼠标事件及应用在 JavaScript 中，鼠标事件是用户与网页进行交互的重要方式，通过监听这些事件，开发者可以实现各种交互效果，如点击、悬停、拖动等。在 JavaScript 中，鼠标事件类型多样&#xff0…...

编程日记 2025/9/1 11:21:50

使用Expo框架开发APP——详细教程

在移动应用开发日益普及的今天，跨平台开发工具越来越受到开发者青睐。Expo 是基于 React Native 的一整套工具和服务，它能够大幅降低原生开发的门槛，让开发者只需关注业务逻辑和界面实现，而不用纠结于复杂的原生配置。本文将从零开…...

编程日记 2025/9/2 5:30:14

深入探究 Hive 中的 MAP 类型：特点、创建与应用

摘要在大数据处理领域，Hive 作为一个基于 Hadoop 的数据仓库基础设施，提供了方便的数据存储和分析功能。Hive 中的 MAP 类型是一种强大的数据类型，它允许用户以键值对的形式存储和操作数据。本文将深入探讨 Hive 中 MAP 类型的特点，详细介绍如何创建含有 MAP 类型字段的表…...

编程日记 2025/8/31 13:04:34

前端开发工厂模式的优缺点是什么？

一、什么是工厂模式？ 工厂模式属于创建型设计模式，核心思想是将对象的实例化过程封装到特定方法或类中，让客户端不需要直接通过new关键字创建对象。举个例子：就像奶茶店不需要顾客自己调配饮品，而是通过"点单-…...

编程日记 2025/8/30 15:18:01

框架PasteForm实际开发案例，换个口味显示数据，支持echarts，只需要标记几个特性即可在管理端显示(2)

PasteForm框架的主要思想就是对Dto进行标记特性，然后管理端的页面就会以不一样的UI呈现使用PasteForm框架开发，让你免去开发管理端的烦恼，你只需要专注于业务端和用户端！在管理端中，如果说表格是基本的显示方式，那么图表chart就是一个锦上添花的体现！如果一个项目拥…...

编程日记 2025/8/28 0:54:46

QEMU学习之路（5）— 从0到1构建Linux系统镜像

QEMU学习之路（5）— 从0到1构建Linux系统镜像一、前言参考：从内核到可启动镜像：0到1构建你的极简Linux系统二、linux源码获取安装编译依赖 sudo apt install -y build-essential libncurses-dev flex bison libssl-dev li…...

编程日记 2025/9/5 4:27:37

AI Agent设计模式一：Chain

概念 ：线性任务流设计 ✅ 优点：逻辑清晰易调试，适合线性处理流程❌ 缺点：缺乏动态分支能力 from typing import TypedDictfrom langgraph.graph import StateGraph, END# 定义后续用到的一些变量 class CustomState(TypedDict):p…...

编程日记 2025/8/31 15:04:34

实操（进程状态，R/S/D/T/t/X/Z）Linux

1 R 状态并不直接代表进程在运行，而是该进程在运行队列中进行排队，由操作系统在内存维护的队列 #include <stdio.h> #include <unistd.h>int main() {while(1){printf("我在运行吗\n");sleep(1);}return 0; }查看状态&#xff08…...

编程日记 2025/9/4 0:24:54

T-SQL语言的自动化运维

T-SQL语言的自动化运维引言在现代IT环境中，自动化运维成为了提高效率、降低成本、提升稳定性的重要手段。数据库作为系统的重要组成部分，运维工作往往需要耗费大量的人力物力。T-SQL（Transact-SQL）作为Microsoft SQL Server的…...

编程日记 2025/8/30 0:04:28

Day06 分割编译与中断处理

文章目录 1. 例程harib03c（c源文件分割并整理makefile文件）2. 例程harib03c（用于描述段的信息）3. 例程harib03d（初始化PIC）4. 例程harib03e（中断处理程序） 1. 例程harib03c&#xff…...

编程日记 2025/9/4 18:04:13

数字化三维实训室：无穿戴动作捕捉技术如何赋能体育与舞蹈

在高校体育与舞蹈教学中，精准的动作训练至关重要。传统训练方式依赖教练的肉眼观察与手动记录，存在效率低下、误差较大的情况。尤其在快速连续动作或复杂肢体形态的捕捉中，人工判读易受主观经验限制，难以实现标准化评估。面对传统…...

编程日记 2025/9/5 13:42:30

6. RabbitMQ 死信队列的详细操作编写

6. RabbitMQ 死信队列的详细操作编写文章目录 6. RabbitMQ 死信队列的详细操作编写1. 死信的概念2. 消息 TTL 过期(触发死信队列)3. 队列超过队列的最大长度(触发死信队列)4. 消息被拒(触发死信队列)5. 最后： 1. 死信的概念先从概念上解释上搞清楚这个定义&#…...

编程日记 2025/9/3 17:58:47

AI浪潮下，新手短视频制作的破局之道

AI浪潮下，新手短视频制作的破局之道引言：短视频新时代，AI 带来的机遇与挑战在当下这个信息飞速流转的时代，短视频已然成为了人们生活中不可或缺的一部分。无论是在通勤路上、午休间隙，还是茶余饭后，打开…...

编程日记 2025/8/27 13:01:04

合肥SMT贴片制造工艺全解析

内容概要作为电子制造领域的核心工艺，SMT（表面贴装技术）在合肥地区电子产业链中占据重要地位。本解析以合肥本地化生产场景为基础，系统梳理从焊膏印刷到成品检测的全流程工艺框架。具体而言，制造流程涵盖四大核心阶段…...

编程日记 2025/9/5 19:34:47

ctfshow VIP题目限免协议头信息泄露

根据提示是协议头信息泄露，那就我们抓个包，抓包才能看到请求体响应体里的协议头啊，抓包之后在响应包里发现了 flag...

编程日记 2025/8/27 21:13:43

【国产工具链发展，生态链分析，TSMaster VS Zcanpro的技术对比】

黎明篇：国产汽车测试工具链的崛起、差距与未来副标题： 从跟随到超越，中国技术如何重塑全球研发体系一、国产工具链的崛起逻辑政策驱动：信创战略与供应链安全需求国家“十四五”规划明确提出支持关键领域技术自主化&#xff0…...

编程日记 2025/9/6 5:24:36

Linux线程同步与互斥：【线程互斥】【线程同步】【线程池】

目录一.线程互斥 1.1相关概念 1.2互斥量为什么会出现负数？？ 互斥量的接口问题： 1.3互斥量实现原理探究 1.4互斥量封装二.线程同步 2.1条件变量 2.2同步概念与竞态条件 2.3接口 2.4生产者消费者模型优点 2.5基于BlockingQueue的…...

编程日记 2025/9/3 11:58:30

网络安全基础知识总结

什么是网络安全采取必要措施，来防范对网络的攻击，侵入，干扰，破坏和非法使用，以及防范一些意外事故，使得网络处于稳定可靠运行的状态，保障网络数据的完整性、保密性、可用性的能力(CIA)。举例…...

编程日记 2025/9/5 21:25:18

请求被中止: 未能创建 SSL/TLS 安全通道。

需要安装vs2019社区办，下载VisualStudioSetup.exe后，报无法从"https://aka,ms/vs/16/release/channel"下载通道清单错误，接着打开%temp%目录下的最新日志，发现日志里报： [27d4:000f][2025-04-04T21:15:43] …...

编程日记 2025/8/29 9:34:06

FPGA学习（四）——状态机重写LED流水灯并仿真

FPGA学习（四）——状态机重写LED流水灯并仿真目录 FPGA学习（四）——状态机重写LED流水灯并仿真一、状态机编程思想1、状态机要素2、状态迁移图3、状态机写法二、LED流水灯仿真实现1、代码实现2、modesim仿真三、实现效果1、仿真…...

编程日记 2025/9/6 0:30:24

spark 集群

hadoop客户端环境准备找到资料包路径下的Windows依赖文件夹，拷贝hadoop-3.1.0到非中文路径（比如d:\hadoop-3.1.0） ① 打开环境变量 ② 在下方系统变量中新建HADOOP_HOME环境变量,值就是保存hadoop的目录。效果如下： ③ 配置P…...

编程日记 2025/9/4 1:26:15

leetcode117 填充每个节点的下一个右侧节点指针2

LeetCode 116 和 117 都是关于填充二叉树节点的 next 指针的问题，但它们的区别在于树的类型不同，117与 116 题类似，但给定的树是普通二叉树（不一定完全填充），即某些节点可能缺少左或右子节点。树的结构…...

编程日记 2025/8/30 4:39:47

Java全栈面试宝典：线程安全机制与Spring Boot核心原理深度解析

目录一、Java线程安全核心原理 🔥 问题1：线程安全的三要素与解决方案线程安全风险模型线程安全三要素 synchronized解决方案 🔥 问题2：synchronized底层实现全解析对象内存布局 Mark Word结构（64位系统&…...

编程日记 2025/9/6 3:32:24

CCF GESP C++编程三级认证真题 2025年3月

C 三级 2025 年 03 月题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 答案 D B A A B A C A C D D D B D C 1 单选题第 1 题 Base64 编码将每3字节的输入数据编码为 4 字节的输出数据。如果输入数据长度不是 3 的倍数，会用号填充。在Base64编码中，如果…...

编程日记 2025/8/27 21:13:21

人工智能爬虫导致维基共享资源带宽需求激增 50%

2025 年 4 月 1 日，维基媒体基金会在博文中表示，自 2024 年 1 月以来，维基共享资源下载多媒体的带宽消耗激增 50%，这一变化趋势主要由用于 AI 训练数据集的网络爬虫导致。以下是具体分析1： 爬虫流量特征与数据存储模式…...

编程日记 2025/8/31 16:04:58

方案精读：华为数据治理之旅【全文阅读】

本文介绍了华为的数据管理工作，包括数据治理、数据质量建设、数据管理工作两阶段历程、数据管理组织和数据管理工作思考。华为以业务数字化为前提，以数据入湖为基础，重点建设数据中台，提高数据质量和管理能力，以支撑公司数字化转型。重点内容： 1. 数据治理：华为进行数…...

编程日记 2025/9/5 19:32:39

Tradingview 策略分享 - SSL 混合和 CE 交易策略

交易策略｜https://v.wkbrowser.com/s/e9DIvLGvYRo/｜复制浏览器打开各位交易员大家好在本文中，我将分享一个简单的日内交易策略。我将 SSL 混合指标与 CE EXIT 相结合，以创建一个高效且有利可图的设置。此策略简单而强大&#x…...

编程日记 2025/9/4 13:26:38

华为OD机试真题——投篮大赛（2025A卷：100分）Java/python/JavaScript/C++/C语言/GO六种最佳实现

2025Q1 A卷 100分题型本文涵盖详细解题思路、代码注释、讲解、复杂的分析以及测试用例； 并提供Java、python、JavaScript、C、C语言、GO六种语言的最佳实现方式！ 华为OD机试A卷真题《投篮大赛》： 题目名称：投篮大赛知识点&am…...

编程日记 2025/9/6 2:41:52

rcore day2

目前常见的操作系统内核都是基于 C 语言的，为何要推荐 Rust 语言？ C 语言的指针灵活且易于使用，但不保证安全性，且缺x少有效的并发支持。这导致内存和并发漏洞成为当前基于 C 语言的主流操作系统的噩梦。Rust 语言具有与 C 一样的…...

编程日记 2025/9/5 3:08:44

【MATLAB定位例程】TDOA（到达时间差）的chan-tylor，三维环境，附完整代码

该代码实现了基于三维空间的动态目标TDOA定位，结合了Chan算法（解析解）与Taylor级数展开法（迭代优化）的双重优势。文章目录运行结果MATLAB代码代码讲解代码功能概述核心算法原理代码结构解析可视化与结果分析运行结果定位示意图：三轴状态曲线：三轴误差曲线： MA…...

编程日记 2025/9/2 3:02:30

LLM面试题六

NLP方向CRF算法面试题什么是CRF?CRF的主要思想是什么？ 设X与Y是随机变量，P(Y | X)是给定条件X的条件下Y的条件概率分布，若随机变量Y构成一个由无向图G(V,E)表示的马尔科夫随机场。则称条件概率分布P(X | Y)为条件随机场。CRF的主要思想统计…...

编程日记 2025/9/5 6:42:36

FPGA(四)——状态机

FPGA(四)——状态机文章目录 FPGA(四)——状态机一、状态机编程思想二、LED流水灯仿真实验三、实现效果四、CPLD和FPGA芯片主要技术区别五、hdlbitsFPGA——组合逻辑学习1、创建一个D触发器2、简单状态转换3、4位移位寄存器4、计数器1-125、边缘捕获寄存器一、状态机编程思想…...

编程日记 2025/9/1 8:44:50

AI 浪潮下企业身份管理：特点凸显，安全挑战升级

“在 AI 时代的浪潮中，企业身份管理是安全之锚，精准把握权限边界，方能抵御身份安全的暗流。” 在人工智能迅猛发展的当下，企业身份管理呈现出诸多新特点，同时也面临着前所未有的身份安全挑战。要理解这些，我…...

编程日记 2025/9/2 10:07:58