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

背包问题详解

news 来源：原创 2025/6/21 1:26:31

一、问题引入：什么是背包问题？

背包问题是经典的动态规划问题，描述如下：

  • 有一个容量为 m 的背包

  • 有 n 个物品，每个物品有体积 v 和价值 w

  • 目标：选择物品装入背包，使总价值最大且总体积不超过 m

  • 限制：每个物品只能选一次（0-1背包）

动态规划解法

使用DP数组 f[i] 表示容量为 i 时的最大价值

三、C语言代码逐行解析

#include <stdio.h>
#define N 1010  // 定义最大容量int f[N];  // DP数组，f[i]表示容量i时的最大价值int main() {int n, m;scanf("%d%d", &n, &m);  // 输入物品数量和背包容量while(n--) {  // 遍历每个物品int v, w;scanf("%d%d", &v, &w);  // 输入物品体积和价值for(int i = m; i >= v; i--) {  // 逆向更新DP数组int value = f[i - v] + w;  // 选当前物品的新价值if(value > f[i]) f[i] = value;  // 更新最大值}}printf("%d", f[m]);  // 输出最大价值return 0;
}

四、图解执行过程

输入示例：

3 5  // 3个物品，背包容量5
2 3  // 物品1：体积2，价值3
1 2  // 物品2：体积1，价值2 
3 4  // 物品3：体积3，价值4

DP数组变化：

处理阶段f[0]f[1]f[2]f[3]f[4]f[5]
初始状态000000
物品1003333
物品2023555
物品3023567

最优解：f[5] = 7（选择物品1和物品3）

五、为什么必须逆向更新？

  • 正向更新会导致重复计算（变成完全背包问题）

  • 逆向更新保证每个物品只被考虑一次

示例对比：

// 错误的正向更新（完全背包）
for(int i = v; i <= m; i++)  // 正确的逆向更新（0-1背包）  
for(int i = m; i >= v; i--)

六、复杂度分析

指标暴力解法动态规划
时间复杂度O(2ⁿ)O(n×m)
空间复杂度O(n)O(m)

七、实际应用场景

  1. 资源分配问题

  2. 投资组合优化

  3. 裁剪问题

  4. 密码学中的子集和问题

八、常见变种问题

  1. 完全背包：物品可重复选（正向更新）

  2. 多重背包：物品有数量限制

  3. 分组背包：物品分组，每组只能选一个

  4. 依赖背包：物品间有依赖关系

九、优化与扩展

  1. 滚动数组优化：进一步减少空间复杂度

  2. 记录选择方案：增加路径记录数组

  3. 超大背包问题：当m很大时，改用价值作为DP维度

相关文章：

背包问题详解

一、问题引入&#xff1a;什么是背包问题&#xff1f; 背包问题是经典的动态规划问题&#xff0c;描述如下&#xff1a; 有一个容量为 m 的背包 有 n 个物品&#xff0c;每个物品有体积 v 和价值 w 目标&#xff1a;选择物品装入背包&#xff0c;使总价值最大且总体积不超过…...

编程日记 2025/6/21 1:26:31

oracle linux 95 升级openssh 10 和openssl 3.5 过程记录

1. 安装操作系统&#xff0c;注意如果可以选择&#xff0c;选择安装开发工具&#xff0c;主要是后续需要编译安装&#xff0c;需要gcc 编译工具。 2. 安装操作系统后&#xff0c;检查zlib 、zlib-dev是否安装&#xff0c;如果没有&#xff0c;可以使用安装镜像做本地源安装&a…...

编程日记 2025/5/20 8:16:04

Tomcat发布websocket

一、tomcal的lib放入文件 tomcat-websocket.jar websocket-api.jar 二、代码示例 package com.test.ws;import com.test.core.json.Jmode;import javax.websocket.*; import javax.websocket.server.ServerEndpoint; import java.util.concurrent.CopyOnWriteArraySet; imp…...

编程日记 2025/6/21 0:24:36

[思维模式-41]：在确定性与不确定性的交响中：人类参与系统的韧性密码。

前言&#xff1a; “任何信息系统&#xff0c;无论怎么复杂&#xff0c;哪怕是几万人同时开发的系统&#xff0c;如无线通信网络&#xff0c;通过标准、设计、算法、完毕的测试、过程的管控等&#xff0c;都是可预测和确定性的。 一个系统&#xff0c;一旦叠加了人的元素和因素…...

