代码随想录刷题笔记 DAY 42 | 背包问题 - 二维 | 背包问题 - 一维 | 分割等和子集 No.416

news/2024/4/24 6:24:33/文章来源:https://blog.csdn.net/weixin_74895237/article/details/136503275

文章目录

    • Day 42
      • 01. 背包问题 - 二维
        • <1> 01 背包问题
        • <2> 动态规划优化
      • 02. 背包问题 - 一维
      • 03. 分割等和子集(No. 416)
        • <1> 题目
        • <2> 笔记
        • <3> 代码

Day 42

01. 背包问题 - 二维

<1> 01 背包问题

n 个物品和最多能装重量为 w 的背包,第 i 件物品的重量为 weight[i],得到的价值是 value[i],那如何将这些物品装入背包能获取最大的价值呢?

背包问题的一个很经典的 求最值 的问题,但因为其动态规划的过于的经典,很多朋友其实忽略了它的暴力解法,每一件物品只有两种状态:取或者不取,所以通过 回溯算法 将所有的情况遍历出来,可以求得最终的结果。

回溯算法示例:

public static void backtracking(int n) {if (n == weight.length - 1 && m <= w) {// 表明遍历到最终的物品res = Math.max(res, v);return;}for (int i = 0; i < 2; i++) {if (i == 0) {// 取的情况v += value[n];m += weight[n];backtracking(n + 1);v -= value[n];m -= weight[n];} else {// 不取该物品的情况backtracking(n + 1);}}
}

这样遍历完之后时间复杂度达到了 O(2n)。

<2> 动态规划优化

利用回溯算法解题的时间复杂度达到了 指数 级别,所以必须要考虑优化的方法。

因为本题的最优解收到 两个维度 的限制,一个是 背包的容量,一个是 选取的物品的重量(这个重量又被能选择哪些物品所影响),在这两个内容的限制下去求得最优的价值,所以在设计 dp 数组的时候也要同时将这两个因素考虑在内。

在设计 dp 数组的时候考虑的就是在 某个背包容量下选取某些物品 能达到的最优价值总和;那 dp[i][j] 就是从下标为 0i 的范围内任意取,放到容量为 j 的背包里,能收获的 最大价值 是多少。

这样就可以开始确定递推公式了:要紧扣两个限制条件,一个物品仅仅有两种情况:

  1. 不取这个物品,那此时价值最大的情况就是 dp[i - 1][j],也就是在 这个容量下 取得的范围限制在 0i - 1
  2. 取这个物品,但也要注意是在 这个容量下 去取的,也就是
    dp[i - 1][j - weight[i]] + value[i],时刻要记得另一个限制,也就是背包的容量。

最优解毫无疑问就是其中的最大值,也即:

dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

现在看一个具体的例子来讨论 dp 数组的初始化:

物品的重量和价值:

重量价值
物品 0115
物品 1320
物品 2430

背包的容量 4,最后形成一个三行五列的数组

初始化的关键是 dp[i] 等式右边的所有数据在遍历到 dp[i] 的时候一定是被填充过的。

比如遍历到 粉色 的节点,此时需要的是它的正上方和左上方的节点(为了保证数组下标不越界,此时的 j 必须要大于等于 weight[i] 否则这个物品就一定无法取得)。

所以要将所有没有上方或者左上方的节点全部初始化,因为依据上面的递推公式无法求出这些节点的值,也即这些节点:

dp[i][j] 就是从下标为 0i 的范围内任意取,放到容量为 j 的背包里,能收获的 最大价值 是多少

那第一 毫无疑问被初始化成 0,第一行则为能取得物品 0 的时候价值为 value[0] 否则为 0,因为此时限制只能取得物品 0,比如上面那个例子,初始化之后的结果就是:

// 遍历第一行
for (int i = 0; i < dp.length; i++) {dp[i][0] = 0;
}
// 遍历第一列
for (int i = weight[0]; i < dp[0].length; i++) {dp[i] = weight[0];
}

接下来确定遍历的顺序,因为我们的
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]) 也就是行表示选取的物品,列表示背包的容量,但其实这个递归公式也可以改写成:

dp[i][j] = Math.max(dp[i][j - 1], dp[i - weight[j]][j - 1] + value[j]) 行为背包的容量,列为选取的物品;这两个其实就对应着两种遍历顺序:先遍历物品还是先遍历背包?

其实两种都是可以的,这两种情况推出一个节点所需要的数据都在 左上角,不影响公式的推导,但因为大多数都是先遍历物品,而且在含义上也更易理解,所以平时建议写的时候先去遍历物品,对于先遍历背包的能够理解和写出代码即可。

那现在写出代码:

