代码随想录算法训练营第四十四天| 背包问题、背包问题之滚动数组、416. 分割等和子集
背包问题
题目链接:背包问题
文档讲解:代码随想录/背包问题
视频讲解:视频讲解-背包问题
状态:已完成(1遍)
解题过程
这几天属实是有点分身乏术了,先直接看题解AC了,二刷的时候再来补上自己的思路和尝试吧。
看完代码随想录之后的想法
用动态规划五部曲:
- 确定dp数组以及下标的含义:dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少;
- 确定递推公式:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
-
代码初始化如下:
for (int j = 0 ; j < weight[0]; j++) { // 当然这一步,如果把dp数组预先初始化为0了,这一步就可以省略,但很多同学应该没有想清楚这一点。dp[0][j] = 0; } // 正序遍历 for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0]; }
- 确定遍历顺序:先遍历物品再遍历背包;
- 举例推导dp数组:
讲解代码如下:
function testWeightBagProblem (weight, value, size) {// 定义 dp 数组const len = weight.length,dp = Array(len).fill().map(() => Array(size + 1).fill(0));// 初始化for(let j = weight[0]; j <= size; j++) {dp[0][j] = value[0];}// weight 数组的长度len 就是物品个数for(let i = 1; i < len; i++) { // 遍历物品for(let j = 0; j <= size; j++) { // 遍历背包容量if(j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}console.table(dp)return dp[len - 1][size];
}function test () {console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
}test();
背包问题之滚动数组
题目链接:背包问题之滚动数组
文档讲解:代码随想录/背包问题之滚动数组
视频讲解:视频讲解-背包问题之滚动数组
状态:已完成(1遍)
解题过程
看完代码随想录之后的想法
用动态规划五部曲:
- 确定dp数组以及下标的含义:dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j];
- 确定递推公式:
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
-
代码初始化如下:假设物品价值都大于0,初始化时都为0就可以了
- 确定遍历顺序:
倒序遍历是为了保证物品i只被放入一次!。但如果一旦正序遍历了,那么物品0就会被重复加入多次!
举一个例子:物品0的重量weight[0] = 1,价值value[0] = 15
如果正序遍历
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此时dp[2]就已经是30了,意味着物品0,被放入了两次,所以不能正序遍历。
为什么倒序遍历,就可以保证物品只放入一次呢?
倒序就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15 (dp数组已经都初始化为0)
dp[1] = dp[1 - weight[0]] + value[0] = 15
所以从后往前循环,每次取得状态不会和之前取得状态重合,这样每种物品就只取一次了。
- 举例推导dp数组
讲解代码如下:
function testWeightBagProblem(wight, value, size) {const len = wight.length, dp = Array(size + 1).fill(0);for(let i = 1; i <= len; i++) {for(let j = size; j >= wight[i - 1]; j--) {dp[j] = Math.max(dp[j], value[i - 1] + dp[j - wight[i - 1]]);}}return dp[size];
}function test () {console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
}test();
416. 分割等和子集
题目链接:416. 分割等和子集
文档讲解:代码随想录/分割等和子集
视频讲解:视频讲解-分割等和子集
状态:已完成(1遍)
解题过程
看完代码随想录之后的想法
用动态规划五部曲:
- 确定dp数组以及下标的含义:dp[j] 表示: 容量为j的背包,所背的物品价值最大可以为dp[j];
- 确定递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
- dp数组如何初始化:本题题目中 只包含正整数的非空数组,所以非0下标的元素初始化为0就可以了;
- 确定遍历顺序:如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!
- 举例推导dp数组:
按照这个递推公式我们来推导一下,dp数组应该是如下的数列: 10 15 30 。
讲解代码如下:
var canPartition = function(nums) {const sum = (nums.reduce((p, v) => p + v));if (sum & 1) return false;const dp = Array(sum / 2 + 1).fill(0);for(let i = 0; i < nums.length; i++) {for(let j = sum / 2; j >= nums[i]; j--) {dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);if (dp[j] === sum / 2) {return true;}}}return dp[sum / 2] === sum / 2;
};
相关文章:
代码随想录算法训练营第四十四天| 背包问题、背包问题之滚动数组、416. 分割等和子集
背包问题 题目链接:背包问题 文档讲解:代码随想录/背包问题 视频讲解:视频讲解-背包问题 状态:已完成(1遍) 解题过程 这几天属实是有点分身乏术了,先直接看题解AC了,二刷的时候再…...

