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

代码随想录算法训练营第四十四天 | 01背包问题理论基础、01背包问题滚动数组、416. 分割等和子集

背包问题其实有很多种,01背包是最基础也是最经典的,软工计科学生一定要掌握的。


01背包问题

代码随想录

视频讲解:带你学透0-1背包问题!| 关于背包问题,你不清楚的地方,这里都讲了!| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili

思路

        直接上动态规划五部曲

1、dp数组及其下标的含义

对于背包问题,有一种写法, 是使用二维数组,即dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少

2.确定递推公式

再回顾一下dp[i][j]的含义:从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。

那么可以有两个方向推出来dp[i][j],

  • 不放物品i:由dp[i - 1][j]推出,即背包容量为j,里面不放物品i的最大价值,此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时,物品i无法放进背包中,所以背包内的价值依然和前面相同。)
  • 放物品i:由dp[i - 1][j - weight[i]]推出,dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值,那么dp[i - 1][j - weight[i]] + value[i] (物品i的价值),就是背包放物品i得到的最大价值

所以递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3.初始化

首先从dp[i][j]的定义出发,如果背包容量j为0的话,即dp[i][0],无论是选取哪些物品,背包价值总和一定为0。

再看其他情况。

状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来,那么i为0的时候就一定要初始化。

dp[0][j],即:i为0,存放编号0的物品的时候,各个容量的背包所能存放的最大价值。

那么很明显当 j < weight[0]的时候,dp[0][j] 应该是 0,因为背包容量比编号0的物品重量还小。

当j >= weight[0]时,dp[0][j] 应该是value[0],因为背包容量放足够放编号0物品。

4.确定遍历顺序

在如下图中,可以看出,有两个遍历的维度:物品与背包重量

动态规划-背包问题3

那么问题来了,先遍历 物品还是先遍历背包重量呢?

其实都可以!! 但是先遍历物品更好理解

5.举例验证,直接看链接里的吧。

代码
def test_2_wei_bag_problem1():weight = [1, 3, 4]value = [15, 20, 30]bagweight = 4# 二维数组dp = [[0] * (bagweight + 1) for _ in range(len(weight))]# 初始化for j in range(weight[0], bagweight + 1):dp[0][j] = value[0]# weight数组的大小就是物品个数for i in range(1, len(weight)):  # 遍历物品for j in range(bagweight + 1):  # 遍历背包容量if j < weight[i]:dp[i][j] = dp[i - 1][j]else:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])print(dp[len(weight) - 1][bagweight])test_2_wei_bag_problem1()

01背包滚动数组

代码随想录

视频讲解:带你学透01背包问题(滚动数组篇) | 从此对背包问题不再迷茫!_哔哩哔哩_bilibili

 看链接吧,老是复制粘贴累了。


416.分割等和子集

本题是 01背包的应用类题目

代码随想录

视频讲解:动态规划之背包问题,这个包能装满吗?| LeetCode:416.分割等和子集_哔哩哔哩_bilibili

思路

        就是01背包的应用,背包的大小是总和的一半,遍历每一个物品,看看遍历到最后能不能装满这个背包。

代码(二维版本在链接里)
class Solution:def canPartition(self, nums: List[int]) -> bool:if sum(nums) % 2 != 0:return Falsetarget = sum(nums) // 2dp = [0] * (target + 1)for num in nums:for j in range(target, num-1, -1):dp[j] = max(dp[j], dp[j-num] + num)return dp[-1] == target

相关文章:

代码随想录算法训练营第四十四天 | 01背包问题理论基础、01背包问题滚动数组、416. 分割等和子集

背包问题其实有很多种&#xff0c;01背包是最基础也是最经典的&#xff0c;软工计科学生一定要掌握的。 01背包问题 代码随想录 视频讲解&#xff1a;带你学透0-1背包问题&#xff01;| 关于背包问题&#xff0c;你不清楚的地方&#xff0c;这里都讲了&#xff01;| 动态规划经…...