编程日记 2025/6/21 1:22:50

维智定位 Android 定位 SDK

概述 维智 Android 定位 SDK是为 Android 移动端应用提供的一套简单易用的定位服务接口&#xff0c;为广大开发者提供融合定位服务。通过使用维智定位SDK&#xff0c;开发者可以轻松为应用程序实现极速、智能、精准、高效的定位功能。 重要&#xff1a;为了进一步加强对最终用…...

编程日记 2025/6/21 1:14:22

Vue3：脚手架

工程环境配置 1.安装nodejs 这里我已经安装过了&#xff0c;只需要打开链接Node.js — Run JavaScript Everywhere直接下载nodejs&#xff0c;安装直接一直下一步下一步 安装完成之后我们来使用电脑的命令行窗口检查一下版本 查看npm源 这里npm源的地址是淘宝的源&#xff0…...

编程日记 2025/5/23 19:07:48

Android native崩溃问题分析

最近在做NDK项目的时候&#xff0c;出现了启动应用就崩溃了&#xff0c;崩溃日志如下&#xff1a; 10:41:04.743 A Build fingerprint: samsung/g0qzcx/g0q:13/TP1A.220624.014/S9060ZCU4CWH1:user/release-keys 10:41:04.743 A Revision: 12 10:41:04.743 A ABI: arm64…...

编程日记 2025/6/3 0:32:48

Playwright vs Selenium：2025 年 Web 自动化终极对比指南

1. 引言 Web 自动化领域正在迅速发展&#xff0c;在 2025 年&#xff0c;Playwright 与 Selenium 之间的选择已成为开发团队面临的重要决策。Selenium 作为行业标准已有十多年&#xff0c;而 Playwright 作为现代替代方案&#xff0c;以卓越的性能和现代化特性迅速崛起。 本指…...

编程日记 2025/6/20 10:40:11

数据结构（3）线性表-链表-单链表

我们学习过顺序表时&#xff0c;一旦对头部或中间的数据进行处理&#xff0c;由于物理结构的连续性&#xff0c;为了不覆盖&#xff0c;都得移&#xff0c;就导致时间复杂度为O&#xff08;n&#xff09;&#xff0c;还有一个潜在的问题就是扩容&#xff0c;假如我们扩容前是10…...

编程日记 2025/5/29 13:37:59

Python 中的 typing.ClassVar 详解

一、ClassVar 的定义和基本用途 ClassVar 是 typing 模块中提供的一种特殊类型&#xff0c;用于在类型注解中标记类变量&#xff08;静态变量&#xff09;。根据官方文档&#xff0c;使用 ClassVar[…] 注释的属性表示该属性只在类层面使用&#xff0c;不应在实例上赋值 例如&…...

编程日记 2025/6/21 1:08:30

主流数据库运维故障排查卡片式速查表与视觉图谱

主流数据库运维故障排查卡片式速查表与视觉图谱 本文件将主文档内容转化为模块化卡片结构&#xff0c;并补充数据库结构图、排查路径图、锁机制对比等视觉图谱&#xff0c;以便在演示、教学或现场排障中快速引用。 &#x1f4cc; 故障卡片速查&#xff1a;连接失败 数据库检查…...

编程日记 2025/6/21 0:26:40

Unity：延迟执行函数：Invoke()

目录 Unity 中的 Invoke() 方法详解 什么是 Invoke()&#xff1f; 基本使用方法 使用要点 延伸功能 ❗️Invoke 的局限与注意事项 在Unity中&#xff0c;延迟执行函数是游戏逻辑中常见的需求&#xff0c;比如&#xff1a; 延迟切换场景 延迟播放音效或动画 给玩家时间…...

编程日记 2025/6/21 1:10:54

医学影像系统性能优化与调试技术：深度剖析与实践指南

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家、CSDN平台优质创作者&#xff0c;高级开发工程师&#xff0c;数学专业&#xff0c;10年以上C/C, C#, Java等多种编程语言开发经验&#xff0c;拥有高级工程师证书&#xff1b;擅长C/C、C#等开发语言&#xff0c;熟悉Java常用开…...

编程日记 2025/5/26 10:00:38