最新一站式AI创作中文系统网站源码+系统部署+支持GPT对话、Midjourney绘画、Suno音乐、GPT-4o文档分析等大模型
一、系统简介 本文将介绍最新的一站式AI创作中文系统(集成ChatGPTMidjourneySunoStable Diffusion)——星河易创AI系统,该系统基于ChatGPT的核心技术,融合了自然语言问答、绘画、音乐、文档分享、图片识别等创作功能,…...
C# 语言类型(二)—预定义类型之字符串及字符类型简述
总目录 C# 语法总目录 参考链接: C#语法系列:C# 语言类型(一)—预定义类型值之数值类型 C#语法系列:C# 语言类型(二)—预定义类型之字符串及字符类型简述 C#语法系列:C# 语言类型(三)—数组/枚举类型/结构体 C#语法系列:C# 语言类型(四)—传递参数及其修饰符 C#语法…...
微信小程序canvas画图使用百分比适配不同机型屏幕达到任何屏幕比例皆可!完美适配任何机型!指定canvas尺寸适配亦可!保证全网唯一完美
错误代码示例: // 在onLoad中调用 const that this wx.getSystemInfo({success: function (res) {console.log(res)that.setData({model: res.model,screen_width: res.windowWidth/375,screen_height: res.windowHeight})} }) 我看到网上很多使用上面这种代码去…...

Redis-02
redis安装包位置 /opt/redis-7.2.5 redis默认安装路径: 配置文件路径:/usr/local/bin/redisconfig gcc安装位置 /opt/rhredis启动: 在/usr/local/bin目录下输入redis-server redisconfig/redis.confredis-cli -p 6379redis性能测试命令 red…...

如何编辑pdf文件内容?编辑技巧大揭秘,秒变办公达人!
如何编辑pdf文件内容?在数字化办公日益普及的今天,PDF文件因其跨平台、格式稳定的特点,成为我们日常工作和学习中不可或缺的一部分。然而,PDF文件的编辑却常常令人头疼,许多人面对需要修改内容的PDF文件时感到无从下手…...
Linux Shell Script 编写入门
Linux Shell 脚本是一种强大的工具,能够帮助用户自动化任务、简化系统管理以及提高工作效率。本文将带您全面了解如何编写 Linux Shell 脚本,并介绍一些常见的脚本编写技巧和注意事项。 目录 什么是 Linux ShellShell 脚本的基本结构常用 Shell 命令变…...

不是从APP store下载的APP在mac上一直提示有损坏,打不开怎么办?
1.点击设置 2.安全与隐私 3.通用看看允许从以下位置下载的APP是否有任何来源 4.如果没有,mac桌面点击🔍输入终端或Terminal 命令行输入下述代码: sudo spctl --master-disable 5.回车,输入mac开机密码。注意:此时密…...
ubuntu22.04部署docker版zlmediakit和源码运行wvp-GB28181-pro
1 运行zlmediakit 1. 修改zlmediakit配置文件 先用run命令运行zlmediakit,将zlmediakit的配置文件拷贝出来 docker run -d -p 1935:1935 -p 8080:80 -p 8554:554 \ -p 10000:10000 -p 10000:10000/udp -p 8000:8000/udp \ --name zlmediakit \ zlmediakit/zlmedi…...

MySQL表的增删改查初阶(上篇)
本篇会加入个人的所谓鱼式疯言 ❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言 而是理解过并总结出来通俗易懂的大白话, 小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的. 🤭🤭🤭可能说的不是那么严谨.但小编初心是能让更多人…...

