代码随想录算法训练营第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指…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