【HTML5学习笔记1】html标签（上）

web标准&#xff08;重点&#xff09; w3c 构成&#xff1a;结构、表现、行为&#xff0c;结构样式行为相分离 结构&#xff1a;网页元素整理分类 html 表现&#xff1a;外观css 行为&#xff1a;交互 javascript html标签 1.html语法规范 1&#xff09; 所有标签都在…...

编程日记 2025/5/29 16:59:24

SearchIndexablesProvider

实现的 provider 根据索引添加文档可知&#xff0c;该 provider 需要继承自 frameworks/base/core/java/android/provider/SearchIndexablesProvider.java 类&#xff0c;并且添加权限 android.permission.READ_SEARCH_INDEXABLES。过滤 Settings 代码&#xff0c;可以轻易找到…...

编程日记 2025/5/26 10:42:29

《k-means 散点图可视化》实验报告

一&#xff0c;实验目的 本次实验旨在通过Python编程实现k - means算法的散点图可视化。学习者将编写代码&#xff0c;深入理解聚类分析基本原理与k - means算法实现流程&#xff0c;掌握数据聚类及可视化方法&#xff0c;以直观展示聚类结果。 二&#xff0c;实验原理 k-mea…...

编程日记 2025/5/29 15:24:09

数学复习笔记 12

前言 现在做一下例题和练习题。矩阵的秩和线性相关。另外还要复盘前面高数的部分的内容。奥&#xff0c;之前矩阵的例题和练习题&#xff0c;也没有做完&#xff0c;行列式的例题和练习题也没有做完。累加起来了。以后还是得学一个知识点就做一个部分的内容&#xff0c;日拱一…...

编程日记 2025/5/24 16:28:43

Web-CSS入门

WEB前端&#xff0c;三部分&#xff1a;HTML部分、CSS部分、Javascript部分。 1.HTML部分&#xff1a;主要负责网页的结构层 2.CSS部分&#xff1a;主要负责网页的样式层 3.JS部分&#xff1a;主要负责网页的行为层 **基本概念** 层叠样式表&#xff0c;Cascading Style Sh…...

编程日记 2025/5/28 15:17:16

Qt/C++编写音视频实时通话程序/画中画/设备热插拔/支持本地摄像头和桌面

一、前言 近期有客户提需求&#xff0c;需要在嵌入式板子上和电脑之间音视频通话&#xff0c;要求用Qt开发&#xff0c;可以用第三方的编解码组件&#xff0c;能少用就尽量少用&#xff0c;以便后期移植起来方便。如果换成5年前的知识储备&#xff0c;估计会采用纯网络通信收发…...

编程日记 2025/5/29 20:12:00

Ubuntu快速安装Python3.11及多版本管理

之前文章和大家分享过&#xff0c;将会出一篇专栏&#xff08;从电脑装ubuntu系统&#xff0c;到安装ubuntu的常用基础软件&#xff1a;jdk、python、node、nginx、maven、supervisor、minio、docker、git、mysql、redis、postgresql、mq、ollama等&#xff09;&#xff0c;目前…...

编程日记 2025/6/1 8:10:21

Qt功能区：Ribbon使用

Ribbon使用 1. Ribbon功能区介绍1.1 样式 2. 基本功能区设置2.1 安装动态库&#xff08;推荐&#xff09;2.2 在MainWindow中使用Ribbon2.3 在QWidget中使用SARibbonBar2.4 创建Category和Pannel2.5 ContextCategory 上下文标签创建 2.6 ApplicationButton2.7 QuickAccessBar和…...

编程日记 2025/5/29 14:43:34

【学习心得】Jupyter 如何在conda的base环境中其他虚拟环境内核

如果你在conda的base环境运行了jupyter lab打开了一个ipynb文本&#xff0c;此时选择的内核是base虚拟环境的Python内核&#xff0c;如果我想切换成其他conda虚拟环境来运行这个文件该怎么办&#xff1f;下面我们试着还原一下问题&#xff0c;并且解决问题。 【注】 这个问题出…...

编程日记 2025/5/26 10:43:16

在微创手术中使用Kinova轻型机械臂进行多视图图像采集和3D重建

