当前位置: 首页 > 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;提供高可用、可…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;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个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; 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条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

优选算法第十二讲:队列 + 宽搜 优先级队列

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

ui框架-文件列表展示

ui框架-文件列表展示 介绍 UI框架的文件列表展示组件&#xff0c;可以展示文件夹&#xff0c;支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项&#xff0c;适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...

TCP/IP 网络编程 | 服务端 客户端的封装

设计模式 文章目录 设计模式一、socket.h 接口&#xff08;interface&#xff09;二、socket.cpp 实现&#xff08;implementation&#xff09;三、server.cpp 使用封装&#xff08;main 函数&#xff09;四、client.cpp 使用封装&#xff08;main 函数&#xff09;五、退出方法…...