Spring Boot 集成 zxing 生成条形码与二维码
前面我们知道了怎么通过 使用 zxing 生成二维码以及条形码, 由于我们现在都是 web 端的项目了,那么我们看下怎么使用 Spring Boot 集成然后返回给前端展示: 工程源码 对应的工程源码我放到了这里:github源码路径,点击…...
C# 编程基础:注释、变量、常量、数据类型和自定义类型
C# 是一种功能强大的面向对象编程语言,它提供了丰富的特性来帮助开发者编写清晰、高效的代码。本文将介绍C#中的注释、变量、常量、基本数据类型以及如何创建和使用自定义类型。 注释 注释用于解释代码的目的,它们不会被程序执行。 单行注释使用 //。…...

网络原理-三
一、连接管理 建立连接,断开连接 建立连接,TCP有连接的. 客户端执行 socket new Socket(SeverIP,severPort); -> 这个操作就是在建立连接. 上述只是调用socket api,真正建立连接的过程,实在操作系统内核完成的. 内核是怎样完成上述的 " 建立连接 "过程的…...

使用Ollama搭建一个免费的聊天机器人
0 概述 Ollama是一个能在本机运行大语言模型的软件,它提供命令行和API的交互方式,对于需要考虑数据隐私的情景,可以方便的使用Ollama部署大语言模型,并在此基础上开发RAG等应用,而无需调用OpenAI等开放API。Ollama基本…...

计算机网络之快重传和快恢复以及TCP连接与释放的握手
快重传和快恢复 快重传可以让发送方尽早得知丢失消息, 当发送消息M1,M2,M3,M4,M5后,假如消息M2丢失,那么按照算法会发送对M2报文前一个报文M1的重复确认(M1正常接受到,已经发送了确认),然后之后收到M4,M5,也会发送两…...

vue 引用第三方库 Swpier轮播图
本文全程干货,没有废话 1.使用 npm 安装 swiper,使用 save 保存到 packjson 中 npm install --save swiper 2、把 swiper看成是第三方库或者是组件,然后按照,引用,挂载组件,使用组件三步法。 3、在 script…...

RabbitMQ-直连交换机(direct)使用方法
RabbitMQ-默认读、写方式介绍 RabbitMQ-发布/订阅模式 目录 1、概述 2、直连交换机 3、多重绑定 4、具体代码实现 4.1 生产者部分 4.2 消费者部分 5、运行代码 6、总结 1、概述 直连交换机,可以实现类似路由的功能,消息从交换机发送到哪个队列…...

942. 增减字符串匹配 - 力扣
1. 题目 由范围 [0,n] 内所有整数组成的 n 1 个整数的排列序列可以表示为长度为 n 的字符串 s ,其中: 如果 perm[i] < perm[i 1] ,那么 s[i] I 如果 perm[i] > perm[i 1] ,那么 s[i] D 给定一个字符串 s ,重构排列 pe…...
2024华为OD机试真题-机器人搬砖-C++(C卷D卷)
题目描述 机器人搬砖,一共有N堆砖存放在N个不同的仓库中,第i堆砖中有bricks[i]块砖头, 要求在8小时内搬完。机器人每小时能搬砖的数量取决于有多少能量格, 机器人一个小时中只能在一个仓库中搬砖,机器人的能量格每小时补充一次且能量格只在这一个小时有效,为使得机器人损…...

【DevOps】深入了解RabbitMQ:AMQP协议基础、消息队列工作原理和应用场景
目录 一、核心功能 二、优势 三、核心概念 四、工作原理 五、交换机类型 六、消息确认 七、持久性和可靠性 八、插件和扩展 九、集群和镜像队列 十、客户端库 十一、管理界面 十二、应用场景 RabbitMQ是一个基于AMQP协议的消息队列中间件,提供高可用、可…...

Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...

优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

ui框架-文件列表展示
ui框架-文件列表展示 介绍 UI框架的文件列表展示组件,可以展示文件夹,支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项,适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...
TCP/IP 网络编程 | 服务端 客户端的封装
设计模式 文章目录 设计模式一、socket.h 接口(interface)二、socket.cpp 实现(implementation)三、server.cpp 使用封装(main 函数)四、client.cpp 使用封装(main 函数)五、退出方法…...