在微创手术中&#xff0c;Kinova轻型机械臂通过其灵活的运动控制和高精度的操作能力&#xff0c;支持多视图图像采集和3D重建。这种技术通过机械臂搭载的光学系统实现精准的多角度扫描&#xff0c;为医疗团队提供清晰且详细的解剖结构模型。其核心在于结合先进的传感器配置与重…...

编程日记 2025/5/29 22:50:00

[Java][Leetcode middle] 238. 除自身以外数组的乘积

第一个想法是&#xff1a; 想求出所有元素乘积&#xff0c;然后除以i对应的元素本书&#xff1b;这个想法是完全错误的&#xff1a; nums[I] 可能有0题目要求了不能用除法 第二个想法是&#xff1a; 其实写之前就知道会超时&#xff0c;但是我什么都做不到啊&#xff01; 双…...

编程日记 2025/5/27 7:02:18

【leetcode】144. 二叉树的前序遍历

给你二叉树的根节点 root &#xff0c;返回它节点值的 前序 遍历。 示例 1&#xff1a; 输入&#xff1a;root [1,null,2,3] 输出&#xff1a;[1,2,3] 解释&#xff1a; 示例 2&#xff1a; 输入&#xff1a;root [1,2,3,4,5,null,8,null,null,6,7,9] 输出&#xff1a…...

编程日记 2025/5/29 11:33:21

SpringBoot常用注解详解

文章目录 1. 前言2. 核心注解2.1 SpringBootApplication2.2 Configuration2.3 EnableAutoConfiguration2.4 ComponentScan2.5 Bean2.6 Autowired2.7 Qualifier2.8 Primary2.9 Value2.10 PropertySource2.11 ConfigurationProperties2.12 Profile 3. Web开发相关注解3.1 Control…...

编程日记 2025/5/26 11:36:08

中文分词与数据可视化02

jieba 库简介 jieba&#xff08;结巴分词&#xff09;是一个高效的中文分词工具&#xff0c;广泛用于中文自然语言处理&#xff08;NLP&#xff09;任务。它支持以下功能&#xff1a; 分词&#xff1a;将句子切分为独立的词语。 自定义词典&#xff1a;添加专业词汇或新词&am…...

编程日记 2025/5/27 15:22:02

SSH主机密钥验证失败：全面解决方案与技术手册

一、问题本质与安全机制解析 SSH(Secure Shell)的主机密钥验证是安全通信的核心机制&#xff0c;当出现"Host key verification failed"错误时&#xff0c;表明客户端检测到服务器身份异常。这种设计可有效防范中间人攻击(Man-in-the-Middle)&#xff0c;其工作原理…...

编程日记 2025/5/29 0:42:28

buuctf Crypto-鸡藕椒盐味1

1.题目&#xff1a; 公司食堂最新出了一种小吃&#xff0c;叫鸡藕椒盐味汉堡&#xff0c;售价八块钱&#xff0c;为了促销&#xff0c;上面有一个验证码&#xff0c;输入后可以再换取一个汉堡。但是问题是每个验证码几乎都有错误,而且打印的时候倒了一下。小明买到了一个汉堡&a…...

编程日记 2025/5/29 10:20:52

真题卷001——算法备赛

蓝桥杯2024年C/CB组国赛卷 1.合法密码 问题描述 小蓝正在开发自己的OJ网站。他要求用户的密码必须符合一下条件&#xff1a; 长度大于等于8小于等于16必须包含至少一个数字字符和至少一个符号字符 请计算一下字符串&#xff0c;有多少个子串可以当作合法密码。字符串为&am…...

编程日记 2025/5/27 8:22:44

基于MCP的桥梁设计规范智能解析与校审系统构建实践

引言 在腾讯云开发者社区中&#xff0c;有多种MCP工具可以用于本系统的开发和优化中&#xff0c;以下是一些潜在的应用场景&#xff1a; ‌PDF解析工具‌&#xff1a;如pdfplumber等&#xff0c;可以用于规范文件的预处理&#xff0c;提取文本和图像信息。‌自然语言处理工具…...

编程日记 2025/5/22 2:16:27

matlab与python问题解析

Python requests乱码的五种解决办法 Python requests乱码的五种解决办法_requests.get乱码-CSDN博客 requests库post请求参数data、json和files的使用 requests库post请求参数data、json和files的使用_requests post data-CSDN博客 如何在浏览器中查看POST请求提交的数据内…...

