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

代码随想录算法训练营第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背包基础 &#xff08;二维数组&#xff09;思路递推公式初始化遍历顺序一维dp数组&#xff08;滚动数组&#xff09;一维数组的递推公式遍历顺序LeetCode 416. 分割等和子集思路总结01背包基础 &#xff08;二维数组&#xff09; 思路 根据动态规划五部进行分析&a…...

QT学习记录(六)类对象属性

类对象属性用来描述类对象的一些信息和当前的状态。类对象属性可以由类的编写者在编写类的时候定义&#xff0c;也可以由类的使用者在使用对象的时候定义。 由类的编写者定义 QPROPERTY()宏就是用来定义一个对象属性。 以第二行属性举例 QPROPERTY(bool enabled READ isEnabl…...

Spring Cloud Alibaba从搭建到源码完整进阶教程

微服务简介 Spring Cloud Alibaba 微服务简介 Nacos注册中心配置中心 Spring Cloud Nacos实战&#xff08;一&#xff09;- 下载和安装 Spring Cloud Nacos实战&#xff08;二&#xff09;- 服务提供者注册 Spring Cloud Nacos实战&#xff08;三&#xff09;- 服务消费者…...

Spring Cloud Nacos实战(一)- 下载和安装

Spring Cloud Alibaba Nacos下载和安装 Nacos介绍 ​ Nacos&#xff08;Naming Configuration Service&#xff09; 是一个易于使用的动态服务发现、配置和服务管理平台&#xff0c;用于构建云原生应用程序 ​ 服务发现是微服务架构中的关键组件之一。Nacos 致力于帮助您发现…...

深入理解设备像素比

文章目录参考描述像素分辨率显示分辨率图像分辨率物理分辨率分辨率单位&#xff08;仅部分&#xff09;DPIPPI设备像素比设备物理像素设备独立像素设备像素比产生放大与缩小尾声参考 项目描述关于物理像素、逻辑像素&#xff08;css像素&#xff09;、分辨率、像素比的超详细讲…...

Revisiting Distributed Synchronous SGD 带有Back-up机制的分布式同步SGD方法 论文精读

论文链接&#xff1a;Revisiting Distributed Synchronous SGD ABS 本文介绍了用于分布式机器学习的同步和异步SGDSGDSGD&#xff0c;同时指出各自的缺点&#xff1a;stragglersstragglersstragglers和stalenessstalenessstaleness。 同时为了解决同步SGDSGDSGD存在straggle…...

shiro CVE-2020-13933

0x00 前言 同CVE-2020-1957&#xff0c;补充一下笔记&#xff0c;在CVE-2020-1957的基础上进行了绕过。 影响版本&#xff1a;Apache Shiro < 1.6.0 环境搭建参考&#xff1a;shiro CVE-2020-1957 0x01 漏洞复现 CVE-2020-13933中使用%3b绕过了shiro /*的检测方式&…...

斐波那契数列(递归+迭代)

目录什么是斐波那契数列递归写法使用递归写法的缺点迭代写法(效率高)什么是斐波那契数列 斐波那契数列&#xff08;Fibonacci sequence&#xff09;&#xff0c;又称黄金分割数列&#xff0c;因数学家莱昂纳多斐波那契&#xff08;Leonardo Fibonacci&#xff09;以兔子繁殖为例…...

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. 激活网卡方法一&#xff1a;直接启动网卡&#xff08;仅限当此&#xff09;方法二&#xff1a;修改配置文件&#xff08;永久&#xff09;2. 将NAT模式改为桥接模式什么是是NAT模式&#xff1f;如何改为桥接模式&#xff1f;三、虚拟机网络连接…...

vue3学习总结1

一.vue3与vue2相比带来哪些变化&#xff1f;a.性能的提升&#xff08;包括打包大小减少&#xff0c;初次渲染的速度加快&#xff0c;更新渲染速度加快&#xff0c;内存减少&#xff09;b.源码的升级&#xff08;响应式的原理发生了变化&#xff0c;由原来的defineProperty变成了…...

SpringBoot统一功能处理

一、统一用户登录权限验证 1.1Spring拦截器 实现拦截器需要以下两步&#xff1a; 1.创建自定义拦截器&#xff0c;实现 HandlerInterceptor 接⼝的 preHandle&#xff08;执行具体方法之前的预处理&#xff09;方法。 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&#xff08;最好的智能指针&#xff09; 四、C11中新提供的智能指针 unique_ptr shared_ptr std::shared_ptr的循环引用问题…...

Seata架构篇 - AT模式

AT 模式 概述 Seata AT 模式是一种非侵入式的分布式事务解决方案&#xff0c;Seata 在内部做了对数据库操作的代理层&#xff0c;我们使用 Seata AT 模式时&#xff0c;实际上用的是 Seata 自带的数据源代理 DataSourceProxy&#xff0c;Seata 在这层代理中加入了很多逻辑&am…...

加油站会员管理小程序实战开发教程12

我们上一篇介绍了会员数据源的开发,本节我们介绍一下会员注册功能。 首先呢梳理一下会员注册的业务逻辑,如果用户是首次登录,那他肯定还没有给我们的小程序提交任何的信息。那么我们就在我的页面给他显示一个注册的按钮,如果他已经注册过了,那么就正常显示会员的信息,他…...

用腾讯云同步Obsidian笔记

介绍 之前用gitee同步OB笔记&#xff0c;同时做图床。但由于git系产品设置起来相对复杂&#xff0c;且后续可能有外链过审等问题。周五被同事小姐姐安利了用腾讯云COS&#xff0c;试了一下&#xff0c;果然不错。其主要优点如下&#xff1a; 设置简单&#xff0c;学习成本低&…...

浅析C++指针与引用,栈传递的关系

目录 前言 C 堆指针 栈指针 常量指针 指针常量 引用 常量引用 总结 前言 目前做了很多项目&#xff0c;接触到各种语言&#xff0c;基本上用什么学什么&#xff0c;语言的边际就会很模糊&#xff0c;实际上语言的设计大同小异&#xff0c;只是语言具备各自的特性区别。…...

图解LeetCode——剑指 Offer 10- II. 青蛙跳台阶问题

一、题目 一只青蛙一次可以跳上1级台阶&#xff0c;也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e97&#xff08;1000000007&#xff09;&#xff0c;如计算初始结果为&#xff1a;1000000008&#xff0c;请返回 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指…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

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

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

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...