【PingPong_注册安全分析报告】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞 …...

车辆路径规划之Dubins曲线与RS曲线简述

描述 Dubins和RS曲线都是路径规划的经典算法&#xff0c;其中车辆运动学利用RS曲线居多&#xff0c;因此简单介绍Dubins并引出RS曲线。 花了点时间看了二者的论文&#xff0c;并阅读了一个开源的代码。 Dubins曲线 Dubins曲线是在满足曲率约束和规定的始端和末端的切线&#…...

PostgreSQL 和Oracle锁机制对比

PostgreSQL 和Oracle锁机制对比 PostgreSQL 和 Oracle 都是业界广泛使用的关系型数据库管理系统&#xff0c;它们在锁机制方面都有独到的设计来控制并发访问&#xff0c;确保数据的一致性和完整性。下面我们详细比较一下这两个数据库系统的锁机制。 1. 锁类型 PostgreSQL P…...

6月05日,每日信息差

第一、特斯拉在碳博会上展示了其全品类的可持续能源解决方案&#xff0c;包括首次在国内展出的超大型电化学商用储能系统 Megapack 和家庭储能系统 Powerwall。此外&#xff0c;特斯拉还展示了电动汽车三电系统的解构和电池回收技术产品 第二、2024 年第一季度&#xff0c;全球…...

MongoDB~俩大特点管道聚合和数据压缩(snappy)

场景 在MySQL中&#xff0c;通常会涉及多个表的一些操作&#xff0c;MongoDB也类似&#xff0c;有时需要将多个文档甚至是多个集合汇总到一起计算分析&#xff08;比如求和、取最大值&#xff09;并返回计算后的结果&#xff0c;这个过程被称为 聚合操作 。 根据官方文档介绍&…...

HTML+CSS+JS 动态登录表单

效果演示 实现了一个登录表单的背景动画效果,包括一个渐变背景、一个输入框和一个登录按钮。背景动画由多个不同大小和颜色的正方形组成,它们在页面上以不同的速度和方向移动。当用户成功登录后,标题会向上移动,表单会消失。 Code <!DOCTYPE html> <html lang=&q…...

统一返回响应

前言 我们为什么要设置统一返回响应 提高代码的可维护性&#xff1a;通过统一返回请求的格式&#xff0c;可以使代码更加清晰和易于维护&#xff0c;减少重复的代码&#xff0c;提高代码质量。 便于调试和测试&#xff1a;统一的返回格式使得在调试和测试时更为简单&#xff…...

大数据学习问题记录

问题记录 node1突然无法连接finalshell node1突然无法连接finalshell 今天我打开虚拟机和finalshell的时候&#xff0c;发现我的node1连接不上finalshell,但是node2、node3依旧可以链接&#xff0c;我在网上找了很多方法&#xff0c;但是是关于全部虚拟机连接不上finalshell&a…...

第N4周:中文文本分类

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 一、预备知识 中文文本分类和英文文本分类都是文本分类&#xff0c;为什么要单独拎出来个中文文本分类呢&#xff1f; 在自然语言处理&#xff08;NLP&#x…...

【kubernetes】探索k8s集群的pod控制器详解(Deployment、StatefulSet、DaemonSet、Job、CronJob)

目录 一、Pod控制器及其功用 二、pod控制器有多种类型 2.1ReplicaSet 2.1.1ReplicaSet主要三个组件组成 2.2Deployment 2.3DaemonSet 2.4StatefulSet 2.5Job 2.6Cronjob 三、Pod与控制器之间的关系 3.1Deployment 3.2SatefulSet 3.2.1StatefulSet三个组件 3.2.2为…...

直接插入排序

