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

动态规划之背包问题:组合优化中的经典NP挑战

背包问题概念:

背包问题是一种经典的组合优化的NP问题,在计算机科学、运筹学等领域有着广泛的应用。

问题可以简单的描述为:

假设有一个容量为C的背包和n个物品,每个物品i都有重量w[i]和价值v[i]。目标是选择一些物品放入背包,使得放入背包的物品总价值最大,同时背包中物品的总重量不能超过背包的容量。

 

 这里先简单介绍两种背包问题:

1.01背包:也就是你物品的个数是1个,你拿了就剩0个,没拿就剩1个

2.完全背包:物品个数无数个,可以拿0/1/2/3/4至无穷多个

背包也可以分两种:1.背包不需要装满。2.背包必须装满

这样两两组合就有4种问题

其实背包问题还有很多种情况,个数有2/3/4/5等等,每个在X2(不必装满||必须装满)

这里重在了解01背包和完全背包问题(其他可能更多出现在竞赛中)

01背包问题是所有问题的基础(基本上所有的背包问题都衍生于01背包)

以牛客网例题为例(leetcode没有较好的入门例题)

题目解析: 

第1小问:背包不必装满问题

第2小问:背包必装满问题

建议画一个表格,而且最好上面标号,就有点像我们之间处理初始化那里一样,多加一行多加一列,有利于我们后面填表

算法原理 :

其实这里的背包问题就是一个线性dp问题,也就是你挑物品时可以从左往右依次选还是不选

类似于我们之前讲解线性dp问题一样去分析即可

1.状态表示:经验+题目要求

经验:以i位置为结尾巴拉巴拉

题目要求:dp[i]:表示以i位置为结尾(从前i个物品中)所有的选法中价值最大的

我们可以发现这个状态表示推导不出来状态转移方程,因为我们在考虑第i个物品的时候,需要考虑这个能不能放进背包,我连总的重量和剩余容量都不知道

所以我们需要改一下状态表示,既然一维表示不了,那我们就二维

dp[i][j]:从前i个物品挑选,总体积不超过j,所有选法中,能挑选出来的最大价值

为什么这里是不超过?因为我们做第一小问,问题是不需要装满

2.状态转移方程:以最近的一步状况,划分情况

1.不选i物品,不选的话是不是最大价值就在i-1前,回归我们的状态表示

dp[i-1][j]:从前i-1个物品挑选,总体积不超过j,所有选法中,能挑选出来的最大价值 

那这种选法中dp[i][j]=dp[i-1][j]

2.选i物品,选的时候是不是要考虑能不能装进背包,所以我们需要判断背包剩余容量

剩余容量就是j-v[i]

如果剩余容量小于0,那这个i物品肯定是不能选的

如果剩余容量大于等于0,这个i物品就可以选,怎么选,回归状态表示

是不是你自身的价值加上i-1的最大价值

所以综上,最大价值就是这两种选法中最大的那个

第2小问讲解:

这里只需要稍加修改一下状态表示即可

原: dp[i][j]:从前i个物品挑选,总体积不超过j,所有选法中,能挑选出来的最大价值

现:dp[i][j]:从前i个物品挑选,总体积正好等于j,所有选法中,能挑选出来的最大价值

基本是一样的,但我们需要特别注意:我们用dp[i][j]=-1,表示没有这种情况,就是所有的选法无法凑到刚好总体积等于j的情况

那为什么不等于0呢?因为如果等于0,我们就无法区分dp[i][j]=0时表示什么情况,我们之前做第一问的时候就有初始化为0,为了区分这两种情况,我们把凑不出总体积为j的情况设为-1

第一种情况不选i物品,可以不用判断dp[i-1][j]!=-1,因为我不选i物品,dp[i-1][j]都等于-1,那证明你凑不出来,那dp[i][j]也凑不出来,所以这时候的dp[i][j]=dp[i-1][j];

第二种情况,选i物品,就必须要判断dp[i-1][j-v[i]] :也就是你必须要判断你前面的必须要凑出来j-v[i]的体积,因为你dp[i][j]这个位置选i物品要加体积v[i]的,所以你前面要能凑出来,这时候在加上v[i]的体积就刚刚好

