代码随想录算法训练营第45天动态规划 背包基础 1 2、 416. 分割等和子集
文章目录
- 01背包基础 (二维数组)
- 思路
- 递推公式
- 初始化
- 遍历顺序
- 一维dp数组(滚动数组)
- 一维数组的递推公式
- 遍历顺序
- LeetCode 416. 分割等和子集
- 思路
- 总结
01背包基础 (二维数组)
思路
根据动态规划五部进行分析,先进行参数和下标的初始化
由于是背包探索我们用二维数组 创建一个 dp[i][j] 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]);
初始化
首先从dp[i][j]的定义出发,如果背包容量j为0的话,即dp[i][0],无论是选取哪些物品,背包价值总和一定为0。
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];
}
遍历顺序
在二维数组中无论是先遍历物品 后遍历背包 或者 先遍历背包后遍历物品都能够达成目的
不过在后序的一维数组中完成背包问题就固定下来了, 先遍历物品后遍历书包。
一维dp数组(滚动数组)
在使用二维数组的时候,递推公式:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上,表达式完全可以是:
dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上,不如只用一个一维数组了,只用dp[j](一维数组,也可以理解是一个滚动数组)。
一维数组的递推公式
dp[j]可以通过dp[j - weight[i]]推导出来,dp[j - weight[i]]表示容量为j -
weight[i]的背包所背的最大价值。dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包 加上
物品i的价值。(也就是容量为j的背包,放入物品i了之后的价值即:dp[j])此时dp[j]有两个选择,一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j],即不放物品i,一个是取dp[j -
weight[i]] + value[i],即放物品i,指定是取最大的,毕竟是求最大价值,
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
遍历顺序
与二维数组不同, 先物品再背包, 背包遍历要求 倒序遍历因为这样就可以保证每一个物品只放一次
for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}
LeetCode 416. 分割等和子集
思路
这里运用了 01背包的思路 ,我的做法是采用了一维数组的方式做的
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--){dp[j]= Math.max( dp[j],dp[j-nums[i]]+nums[i]);}}return dp[target] == target;}
}
总结
恢复更新了,之前在返校,临开学也没有状态就休息了一段时间
相关文章:
代码随想录算法训练营第45天动态规划 背包基础 1 2、 416. 分割等和子集
文章目录01背包基础 (二维数组)思路递推公式初始化遍历顺序一维dp数组(滚动数组)一维数组的递推公式遍历顺序LeetCode 416. 分割等和子集思路总结01背包基础 (二维数组) 思路 根据动态规划五部进行分析&a…...
QT学习记录(六)类对象属性
类对象属性用来描述类对象的一些信息和当前的状态。类对象属性可以由类的编写者在编写类的时候定义,也可以由类的使用者在使用对象的时候定义。 由类的编写者定义 QPROPERTY()宏就是用来定义一个对象属性。 以第二行属性举例 QPROPERTY(bool enabled READ isEnabl…...
Spring Cloud Alibaba从搭建到源码完整进阶教程
微服务简介 Spring Cloud Alibaba 微服务简介 Nacos注册中心配置中心 Spring Cloud Nacos实战(一)- 下载和安装 Spring Cloud Nacos实战(二)- 服务提供者注册 Spring Cloud Nacos实战(三)- 服务消费者…...
Spring Cloud Nacos实战(一)- 下载和安装
Spring Cloud Alibaba Nacos下载和安装 Nacos介绍 Nacos(Naming Configuration Service) 是一个易于使用的动态服务发现、配置和服务管理平台,用于构建云原生应用程序 服务发现是微服务架构中的关键组件之一。Nacos 致力于帮助您发现…...
深入理解设备像素比
文章目录参考描述像素分辨率显示分辨率图像分辨率物理分辨率分辨率单位(仅部分)DPIPPI设备像素比设备物理像素设备独立像素设备像素比产生放大与缩小尾声参考 项目描述关于物理像素、逻辑像素(css像素)、分辨率、像素比的超详细讲…...
Revisiting Distributed Synchronous SGD 带有Back-up机制的分布式同步SGD方法 论文精读
论文链接:Revisiting Distributed Synchronous SGD ABS 本文介绍了用于分布式机器学习的同步和异步SGDSGDSGD,同时指出各自的缺点:stragglersstragglersstragglers和stalenessstalenessstaleness。 同时为了解决同步SGDSGDSGD存在straggle…...
shiro CVE-2020-13933
0x00 前言 同CVE-2020-1957,补充一下笔记,在CVE-2020-1957的基础上进行了绕过。 影响版本:Apache Shiro < 1.6.0 环境搭建参考:shiro CVE-2020-1957 0x01 漏洞复现 CVE-2020-13933中使用%3b绕过了shiro /*的检测方式&…...
斐波那契数列(递归+迭代)
目录什么是斐波那契数列递归写法使用递归写法的缺点迭代写法(效率高)什么是斐波那契数列 斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多斐波那契(Leonardo Fibonacci)以兔子繁殖为例…...
2022黑马Redis跟学笔记.实战篇(六)
2022黑马Redis跟学笔记.实战篇 六4.7.达人探店功能4.7.1.分享探店图文1. 达人探店-发布探店笔记2. 达人探店-查看探店笔记4.7.2.点赞功能4.7.3.基于List实现点赞用户列表TOP104.7.4.基于SortedSet实现点赞排行榜4.8.关注列表4.8.1.关注列表实现原理4.8.2.添加关注1. 好友关注-关…...
Linux-VMware常用设置(时间+网络)及网络连接激活失败解决方法-基础篇②
目录一、设置时间二、网络设置1. 激活网卡方法一:直接启动网卡(仅限当此)方法二:修改配置文件(永久)2. 将NAT模式改为桥接模式什么是是NAT模式?如何改为桥接模式?三、虚拟机网络连接…...
vue3学习总结1
一.vue3与vue2相比带来哪些变化?a.性能的提升(包括打包大小减少,初次渲染的速度加快,更新渲染速度加快,内存减少)b.源码的升级(响应式的原理发生了变化,由原来的defineProperty变成了…...
SpringBoot统一功能处理
一、统一用户登录权限验证 1.1Spring拦截器 实现拦截器需要以下两步: 1.创建自定义拦截器,实现 HandlerInterceptor 接⼝的 preHandle(执行具体方法之前的预处理)方法。 2.将⾃定义拦截器加⼊ WebMvcConfigurer 的 addIntercept…...
2022年3月电子学会Python等级考试试卷(五级)答案解析
目录 一、单选题(共25题,共50分) 二、判断题(共10题,共20分) 三、编程题(共3题,共30分) 青少年软件编程(Python)等级考试试卷(五级&#...
【C++】智能指针
目录 一、先来看一下什么是智能指针 二、 auto_ptr 1、C98版本 2、C11的auto_ptr 三、boost 库中的智能指针 1. scoped_ptr 2、shared_ptr(最好的智能指针) 四、C11中新提供的智能指针 unique_ptr shared_ptr std::shared_ptr的循环引用问题…...
Seata架构篇 - AT模式
AT 模式 概述 Seata AT 模式是一种非侵入式的分布式事务解决方案,Seata 在内部做了对数据库操作的代理层,我们使用 Seata AT 模式时,实际上用的是 Seata 自带的数据源代理 DataSourceProxy,Seata 在这层代理中加入了很多逻辑&am…...
加油站会员管理小程序实战开发教程12
我们上一篇介绍了会员数据源的开发,本节我们介绍一下会员注册功能。 首先呢梳理一下会员注册的业务逻辑,如果用户是首次登录,那他肯定还没有给我们的小程序提交任何的信息。那么我们就在我的页面给他显示一个注册的按钮,如果他已经注册过了,那么就正常显示会员的信息,他…...
用腾讯云同步Obsidian笔记
介绍 之前用gitee同步OB笔记,同时做图床。但由于git系产品设置起来相对复杂,且后续可能有外链过审等问题。周五被同事小姐姐安利了用腾讯云COS,试了一下,果然不错。其主要优点如下: 设置简单,学习成本低&…...
浅析C++指针与引用,栈传递的关系
目录 前言 C 堆指针 栈指针 常量指针 指针常量 引用 常量引用 总结 前言 目前做了很多项目,接触到各种语言,基本上用什么学什么,语言的边际就会很模糊,实际上语言的设计大同小异,只是语言具备各自的特性区别。…...
图解LeetCode——剑指 Offer 10- II. 青蛙跳台阶问题
一、题目 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e97(1000000007),如计算初始结果为:1000000008,请返回 1。 二、示例 2.1>…...
【Linux】用户分类+权限管理+umask+粘滞位说明
目录 1.用户分类 su指令 2.认识Linux权限 2.1 文件访问者的分类 2.2 文件类型和访问权限 a. 文件类型 file指令 b. 访问权限 2.3 文件权值的表示方法 a. 字母表示法 b. 八进制表示法 3.如何修改文件访问者的权限及相关指令 1. chmod指令 2. chown指令 3. chgrp指…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
学习一下用鸿蒙DevEco Studio HarmonyOS5实现百度地图
在鸿蒙(HarmonyOS5)中集成百度地图,可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API,可以构建跨设备的定位、导航和地图展示功能。 1. 鸿蒙环境准备 开发工具:下载安装 De…...