#include <stdio.h>void insert_sort(int arr[], int n) {int i;int j;int tmp;for (i 1; i < n; i){tmp arr[i];j i - 1;// 将要插入的元素与数组中的元素比较&#xff08;从后向前比&#xff09; while (j > 0 && arr[j] > tmp){arr[j 1] arr[…...

esp32s3 nvs 存储过程中使用malloc和free函数的一点困惑

我的项目中&#xff0c;大量使用了malloc()和free()函数&#xff0c;在使用nvs存储之前没有出现问题。 esp32厂家nvs的blob存储的例程中&#xff0c;有使用malloc()和free()&#xff0c;我参照例程写了自己的blob存储函数f&#xff0c;一开始是可以正常使用的&#xff0c;后来…...

除visio以外的几款好用流程图绘制工具

流程图绘制软件在嵌入式软件开发中扮演着重要的角色&#xff0c;它们能够帮助用户清晰、直观地展示工作流程。以下是几款流行的流程图绘制软件及其特点的详细报告&#xff1a; 思维导图MindMaster MindMaster作为一款专业的思维导图软件&#xff0c;不仅具备强大的思维导图制作…...

CentOS 7 64位 常用命令

一、系统管理命令 systemctl start firewalld.service&#xff1a;启动防火墙服务 systemctl stop firewalld.service&#xff1a;停止防火墙服务 systemctl enable firewalld.service&#xff1a;设置防火墙服务开机自启 systemctl disable firewalld.service&#xff1a;禁止…...

ChatGPT-4o抢先体验

速度很快&#xff0c;结果很智能&#xff0c;支持多模态输入输出&#xff0c;感兴趣联系作者。 windows/linux/mac 客户端下载参考&#xff1a;https://github.com/lencx/Noi...

STM32实验之USART串口发送+接受数据(二进制/HEX/文本)

涉及三个实验&#xff1a; 1.USART串口发送和接收数据 我们使用的是将串口封装成为一个Serial.c模块.其中包含了 void Serial_Init(void);//串口初始化 void Serial_SendByte(uint8_t Byte);//串口发送一个字节 void Serial_SendArray(uint8_t *Array,uint16_t Length);//…...

网关(Gateway)- 内置过滤器工厂

官方文档&#xff1a;Spring Cloud Gateway 内置过滤器工厂 AddRequestHeaderGatewayFilterFactory 为请求添加Header Header的名称及值 配置说明 server:port: 8088 spring:application:name: api-gatewaycloud:nacos:discovery:server-addr: 127.0.0.1:8847username: nacos…...

电风扇如何实现跌倒断电保护功能

电风扇作为日常生活中常用的家电产品&#xff0c;为了提升安全性能&#xff0c;在设计上通常会考虑加入跌倒断电保护功能。其中&#xff0c;光电倾倒开关是实现跌倒断电保护功能的关键组件之一。 光电倾倒开关内置红外发光二极管和光敏接收器&#xff0c;其工作原理非常巧妙。…...

编译原理总结

编译器构成 1. 前端分析部分 1.1 词法分析 确定词性&#xff0c;输出为token序列 1.2 语法分析 识别短语 1.3 语义分析 分析短语在句子中的成分 IR中间代码生成 2. 机器无关代码优化 3. 后端综合部分 目标代码生成 机器相关代码优化 4. 其他 全局信息表 异常输出...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

自然语言处理——文本分类

文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益&#xff08;IG&#xff09; 分类器设计贝叶斯理论&#xff1a;线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别&#xff0c; 有单标签多类别文本分类和多…...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...

基于江科大stm32屏幕驱动,实现OLED多级菜单(动画效果),结构体链表实现(独创源码)

引言 在嵌入式系统中&#xff0c;用户界面的设计往往直接影响到用户体验。本文将以STM32微控制器和OLED显示屏为例&#xff0c;介绍如何实现一个多级菜单系统。该系统支持用户通过按键导航菜单&#xff0c;执行相应操作&#xff0c;并提供平滑的滚动动画效果。 本文设计了一个…...