编程日记 2025/5/29 16:59:09

【分布式锁通关指南 10】源码剖析redisson之MultiLock的实现

引言 本期我们将把目光聚焦在 Redisson 中另一个颇具代表性的分布式锁实现——MultiLock。它的核心思想是&#xff1a;一次性对多个独立的 RLock 进行加锁或解锁操作&#xff0c;只有当多个锁都成功加锁时才算真正完成锁的获取&#xff0c;一旦有任何一个失败&#xff0c;整体操…...

编程日记 2025/5/29 13:11:49

MySQL 8.0 OCP 1Z0-908 131-140题

Q131.You have upgraded the MySQL binaries from 5.7.28 to 8.0.18 by using an in-place upgrade. Examine the message sequence generated during the first start of MySQL 8.0.18: 。。。[System]。。。/usx/sbin/mysqld (mysqld 8.0.18-commercial) starting as process…...

编程日记 2025/5/29 13:38:04

实战解析MCP-使用本地的Qwen-2.5模型-AI协议的未来？

文章目录 目录 文章目录 前言 一、MCP是什么&#xff1f; 1.1MCP定义 1.2工作原理 二、为什么要MCP&#xff1f; 2.1 打破碎片化的困局 2.2 实时双向通信&#xff0c;提升交互效率 2.3 提高安全性与数据隐私保护 三、MCP 与 LangChain 的区别 3.1 目标定位不同 3.…...

编程日记 2025/5/29 12:00:03

从零开始学习three.js（20）：three.js实现天气与时间动态效果（白天，黑夜，下雨，下雪）

基于Three.js的天气与时间动态效果实现 本文将通过代码解析&#xff0c;介绍如何使用Three.js实现动态天气&#xff08;下雨、下雪&#xff09;和时间&#xff08;白天、黑夜&#xff09;切换效果。完整代码基于一个交互式天气模拟项目&#xff0c;支持粒子密度、速度和环境亮…...

编程日记 2025/5/17 5:58:50

sqli-labs靶场23-28a关（过滤）

目录 less23&#xff08;--过滤&#xff09; less24&#xff08;二次注入&#xff09; less25&#xff08;or过滤&#xff09; less25a&#xff08;or过滤&#xff09; less26&#xff08;--和空格过滤报错&#xff09; less26a&#xff08;--空格过滤盲注&#xff09; …...

编程日记 2025/5/22 0:30:54

Sigmoid与Softmax：从二分类到多分类的深度解析

Sigmoid与Softmax：从二分类到多分类的深度解析 联系 函数性质：二者都是非线性函数 ，也都是指数归一化函数，可将输入值映射为0到1之间的实数 ，都能把输出转化成概率分布的形式，在神经网络中常作为激活函数使用。Softmax是Sigmoid的推广：从功能角度看，Softmax函数可视为…...

编程日记 2025/5/29 16:52:55

uni-app x正式支持鸿蒙原生应用开发

DCloud发布的HBuilderX 4.64正式版&#xff0c;支持编译uni-app x项目到鸿蒙平台&#xff0c;实现跨平台开发鸿蒙原生应用。至此&#xff0c;uni-app x 已经完成Android、iOS、鸿蒙、Web、微信小程序等主流平台全覆盖。 uni-app x&#xff0c;是下一代 uni-app&#xff0c;是一…...

编程日记 2025/5/28 22:40:30

【软件推荐——pdf2docx】

pdf2docx Open source Python library for converting PDF to DOCX. https://github.com/ArtifexSoftware/pdf2docx Install pip install pdf2docx使用 from pdf2docx import Converterpdf_file D:\my\c4611_sample_explain.pdf docx_file D:\my\c4611_sample_explain.d…...

编程日记 2025/5/27 0:13:48

HarmonyOS开发组件基础

个人简介 &#x1f468;‍&#x1f4bb;‍个人主页&#xff1a; 魔术师 &#x1f4d6;学习方向&#xff1a; 主攻前端方向&#xff0c;正逐渐往全栈发展 &#x1f6b4;个人状态&#xff1a; 研发工程师&#xff0c;现效力于政务服务网事业 &#x1f1e8;&#x1f1f3;人生格言&…...

编程日记 2025/5/29 16:46:54