class Solution {public int BagProblem(int[] weight, int[] value, int bagSize) {int n = weight.length; // 物品的数量int[][] dp = new int[n][bagSize + 1];// 初始化 dp 数组for (int i = weight[0]; i < dp[0].length; i++) {dp[0][i] = value[0];}for (int i = 1; i < dp.length; i++) {for (int j = 1; j < dp[0].length; j++) {if (j >= weight[i]) {// 可以放下物品的情况dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);} else {// 不能放下物品的情况dp[i][j] = dp[i - 1][j];}}}return dp[n - 1][bagSize];}
}

02. 背包问题 - 一维

💡 相较于二维的方法,我认为一维的方法不止是在写法上,也是在性能上的一种优化。

可以观察一下上面的推导中的这一部分:

if (j >= weight[i]) {
// 可以放下物品的情况dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
} else {
// 不能放下物品的情况dp[i][j] = dp[i - 1][j];
}

当出现 else 的情况,也就是背包容量装不下该物品的时候,这时候就是 直接将上一行的值原封不动的照搬下来,所以会去考虑:能否从 weight[i] 开始遍历呢?但是由于二维数组的限制,还需要将上面那一行的剩余部分通过遍历挪下来,还是上面那个例子:

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

那既然通过二维数组无法实现,那是不是可以考虑一维数组呢?

只要我不去修改那部分的值也就相当于直接挪下来了,试一下:

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

这时候只要解决 34 的问题其实就可以得到一个可行的方法了;回顾上面的推导公式,推导出一个节点的新值其实只需要它的 左上角的节点即可,那一维数组的这个左上角在哪呢?就在 本行 嘛,为了保证左上角一定有值,遍历就需要 从后向前去遍历,遍历的终点就是 j < weight[i],这样其实就将二维数组的方法转成一维的了。

之所以一维数组能够解决问题,其本质还是递推公式的性质:推导一个节点只需要 左上角 的值。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

看一下对比的关系因为上一行的内容相当于挪到本行的,所以不需要 i - 1,这就是新得到的递归公式。

写出代码

class Solution {public int BagProblem(int[] weight, int[] value, int bagSize) {int n = weight.length; // 物品的数量int[] dp = new int[bagSize + 1];// 初始化 dp 数组for (int i = weight[0]; i < dp.length; i++) {dp[i] = value[0];}for (int i = 1; i < n; i++) {for (int j = dp.length - 1; j >= weight[i]; j--) {// 可以放下物品的情况dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}return dp[bagSize];}
}

💡 其实这个一位数组的遍历还隐藏着一个特性,如果从前向后遍历其实得到的是有 无限个 物品的情况

  • 看一下这个递推公式 dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);

