当前位置: 首页 > 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. 其他 全局信息表 异常输出...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

背包问题双雄:01 背包与完全背包详解(Java 实现)

一、背包问题概述 背包问题是动态规划领域的经典问题&#xff0c;其核心在于如何在有限容量的背包中选择物品&#xff0c;使得总价值最大化。根据物品选择规则的不同&#xff0c;主要分为两类&#xff1a; 01 背包&#xff1a;每件物品最多选 1 次&#xff08;选或不选&#…...

[特殊字符] Spring Boot底层原理深度解析与高级面试题精析

一、Spring Boot底层原理详解 Spring Boot的核心设计哲学是约定优于配置和自动装配&#xff0c;通过简化传统Spring应用的初始化和配置流程&#xff0c;显著提升开发效率。其底层原理可拆解为以下核心机制&#xff1a; 自动装配&#xff08;Auto-Configuration&#xff09; 核…...

比较数据迁移后MySQL数据库和ClickHouse数据仓库中的表

设计一个MySQL数据库和Clickhouse数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

SFTrack:面向警务无人机的自适应多目标跟踪算法——突破小尺度高速运动目标的追踪瓶颈

【导读】 本文针对无人机&#xff08;UAV&#xff09;视频中目标尺寸小、运动快导致的多目标跟踪难题&#xff0c;提出一种更简单高效的方法。核心创新在于从低置信度检测启动跟踪&#xff08;贴合无人机场景特性&#xff09;&#xff0c;并改进传统外观匹配算法以关联此类检测…...

Linux信号保存与处理机制详解

Linux信号的保存与处理涉及多个关键机制&#xff0c;以下是详细的总结&#xff1a; 1. 信号的保存 进程描述符&#xff08;task_struct&#xff09;&#xff1a;每个进程的PCB中包含信号相关信息。 pending信号集&#xff1a;记录已到达但未处理的信号&#xff08;未决信号&a…...