初始化:明确第一行第一列表示啥,第一行我从0个物品中选还是不选凑出体积为0/1/2/3

第一列我选不选0/1/2/3/4物品,凑0体积,那就说明都不选,价值就是0,为了方便,我们只要创建dp表的时候初始化第一行为-1即可

后面的都和第一小问一模一样了

 

优化 :

第一种方法:滚动数组的方法,我们可以发现我们的状态转移方程仅仅需要两行的数组

也就是我们在填这一行的数据时,仅仅需要上一行的数据

例如我们在填写第一行数据时,仅仅需要第0行的数据,那我们填第2行时,就可以把第0行滚动下来充当第2行

 

如果你还觉得两行数组很麻烦,当然也可以用一行数组,

但需要注意你的填表顺序要从右往左

如果你是左往右,你填表的时候需要借助左上角的值,那左往右就是覆盖,填右边的时候就出错

这里运用的原理就是覆盖,你的数组原来是有数据的,也就是上一行的数据,你填这一行时就可以用到这个数据,注意填表从右往左就行(因为你只有一行数组) 

相关文章:

动态规划之背包问题:组合优化中的经典NP挑战

背包问题概念: 背包问题是一种经典的组合优化的NP问题,在计算机科学、运筹学等领域有着广泛的应用。 问题可以简单的描述为: 假设有一个容量为C的背包和n个物品,每个物品i都有重量w[i]和价值v[i]。目标是选择一些物品放入背包&…...

JavaScript 基础

JS概念 JS基础概念 JS是一种运行在客户端(浏览器)的编程语言, 实现人机交换结果 作用: 网页特效表单验证数据交互服务端编程(node.js) JS的组成 ECMAScript—javaScript语言基础Web APIs—(DOM: 页面文档对象模型)(BOM: 浏览器对象模型) JS书写 位置 内部: 写到< /body…...

Vibe Coding: 优点与缺点