  • 按照这个递推公式遍历一下物品 1 来感受一下
    外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
    推导出来的部分是这样的,即物品有无限个的情况。

03. 分割等和子集(No. 416)

题目链接

代码随想录题解

<1> 题目

给你一个 只包含正整数非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

示例 1:

输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2:

输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。

提示:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100
<2> 笔记

这道题是背包问题的一个经典的实例问题,其实一开始看到这个题的时候并没有想到往背包方向靠的思路,而是当成了组合问题去做,但是在写的时候突然想到,这不就是 找一个子集,使得它们的和等于原集合和的一半 嘛?

再继续深入的想一下,如何才能凑出这个原集合的和的一半值呢?为了好表述这里将这个值设为 target,只考虑子集的和 小于或者等于 target 的情况,这个问题就可以转化为:

从集合中的所有元素中选取元素,刨去大于 target 的那部分,它们的和的最大值能否达到 target

是不是感觉和背包问题有点像了?这个 target 就是限制最大值的指标,集合中的元素的大小(选取范围)就是限制的另一个部分,这不正是背包问题的 两个限制条件 嘛?再继续类比,这个 target,其实就是 背包的容量,集合中的元素就是物品,其重量和价值 都是 nums[i]

将其转换成背包问题去做,只需要判断最右下角的那个元素是否 等于 target 即可,否则就无法凑成。

而对于背包问题的遍历其实就是上面提到的一维和二维的情况;但是二维的情况明显更好:二维数组是从后向前遍历的,而这个最大值是在哪里出现的呢?恰好是最后一列中,所以在每次遍历完一层之后其实可以判断这个值是否达到了 target,如果出现就可以直接返回 true 而不需要继续遍历。

比如 [1,5,11,5] 在遍历到第三层的时候其实就已经得到 11 了。

这里将两种遍历方式的代码都提供出来。

<3> 代码

二维遍历方式:

class Solution {public boolean canPartition(int[] nums) {int length = nums.length; // 输入集合的长度int sum = 0; // 集合的总和int target = 0; // 集合总和的一半for (int i : nums) sum += i;if (sum % 2 != 0 || nums.length < 2) return false;target = sum / 2;int[][] dp = new int[target + 1][length];// 初始化 dp 数组for (int i = 0; i < dp.length; i++) {if (i > nums[0]) dp[i][0] = nums[0];}for (int i = 1; i < dp.length; i++) {for (int j = 1; j < dp[0].length; j++) {if (i >= nums[j]) {dp[i][j] = Math.max(dp[i][j - 1],dp[i - nums[j]][j - 1] + nums[j]);} else {dp[i][j] = dp[i][j - 1];}}}return dp[target][length - 1] == target;}
}

一维遍历方式:

class Solution {public boolean canPartition(int[] nums) {if(nums == null || nums.length == 0) return false;int n = nums.length;int sum = 0;for(int num : nums) {sum += num;}//总和为奇数,不能平分if(sum % 2 != 0) return false;int target = sum / 2;int[] dp = new int[target + 1];for(int i = 0; i < n; i++) {for(int j = target; j >= nums[i]; j--) {//物品 i 的重量是 nums[i],其价值也是 nums[i]dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}//剪枝if(dp[target] == target)return true;}return dp[target] == target;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_996673.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

SpringBoot集成ElasticSearch(ES)

ElasticSearch环境搭建 采用docker-compose搭建&#xff0c;具体配置如下&#xff1a; version: 3# 网桥es -> 方便相互通讯 networks:es:services:elasticsearch:image: registry.cn-hangzhou.aliyuncs.com/zhengqing/elasticsearch:7.14.1 # 原镜像elasticsearch:7.…

销售管理之反向与正向目标控制

在销售活动中&#xff0c;控制力是关键。但控制力其实分为两种&#xff1a;反向控制和正向控制。本文将深入探讨这两种控制方式&#xff0c;并阐述如何在销售活动中加以应用&#xff0c;以提升销售效果。 一、反向控制&#xff1a;以客户为中心&#xff0c;引导客户需求 反向控…

如何使用grafana 下JSON API访问展示接口数据

一.新增connection 点击左侧菜单栏&#xff0c;选择Add new connection 下载安装即可。 二. 增加对应url和参数 1. 添加新的数据源 2. 配置对应url 3.新建仪表盘和添加接口url和参数等

【Android】源码解析 Activity 的构成

本文是基于 Android 14 的源码解析。 当我们写 Activity 时会调用 setContentView() 方法来加载布局。现在来看看 setContentView() 方法是怎么实现的&#xff0c;源码如下所示&#xff1a; 路径&#xff1a;/frameworks/base/core/java/android/app/Activity.javapublic void…

2-web端管理界面使用rabbitmq

Web管理界面可以直接操作RabbitMQ&#xff0c;下面进行操作并记录步骤 1、添加交换器&#xff1a; Add a new exchange 中&#xff0c;Name是交换器名称&#xff0c;Type是交换器类型&#xff0c;有direce、fanout、heders、topic 4种。 这里先只填Name和选个类型&#xff0c;…

基于OpenCV的图形分析辨认05(补充)

目录 一、前言 二、实验内容 三、实验过程 一、前言 编程语言&#xff1a;Python&#xff0c;编程软件&#xff1a;vscode或pycharm&#xff0c;必备的第三方库&#xff1a;OpenCV&#xff0c;numpy&#xff0c;matplotlib&#xff0c;os等等。 关于OpenCV&#xff0c;num…

数据库系列之:什么是 SAP HANA?

数据库系列之&#xff1a;什么是 SAP HANA&#xff1f; 一、什么是 SAP HANA&#xff1f;二、什么是内存数据库&#xff1f;三、SAP HANA 有多快&#xff1f;四、SAP HANA 的十大优势五、SAP HANA 架构六、数据库设计七、数据库管理八、应用开发九、高级分析十、数据虚拟化 一、…

QT----在编译器里能够连接云端数据库,使用windeployqt打包后运行程序,链接不上云端mysql数据库

问题描述 在编译器里能够连接云端数据库&#xff0c;使用windeployqt打包后运行程序&#xff0c;链接不上云端mysql数据库&#xff0c;困扰了好几天 打包发布手机上的app还是无法连接 问题解决 打包的时候没有将这个文件放入&#xff0c;我们复制放到exe的目录即可

彻底搞清楚CUDA和cuDNN版本问题

彻底搞清楚CUDA和cuDNN版本问题 1. 缘起 我的机器上以下三条指令输出的版本不相同。 nvcc -V # 这个输出11.7 nvidia-smi # 右上角显示12.3 import torch; torch.version.cuda # 这个输出12.1我想以此为契机&#xff0c;彻底搞清楚CUDA、cuDNN和torch之间的关系。 环境&a…

Ubuntu20.04安装并配置vscode

Ubuntu20.04安装并配置vscode vscode安装miniconda安装创建虚拟python3.8环境pytorch和匹配的cuda安装 vscode安装 VSCode可以通过 Snapcraft 商店或者微软源仓库中的一个 deb 软件包来安装。 我们这里选用安装VSCode snap版&#xff0c;打开你的终端(CtrlAltT)并且运行下面的…

比较 2 名无人机驾驶员:借助分析飞得更高

近年来&#xff0c;越来越多的政府和执法机构使用无人机从空中鸟瞰。为了高效执行任务&#xff0c;无人机必须能够快速机动到预定目标。快速机动使它们能够在复杂的环境中航行&#xff0c;并高效地完成任务。成为认证的无人机驾驶员的要求因国家/地区而异&#xff0c;但都要求您…

蓝桥杯练习题——差分

1.空调 思路 1.区间同时加减 1&#xff0c;可以转换成一个差分数组两个端点的操作 2.用 p 减去 t 数组&#xff0c;得到要消除的数组 a&#xff0c;对 a 求差分数组 3.差分数组一正一负为一个操作&#xff0c;因为是把这个原数组区间加上了 1&#xff0c;单独的正负为一个操作…

解决QMYSQL driver not loaded问题

前言 之前都是在Qt5.51上开发&#xff0c;连接mysql数据库一直没有问题&#xff0c;换到5.15.2后一直报错 一查才发现\5.15.2\msvc2019_64\plugins\sqldrivers目录下没有qsqlmysql了&#xff0c;5.5.1是有的&#xff0c;5.15.2是要自己编译的。。。 下载源码 安装qt的时候没…

云服务器99元一年阿里云和腾讯云对比,明智选择!

腾讯云服务器99元一年是真的吗&#xff1f;真的&#xff0c;只是又降价了&#xff0c;现在只要61元一年&#xff0c;配置为2核2G3M轻量应用服务器&#xff0c;40GB SSD盘&#xff0c;腾讯云百科txybk.com分享腾讯云官方活动购买链接 https://curl.qcloud.com/oRMoSucP 活动打开…

鸿蒙Harmony应用开发—ArkTS声明式开发(事件独占控制)

设置组件是否独占事件&#xff0c;事件范围包括组件自带的事件和开发者自定义的点击、触摸、手势事件。 在一个窗口内&#xff0c;设置了独占控制的组件上的事件如果首先响应&#xff0c;则本次交互只允许此组件上设置的事件响应&#xff0c;窗口内其他组件上的事件不会响应。 …

新闻资讯|基于微信小程序的经济新闻资讯系统设计与实现(源码+数据库+文档)

新闻资讯小程序目录 目录 基于微信小程序的经济新闻资讯系统设计与实现 一、前言 二、系统设计 三、系统功能设计 1、用户信息管理 2 短视频信息管理 3、新闻信息管理 4、论坛信息管理 四、数据库设计 1、实体ER图 五、核心代码 六、论文参考 七、最新计算机毕设…

数学建模【主成分分析】

一、主成分分析简介 主成分分析&#xff08;Principal Component Analysis&#xff0c;PCA&#xff09;是一种降维算法&#xff0c;它能将多个指标转换为少数几个主成分&#xff0c;这些主成分是原始变量的线性组合&#xff0c;且彼此之间互不相关&#xff0c;其能反映出原始数…

python三剑客之一——Numpy

温故而知新&#xff0c;借着工作需要用到Numpy的机会重新学习一遍Numpy。 Numpy是一个运行速度非常快的数学库&#xff0c;主要用于数组计算&#xff0c;包含如下&#xff1a; 一个强大的N维数组对象ndarray【Nd&#xff08;Dimension维度&#xff09;array】 广播功能函数 整…

在maven多模块之间调用报错

错误信息为&#xff1a;不能解决maven_02_ssm项目的依赖问题&#xff0c;找不到maven_03_pojo这个jar包。 为什么找不到呢? 原因是Maven会从本地仓库找对应的jar包&#xff0c;但是本地仓库又不存在该jar包所以会报错。 在IDEA中是有maven_03_pojo这个项目&#xff0c;所以…

uniapp模仿下拉框实现文字联想功能 - uniapp输入联想(官方样式-附源码)

一、效果 废话不多说&#xff0c;上效果图&#xff1a; 在下方的&#xff1a; 在上方的&#xff1a; 二、源码 一般是个输入框&#xff0c;输入关键词&#xff0c;下拉一个搜索列表。 ElementUI有提供<el-autocomplete>&#xff0c;但uniapp官网没提供这么细&#x…