JMeter 测试工具--组件--简单介绍

目录 ​编辑 一、测试计划&#xff08;Test Plan&#xff09; 二、线程组&#xff08;Thread Group&#xff09; 三、取样器&#xff08;Sampler&#xff09; 四、监听器&#xff08;Listener&#xff09; 五、逻辑控制器&#xff08;Logic Controller&#xff09; 六、断…...

编程日记 2025/5/26 9:42:38

ECPF 简介

ECPF&#xff08;Embedded CPU Function&#xff0c;嵌入式CPU功能&#xff09;是NVIDIA BlueField DPU特有的一种功能类型&#xff0c;和PF&#xff08;Physical Function&#xff0c;物理功能&#xff09;、VF&#xff08;Virtual Function&#xff0c;虚拟功能&#xff09;密…...

编程日记 2025/5/29 20:56:24

【Opencv】canny边缘检测提取中心坐标

采用opencv 对图像中的小球通过canny边缘检测的方式进行提取坐标 本文介绍了如何使用OpenCV对图像中的小球进行Canny边缘检测&#xff0c;并通过Zernike矩进行亚像素边缘检测&#xff0c;最终拟合椭圆以获取小球的精确坐标。首先&#xff0c;图像被转换为灰度图并进行高斯平滑…...

编程日记 2025/5/27 6:19:25

C#实现访问远程硬盘（附源码）

在现实场景中&#xff0c;我们经常用到远程桌面功能&#xff0c;而在某些场景下&#xff0c;我们需要使用类似的远程硬盘功能&#xff0c;这样能非常方便地操作对方电脑磁盘的目录、以及传送文件。那么&#xff0c;这样的远程硬盘功能要怎么实现了&#xff1f; 这次我们将给出…...

编程日记 2025/5/21 11:24:18

AI日报 · 2025年05月16日｜Google DeepMind推出AlphaEvolve，能自主设计高级算法的编码代理

全球AI新闻日报 日期&#xff1a;2025年5月16日 目录 OpenAI与CoreWeave签署40亿美元新协议&#xff0c;GPT-4.1模型全面推出Google DeepMind推出AlphaEvolve&#xff0c;能自主设计高级算法的编码代理Anthropic律师因Claude模型虚构法律引用被迫道歉Meta推迟旗舰AI模型&quo…...

编程日记 2025/5/29 9:39:30

TCP/IP 知识体系

TCP/IP 知识体系 一、TCP/IP 定义 全称&#xff1a;Transmission Control Protocol/Internet Protocol&#xff08;传输控制协议/网际协议&#xff09;核心概念&#xff1a; 跨网络实现信息传输的协议簇&#xff08;包含 TCP、IP、FTP、SMTP、UDP 等协议&#xff09;因 TCP 和…...

编程日记 2025/5/29 21:43:40

记一次缓存填坑省市区级联获取的操作

先说缓存是什么&#xff1f; 缓存主要是解决高并发&#xff0c;大数据场景下&#xff0c;热点数据快速访问。缓存的原则首先保证数据的准确和最终数据一致&#xff0c;其次是距离用户越近越好&#xff0c;同步越及时越好。 再说我们遇到的场景&#xff1a; 接手项目后&#…...

编程日记 2025/5/29 13:33:24

【时空图神经网络 交通】相关模型2：STSGCN | 时空同步图卷积网络 | 空间相关性，时间相关性，空间-时间异质性

注：仅学习使用~ 前情提要： 【时空图神经网络 & 交通】相关模型1：STGCN | 完全卷积结构，高效的图卷积近似，瓶颈策略 | 时间门控卷积层：GLU（Gated Linear Unit），一种特殊的非线性门控单元目录 STSGCN-2020年1.1 背景1.2 模型1.2.1 问题背景：现有模型存在的问题1.2…...

编程日记 2025/5/29 21:36:56

uniapp实现在线pdf预览以及下载

uniapp实现在线pdf预览以及下载 在线预览 遇到的问题 后端返回一个url地址&#xff0c;我需要将在在页面中渲染出来。因为在浏览器栏上我输入url地址就可以直接预览pdf文件&#xff0c;因此直接的想法是通过web-view组件直接渲染。有什么问题呢&#xff1f;在h5端能够正常渲…...

编程日记 2025/5/29 12:43:46