如果你最近在开发圈子里,你很可能听说过这个新趋势"vibe coding"(氛围编程)。 我只能说我对此感受复杂。以下是原因。 优势 在构建新项目时,靠着氛围编程达到成功感觉很自由!但对于遗留代码来说情况就不同了,尽管也不是不可能。 实时反馈和快速迭代 Cursor(…...

小动物听力评价系统基本原理简析

小动物听力评价系统是用于评估小动物听力功能的专业设备&#xff0c;以下从系统组成、工作原理、评价方法等方面为你介绍&#xff1a; 一 系统组成 声音刺激模块&#xff1a;能产生不同频率、强度和类型的声音信号&#xff0c;如纯音、啭音、短声等&#xff0c;以刺激小动物的听…...

spark缓存-persist

存储级别指定 persist&#xff1a;可以通过传入 StorageLevel 参数来指定不同的持久化级别。常见的持久化级别有&#xff1a; MEMORY_ONLY&#xff1a;将 RDD 以 Java 对象的形式存储在 JVM 的内存中。若内存不足&#xff0c;部分分区将不会被缓存&#xff0c;需要时会重新计算…...

树初步 #1(插排串联 - 辽宁省2024CCPC)

树初步 数的基础内容可以看看树基础 - OI Wiki里面的讲解&#xff0c;对一些操作的基础概念介绍的很清楚&#xff1b; 下面直接来看例题&#xff1a; 插排串联 - 辽宁省CCPC 题目大意 给定一个n1个节点的有根数&#xff1b; 根节点&#xff08;0号&#xff09;是插座&…...

CDGP重点知识梳理(82个)

目 录 考点分布 考试要求 第一章 数据管理-5%...

shell脚本基础详细学习(更新中)

shell简单介绍 Shell不仅仅是充当用户与UNIX或者localhost交互的角色&#xff0c;还可以作为一种程序设计 语言来使用。通过Shell编程&#xff0c;可以实现许多非常实用的功能&#xff0c;提高系统管理的自动化水平。 如果有一系列经常需要使用的命令&#xff0c;把它存储在一…...

记录一下学习kafka的使用以及思路

下面这是kafka的依赖 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-stream-kafka</artifactId></dependency> 我在学习的时候直接导入是没有导入成功的&#xff0c;我猜测大概的原因是我本…...

AT9880B北斗单模卫星定位SOC芯片

AT9880B是一款高性能北斗单模卫星导航接收机SOC单芯片&#xff0c;芯片集成射频前端和数字基带、北斗多频卫星信号处理引擎、电源管理功能。芯片支持接收中国北斗二号和北斗三号&#xff0c;支持接收B1I、B1C、B2I、B3I、B2a和 B2b等频点信号。 主要特性&#xff1a; 支持北斗…...

李沐《动手学深度学习》 | 多层感知机

文章目录 感知机模型《深度学习入门》的解释训练感知机损失函数的选择感知机的收敛定理&#xff1a;什么时候能够停下来&#xff0c;是不是真的可以停下来感知机的不足 多层感知模型案例引入隐藏层从线性到非线性单隐藏层-单分类案例多隐藏层 激活函数softmax函数溢出的问题 多…...

vue数据可视化开发常用库

一、常用数据可视化库 1. ECharts 特点&#xff1a;功能强大&#xff0c;支持多种图表类型&#xff0c;社区活跃。适用场景&#xff1a;复杂图表、大数据量、3D 可视化。安装&#xff1a;npm install echarts示例&#xff1a;<template><div ref"chart" c…...

CAN转ModbusTCP网关:破解电池生产线设备协议壁垒,实现全链路智能互联

在电池生产的现代工艺中&#xff0c;自动化和信息化水平的提高是提升产能、保障品质与安全的关键。CAN 协议作为一种广泛应用于汽车、工业控制等领域的串行通信协议&#xff0c;它以其高可靠性和强实时性而受到企业的青睐。而在众多工业通讯协议中&#xff0c;ModbusTCP作为一种…...

更新 / 安装 Nvidia Driver 驱动 - Ubuntu - 2

如果按更新 / 安装 Nvidia Driver 驱动 - Ubuntu-CSDN博客中的步骤操作后问题依旧&#xff0c;则查看过程中的提示信息。 如果发现有“Use sudo apt autoremove to remove them.”&#xff0c;则执行&#xff1a; #sudo apt autoremove #nvidia-smi...

技术分享 | 如何在2k0300(LoongArch架构)处理器上跑通qt开发流程

近期迅为售后团队反馈&#xff0c;许多用户咨询&#xff1a;2K0300处理器采用了LA264处理器核&#xff0c;若要在该处理器上运行Qt程序&#xff0c;由于架构发生了变化&#xff0c;其使用方法是否仍与ARM平台保持一致&#xff1f; 单纯回答‘一致’或‘不一致’缺乏说服力&…...

ubuntu 24.04 error: cannot uninstall blinker 1.7.0, record file not found. hint

最近在打python3.12的镜像&#xff0c;安装browser-gym的核心库&#xff0c;编译一个使用browswer agents的环境&#xff0c;然后出现了下面的问题&#xff1a; error: cannot uninstall blinker 1.7.0, record file not found. hint: the package was installed by debian.系…...

学习记录:DAY28

DispatcherController 功能完善与接口文档编写 前言 没什么动力说废话了。 今天来完善 DispatcherController 的功能&#xff0c;然后写写接口文档。 日程 早上&#xff1a;本来只有早八&#xff0c;但是早上摸鱼了&#xff0c;罪过罪过。下午&#xff1a;把 DispatcherContro…...

C# 的异步任务中, 如何暂停, 继续,停止任务

namespace taskTest {using System;using System.Threading;using System.Threading.Tasks;public class MyService{private Task? workTask;private readonly SemaphoreSlim semaphore new SemaphoreSlim(0, 1); // 初始为 0&#xff0c;Start() 启动时手动放行private read…...

html object标签介绍(用于嵌入外部资源通用标签)(已不推荐使用deprecated,建议使用img、video、audio标签)

文章目录 HTML <object> 标签详解基本语法与核心属性关键属性解析1. **data**2. **type**3. **width & height**4. **name** 嵌入不同类型的资源1. **嵌入图像**2. **嵌入音频**3. **嵌入视频**4. **嵌入 PDF** 参数传递与回退内容**参数&#xff08;<param>&a…...

专题练习1

优化: 找101-200的质数: 开发验证码: 解密数字 抽奖 优化 彩票...

Uniapp编写微信小程序,使用canvas进行绘图

一、canvas文档&#xff1a; https://developer.mozilla.org/zh-CN/docs/Web/API/Canvas_API/Tutorial 二、数据绘制&#xff08;单位是像素&#xff09;&#xff1a; 1、绘制文本&#xff1a; 文字的长度超过设置的最大宽度&#xff0c;文字会缩在一起 ① 填充文本&#xf…...

Java高频基础面试题

Java高频基础面试题 Java基础 Java的特点是什么&#xff1f; 面向对象平台无关性&#xff08;“一次编写&#xff0c;到处运行”&#xff09;支持多线程自动内存管理&#xff08;垃圾回收&#xff09;安全性丰富的类库 JDK、JRE和JVM的区别 JDK (Java Development Kit): Java…...

U9C-SQL-采购订单视图

U9C-SQL-采购订单视图 SELECTpo.ID,CONVERT ( VARCHAR ( 10 ), po.CreatedOn, 23 ) AS 签订日期,org.Name AS 甲方,po.DocNo AS 单号,item.Code AS 料号,item.Name AS 品名,item.SPECS AS 规格,item.DescFlexField_PrivateDescSeg1 AS 图号,item.DescFlexField_PrivateDescSeg2…...

HTML字符串转换为React元素实现

HTML字符串安全转换为React元素的实现 一、背景介绍 介绍HTML字符串在Web开发中的常见场景。说明React中直接使用HTML字符串的局限性。提出将HTML字符串转换为React元素的需求。 二、首先必备的两个npm库&#xff1a;html-react-parser和dompurify 导入&#xff1a; pnpm i…...

全局异常未能正确捕获到对应的异常

自定义Validation验证器遇到的问题 抛出的异常没有能被指定的TaskValidException.class方法拦截到。故写这个原因 全局异常拦截只能拦截相同的异常。只能通过解析转入自定义的异常。自定义的异常继承的异常要是一家子的。如TaskValidException和ValidationException。这样就能在…...

LeetCode 解题思路 47(最长回文子串、最长公共子序列)

解题思路&#xff1a; dp 数组的含义&#xff1a; dp[i][j] 是否为回文子串。递推公式&#xff1a; dp[i][j] s.charAt(i) s.charAt(j) && dp[i 1][j - 1]。dp 数组初始化&#xff1a; 单字符 dp[i][i] true&#xff0c;双字符 dp[i][i 1] s.charAt(i) s.charA…...

P11369 [Ynoi2024] 弥留之国的爱丽丝(操作分块,DAG可达性trick)

真的神仙题。感觉学到了很多。 题意&#xff1a; 给你一张 n n n 个结点 m m m 条边的有向图&#xff0c;点编号为 1 , 2 , … , n 1,2,\dots,n 1,2,…,n。每条边的颜色为黑色或白色。一开始所有 m m m 条边都是黑色的。 你需要进行 q q q 次操作&#xff0c;有两种操作…...

NAT穿越

概述 IPSec协商是通过IKE完成--->ISAKMP协议完成--->由UDP封装&#xff0c;源目端口均为500。 NAT--->NAPT&#xff0c;同时转换IP和端口信息。 对端设备会查验收到的数据报文中的源IP和源端口&#xff0c;其中源IP可以设定为NAT转换后的IP&#xff0c;但是源端口无法…...

不黑文化艺术学社首席艺术家孙溟㠭浅析“雪渔派”

孙溟㠭浅析“雪渔派” 何震 字主臣 &#xff0c;长卿&#xff0c;号雪渔&#xff0c;安徽婺源&#xff08;今江西&#xff09;人&#xff0c;是明代著名的篆刻家和书法家&#xff0c;与文彭独树一帜&#xff0c;实现书法与刀法的统一。 云中白鹤 笑谭间气吐霓虹 边款 其篆刻吸…...

【Linux操作系统】第一弹——Linux基础篇

文章目录 &#x1f4a1; 一. Linux的基本常识&#x1fa94; 1.1 linux网络连接三种方式&#x1fa94;1.2 虚拟机的克隆&#x1fa94;1.3 虚拟机的快照&#x1fa94;1.4 虚拟机的迁移和删除&#x1fa94;1.5 vmtools工具 &#x1f4a1;二. Linux的目录结构&#x1fa94;2.1 Linu…...

“ES7+ React/Redux/React-Native snippets“常用快捷前缀

请注意&#xff0c;这是一个常用的列表&#xff0c;不是扩展提供的所有前缀。最完整和最新的列表请参考扩展的官方文档或在 VS Code 中查看扩展的详情页面。 React (通常用于 .js, .jsx, .ts, .tsx): rfce: React Functional Component with Export Defaultrafce: React Arro…...

selenium替代----playwright

安装 好处特点&#xff1a;这个东西不像selenium需要固定版本的驱动 pip config set global.index-url https://mirrors.aliyun.com/pypi/simplepip install --upgrade pippip install playwright playwright installplaywright install ffmpeg (处理音视频的)验证&#x…...

2025年社交APP安全防御指南:抵御DDoS与CC攻击的实战策略

2025年&#xff0c;社交APP的用户规模与业务复杂度持续增长&#xff0c;但随之而来的DDoS与CC攻击也愈发隐蔽和智能化。攻击者通过AI伪造用户行为、劫持物联网设备&#xff0c;甚至利用区块链漏洞发起混合攻击&#xff0c;对平台稳定性与用户数据安全构成严峻挑战。本文将结合最…...

PHP会话技术

第十六章-PHP会话技术 PHP会话技术是构建动态、个性化Web应用的核心机制之一&#xff0c;它通过跟踪用户在网站上的连续操作状态&#xff0c;实现了网页间的数据持久化交互。无论是电商平台的购物车信息保存、社交媒体的用户登录状态维持&#xff0c;还是表单数据的跨页面传递…...

QT聊天项目DAY10

1.封装redis操作类 头文件 #ifndef REDISMANAGE_H #define REDISMANAGE_H#include "Singletion.h" #include "GlobalHead.h"class RedisManage : public Singletion<RedisManage> {friend class Singletion<RedisManage>; public:~RedisMana…...

5.0.5 变换(旋转、缩放、扭曲)

WPF变换可以产生特殊效果,如平移、旋转、扭曲。 变换类 描述TranslateTransform沿着X轴和Y轴平移ScaleTransform 沿着定义的中心点缩放RotateTransform沿着定义的中心点旋转SkewTransform 扭曲元素MatrixTransfrom提供3x3矩阵,用于定义一个自定义变换 1…...

matlab转python

1 matlab2python开源程序 https://blog.csdn.net/qq_43426078/article/details/123384265 2 网址 转换网址&#xff1a;https://app.codeconvert.ai/code-converter?inputLangMatlab&outputLangPython 文件比较网址&#xff1a;https://www.diffchecker.com/text-comp…...

什么是直播美颜SDK?跨平台安卓、iOS美颜SDK开发实战详解

时下&#xff0c;尤其在社交、娱乐、电商等应用场景中&#xff0c;一个流畅且效果自然的美颜功能往往能直接影响用户的留存率和平台的营收。要实现这些效果&#xff0c;美颜SDK是核心工具。那么&#xff0c;什么是直播美颜SDK&#xff1f;它的功能有哪些&#xff1f;如何进行跨…...

大尺寸PCB如何重塑通信与新能源产业格局

在5G通信基站与新能源电站的机房内&#xff0c;一块块面积超过600mm600mm的PCB板正悄然推动着技术革命。作为电子设备的核心载体&#xff0c;大尺寸PCB凭借其高密度集成与复杂工艺&#xff0c;成为通信、能源等领域的“隐形功臣”。以猎板PCB为代表的厂商&#xff0c;凭借宽幅曝…...

JavaSE核心知识点02面向对象编程02-04(包和导入)

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 JavaSE核心知识点02面向对象编程02-04&#…...

【漫话机器学习系列】249.Word2Vec自然语言训练模型

【自然语言处理】用 Word2Vec 将词语映射到向量空间详解 一、背景介绍 在自然语言处理&#xff08;NLP&#xff09;领域&#xff0c;我们常常需要将文本信息转化为机器能够理解和处理的形式。传统的方法&#xff0c;如 one-hot编码&#xff0c;虽然简单&#xff0c;但存在严重…...

CSS transition过渡属性

transition 是 CSS 中用于创建平滑动画效果的属性&#xff0c;它允许元素在两个状态之间平滑过渡&#xff0c;而不是立即改变。通过定义过渡的属性、持续时间和速度曲线&#xff0c;你可以实现丰富的交互体验&#xff0c;如悬停效果、状态切换动画等。 核心作用 平滑过渡&…...

U9C对接飞书审批流完整过程

U9C虽然很强大&#xff0c;但是移动办公和审批流功能并不好用&#xff0c;为了弥补U9C这种不足&#xff0c;很多的企业在使用U9C的同时再开通钉钉、飞书、企业微信这种OA管理系统&#xff0c;两套系统并行使用&#xff0c;就需要考虑U9C和OA系统数据同步的问题&#xff0c;最简…...

阿里云 SLS 多云日志接入最佳实践:链路、成本与高可用性优化

作者&#xff1a;裘文成&#xff08;翊韬&#xff09; 摘要 随着企业全球化业务的扩展&#xff0c;如何高效、经济且可靠地将分布在海外各地的应用与基础设施日志统一采集至阿里云日志服务 (SLS) 进行分析与监控&#xff0c;已成为关键挑战。 本文聚焦于阿里云高性能日志采集…...

从0开始学习大模型--Day04--大模型的框架以及基本元素

Agent框架与策略分析 计划与执行&#xff08;planning-and-Execute&#xff09; 该框架侧重于先规划一系列的行动&#xff0c;然后执行。这个框架可以使大模型能够先综合考虑任务的多个方面&#xff0c;然后按照计划进行行动&#xff0c;比较适合应用在较复杂的项目管理中或者…...

FPGA实战项目2———多协议通信控制器

1. 多协议通信控制器模块 (multi_protocol_controller) 简要介绍 这是整个设计的顶层模块,承担着整合各个子模块的重要任务,是整个系统的核心枢纽。它负责协调 UART、SPI、I2C 等不同通信协议模块以及 DMA 模块的工作,同时处理不同时钟域之间的信号交互,确保各个模块能够…...

strings.Builder 使用详解

目录 1. 官方包 2. 支持版本 3. 官方说明 官方示例 方法 func (b *Builder) Cap() int func (b *Builder) Grow(n int) func (b *Builder) Len() int func (b *Builder) Reset() func (b *Builder) String() string func (b *Builder) Write(p []byte) (int, error)…...

数巅智能携手北京昇腾创新中心深耕行业大模型应用

当前&#xff0c;AI技术正在加速向各行业深度渗透,成为驱动产业转型和社会经济发展的重要引擎。构建开放协作的AI应用生态体系、推动技术和应用深度融合&#xff0c;已成为行业发展的重要趋势。 近日&#xff0c;数巅智能与北京昇腾人工智能计算中心&#xff08;北京昇腾创新中…...

【嵌入式系统设计师(软考中级)】第二章:嵌入式系统硬件基础知识——⑤电源及电路设计

文章目录 7. 嵌入式系统电源分类及管理7.1 嵌入式系统电源分类7.2 电源管理技术7.3 电源完整性设计 8. 电子电路设计8.1 电子电路设计基础知识8.1.1 电子电路设计原理8.1.2 电子电路设计方法及步骤8.1.3 电子电路可靠性设计 8.2 PCB设计基础知识8.2.1 PCB设计原理8.2.2 PCB设计…...

排序算法-希尔排序

希尔排序是插入排序的改进版&#xff0c;通过将原始数组分成多个子序列进行间隔插入排序&#xff0c;逐步缩小间隔直至为1&#xff0c;最终完成整体排序。它也被称为缩小增量排序。 希尔排序步骤 选择增量序列&#xff08;Gap Sequence&#xff09;&#xff1a;确定一个递减的…...