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

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

背包问题

题目链接:背包问题

文档讲解:代码随想录/背包问题

视频讲解:视频讲解-背包问题

状态:已完成(1遍)

解题过程 

这几天属实是有点分身乏术了,先直接看题解AC了,二刷的时候再来补上自己的思路和尝试吧。

看完代码随想录之后的想法 

用动态规划五部曲:

  1. 确定dp数组以及下标的含义:dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少;
  2. 确定递推公式:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
  3. 代码初始化如下:

    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];
    }
  4. 确定遍历顺序:先遍历物品再遍历背包;
  5. 举例推导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遍)

解题过程  

 看完代码随想录之后的想法 

用动态规划五部曲:

  1. 确定dp数组以及下标的含义:dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j]
  2. 确定递推公式:
    dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  3. 代码初始化如下:假设物品价值都大于0,初始化时都为0就可以了

  4. 确定遍历顺序:

    倒序遍历是为了保证物品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

    所以从后往前循环,每次取得状态不会和之前取得状态重合,这样每种物品就只取一次了。

  5. 举例推导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遍)

解题过程  

看完代码随想录之后的想法 

用动态规划五部曲:

  1. 确定dp数组以及下标的含义:dp[j] 表示: 容量为j的背包,所背的物品价值最大可以为dp[j];
  2. 确定递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  3. dp数组如何初始化:本题题目中 只包含正整数的非空数组,所以非0下标的元素初始化为0就可以了;
  4. 确定遍历顺序:如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!
  5. 举例推导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. 分割等和子集

背包问题 题目链接&#xff1a;背包问题 文档讲解&#xff1a;代码随想录/背包问题 视频讲解&#xff1a;视频讲解-背包问题 状态&#xff1a;已完成&#xff08;1遍&#xff09; 解题过程 这几天属实是有点分身乏术了&#xff0c;先直接看题解AC了&#xff0c;二刷的时候再…...

最新一站式AI创作中文系统网站源码+系统部署+支持GPT对话、Midjourney绘画、Suno音乐、GPT-4o文档分析等大模型

一、系统简介 本文将介绍最新的一站式AI创作中文系统&#xff08;集成ChatGPTMidjourneySunoStable Diffusion&#xff09;——星河易创AI系统&#xff0c;该系统基于ChatGPT的核心技术&#xff0c;融合了自然语言问答、绘画、音乐、文档分享、图片识别等创作功能&#xff0c;…...

C# 语言类型(二)—预定义类型之字符串及字符类型简述

总目录 C# 语法总目录 参考链接&#xff1a; C#语法系列:C# 语言类型(一)—预定义类型值之数值类型 C#语法系列:C# 语言类型(二)—预定义类型之字符串及字符类型简述 C#语法系列:C# 语言类型(三)—数组/枚举类型/结构体 C#语法系列:C# 语言类型(四)—传递参数及其修饰符 C#语法…...

微信小程序canvas画图使用百分比适配不同机型屏幕达到任何屏幕比例皆可!完美适配任何机型!指定canvas尺寸适配亦可!保证全网唯一完美

错误代码示例&#xff1a; // 在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默认安装路径&#xff1a; 配置文件路径&#xff1a;/usr/local/bin/redisconfig gcc安装位置 /opt/rhredis启动&#xff1a; 在/usr/local/bin目录下输入redis-server redisconfig/redis.confredis-cli -p 6379redis性能测试命令 red…...

如何编辑pdf文件内容?编辑技巧大揭秘,秒变办公达人!

如何编辑pdf文件内容&#xff1f;在数字化办公日益普及的今天&#xff0c;PDF文件因其跨平台、格式稳定的特点&#xff0c;成为我们日常工作和学习中不可或缺的一部分。然而&#xff0c;PDF文件的编辑却常常令人头疼&#xff0c;许多人面对需要修改内容的PDF文件时感到无从下手…...

Linux Shell Script 编写入门

Linux Shell 脚本是一种强大的工具&#xff0c;能够帮助用户自动化任务、简化系统管理以及提高工作效率。本文将带您全面了解如何编写 Linux Shell 脚本&#xff0c;并介绍一些常见的脚本编写技巧和注意事项。 目录 什么是 Linux ShellShell 脚本的基本结构常用 Shell 命令变…...

不是从APP store下载的APP在mac上一直提示有损坏,打不开怎么办?

1.点击设置 2.安全与隐私 3.通用看看允许从以下位置下载的APP是否有任何来源 4.如果没有&#xff0c;mac桌面点击&#x1f50d;输入终端或Terminal 命令行输入下述代码&#xff1a; sudo spctl --master-disable 5.回车&#xff0c;输入mac开机密码。注意&#xff1a;此时密…...

ubuntu22.04部署docker版zlmediakit和源码运行wvp-GB28181-pro

1 运行zlmediakit 1. 修改zlmediakit配置文件 先用run命令运行zlmediakit&#xff0c;将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表的增删改查初阶(上篇)

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

Spring Boot 集成 zxing 生成条形码与二维码

前面我们知道了怎么通过 使用 zxing 生成二维码以及条形码&#xff0c; 由于我们现在都是 web 端的项目了&#xff0c;那么我们看下怎么使用 Spring Boot 集成然后返回给前端展示&#xff1a; 工程源码 对应的工程源码我放到了这里&#xff1a;github源码路径&#xff0c;点击…...

C# 编程基础:注释、变量、常量、数据类型和自定义类型

C# 是一种功能强大的面向对象编程语言&#xff0c;它提供了丰富的特性来帮助开发者编写清晰、高效的代码。本文将介绍C#中的注释、变量、常量、基本数据类型以及如何创建和使用自定义类型。 注释 注释用于解释代码的目的&#xff0c;它们不会被程序执行。 单行注释使用 //。…...

网络原理-三

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

使用Ollama搭建一个免费的聊天机器人

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

计算机网络之快重传和快恢复以及TCP连接与释放的握手

快重传和快恢复 快重传可以让发送方尽早得知丢失消息&#xff0c; 当发送消息M1,M2&#xff0c;M3,M4,M5后,假如消息M2丢失&#xff0c;那么按照算法会发送对M2报文前一个报文M1的重复确认&#xff08;M1正常接受到&#xff0c;已经发送了确认),然后之后收到M4,M5,也会发送两…...

vue 引用第三方库 Swpier轮播图

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

RabbitMQ-直连交换机(direct)使用方法

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

942. 增减字符串匹配 - 力扣

1. 题目 由范围 [0,n] 内所有整数组成的 n 1 个整数的排列序列可以表示为长度为 n 的字符串 s &#xff0c;其中: 如果 perm[i] < perm[i 1] &#xff0c;那么 s[i] I 如果 perm[i] > perm[i 1] &#xff0c;那么 s[i] D 给定一个字符串 s &#xff0c;重构排列 pe…...

2024华为OD机试真题-机器人搬砖-C++(C卷D卷)

题目描述 机器人搬砖,一共有N堆砖存放在N个不同的仓库中,第i堆砖中有bricks[i]块砖头, 要求在8小时内搬完。机器人每小时能搬砖的数量取决于有多少能量格, 机器人一个小时中只能在一个仓库中搬砖,机器人的能量格每小时补充一次且能量格只在这一个小时有效,为使得机器人损…...

【DevOps】深入了解RabbitMQ:AMQP协议基础、消息队列工作原理和应用场景

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

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...