代码随想录算法训练营第42天| 背包问题、416. 分割等和子集
01 背包
题目描述:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。
二维dp数组01背包:
- 确定dp数组以及下标的含义
对于背包问题,有一种写法, 是使用二维数组,即dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。
-
确定递推公式
再回顾一下dp[i][j]的含义:从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。那么可以有两个方向推出来dp[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]是由其左侧和左上方数据推导出来的,因此要初始化dp[i][0]列和dp[0][j]行的数据,背包重量为0时,背包内物品的价值为零,dp[i][0]列为0。dp[0][i]行的数据,当背包容量j≥wieght[j]时,dp[0][j]=value[j],其他时候为零。 -
遍历顺序
先遍历还是weight还是value都可以。
#include<iostream>
#include<vector>
using namespace std;void slove(int m, int n){vector<int> wight;vector<int> value;int x;for (int i = 0; i < m;i++){cin>>x;wight.push_back(x);}for (int i = 0; i < m;i++){cin>>x;value.push_back(x);}vector<vector<int>> dp(m,vector<int>(n+1,0));for(int j = 0; j <= n; j++){if(j>=wight[0]){dp[0][j] = value[0];}}for (int i = 1; i < m; i++){for (int j = 1; j <= n; j++){if(j < wight[i]){dp[i][j] = dp[i-1][j];} else {dp[i][j] = max(dp[i-1][j], dp[i-1][j-wight[i]]+value[i]);}}}cout << dp[m-1][n] <<endl;
}int main(){int m,n;cin>>m>>n;slove(m,n);
}
一维dp数组01背包:
对于背包问题其实状态都是可以压缩的。
在使用二维数组的时候,递推公式: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数组的遍历要为倒序遍历,倒序遍历是为了保证物品i只被放入一次!。但如果一旦正序遍历了,那么物品0就会被重复加入多次!
#include<iostream>
#include<vector>
using namespace std;void slove(int m, int n){vector<int> wight;vector<int> value;int x;for (int i = 0; i < m;i++){cin>>x;wight.push_back(x);}for (int i = 0; i < m;i++){cin>>x;value.push_back(x);}vector<int> dp(n+1,0);for (int i = 0; i < m; i++){for (int j = n; j >= 0; j--){if(j >= wight[i]){dp[j] = max(dp[j], dp[j-wight[i]]+value[i]);}}}cout << dp[n] <<endl;
}int main(){int m,n;cin>>m>>n;slove(m,n);
}
416. 分割等和子集
题目链接:分割等和子集
题目描述:给你一个 只包含正整数 的 非空 数组
nums
。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
解题思想:
要明确本题中我们要使用的是01背包,因为元素我们只能用一次。
回归主题:首先,本题要求集合里能否出现总和为 sum / 2 的子集。
那么来一一对应一下本题,看看背包问题如何来解决。
只有确定了如下四点,才能把01背包问题套到本题上来。
- 背包的体积为sum / 2
- 背包要放入的商品(集合里的元素)重量为 元素的数值,价值也为元素的数值
- 背包如果正好装满,说明找到了总和为 sum / 2 的子集。
- 背包中每一个元素是不可重复放入。
后面的解题思路就和01背包问题相同
class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;int target = 0;for (int num : nums)sum += num;if (sum % 2)return false;elsetarget = sum / 2;vector<int> dp(target + 1, 0);for (int i = 0; i < nums.size(); i++) {for (int j = target; j >= nums[i]; j--) {dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}if (dp[target] == target) {return true;}return false;}
};
相关文章:
代码随想录算法训练营第42天| 背包问题、416. 分割等和子集
01 背包 题目描述:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。 二维dp数组01背包: 确定dp数组以及下标的含义 …...
Node.js安装及环境配置指南
Node.js安装及环境配置指南 一、Node.js的安装 安装Node.js之前,首先需要确保你的电脑已经安装了合适的编译器和开发环境。Node.js是一个开源的、跨平台的JavaScript运行环境,它使得JavaScript可以在服务器端运行。 下载Node.js安装包 访问Node.js的…...
【Java基础】面试题汇总
Java基础面试题1. JVM vs JDK vs JRE 2. 什么是字节码?采用字节码的好处是什么?3. 为什么说 Java 语言“编译与解释并存”?4. AOT 有什么优点?为什么不全部使用 AOT 呢?5. Java 和 C 的区别?6. Java 中的基本数据类型࿱…...
数据库事务的超级详细讲解,包括事务特性、事务隔离级别、MVCC(多版本并发控制)
数据库事务: 主要有事务特性,事务的隔离级别,MVCC。 事务特性: 事务(Transaction)是指作为单个逻辑工作单元执行的一系列操作,这些操作要么全部成功执行,要么全部不执行ÿ…...
鸿蒙Lottie动画-实现控制动画的播放、暂停、倍速播放、播放顺序
介绍 本示例展示了lottie对动画的操作功能。引入Lottie模块,实现控制动画的播放、暂停、倍速播放、播放顺序、播放到指定帧停止或从指定帧开始播放、侦听事件等功能,动画资源路径必须是json格式。 效果预览 使用说明: 进入页面默认开始201…...
C++面试100问与自动驾驶100问
C的学习和面试其实是非常的不友好的,首先C的学习内容非常的多,其次C的面试不单单面试C的知识点,还有它的“七大姑八大姨”(计算机网络、数据结构、算法、计算机组成原理、操作系统、编译、xxx的底层实现 and so on)。 …...
加速 Redis 操作:掌握管道技术提升性能与效率
Redis 管道技术是一种用于优化 Redis 命令执行效率的机制。在传统的 Redis 操作中,每次向 Redis 服务器发送一个命令,都需要等待命令执行完成并返回结果,这样会导致频繁的网络通信和服务器端的命令执行开销,降低系统的性能和吞吐量…...
深入浅出 -- 系统架构之分布式系统底层的一致性
在分布式领域里,一致性成为了炙手可热的名词,缓存、数据库、消息中间件、文件系统、业务系统……,各类分布式场景中都有它的身影,因此,想要更好的理解分布式系统,必须要理解“一致性”这个概念。 其实关于…...
idea Springboot 电影推荐系统LayUI框架开发协同过滤算法web结构java编程计算机网页
一、源码特点 springboot 电影推荐系统是一套完善的完整信息系统,结合mvc框架和LayUI框架完成本系统springboot dao bean 采用协同过滤算法进行推荐 ,对理解JSP java编程开发语言有帮助系统采用springboot框架(MVC模式开发)&…...
xss【2】
1.xss钓鱼 钓鱼攻击利用页面,fish.php黑客钓鱼获取到账号密码存储的位置 xss进行键盘记录 2.xss常规防范 3.xss验证payload XSS(跨站攻击)_details/open/ontoggle-CSDN博客...
时序分解 | Matlab实现GSWOA-VMD改进鲸鱼优化算法优化变分模态分解时间序列信号分解
时序分解 | Matlab实现GWO-CEEMDAN基于灰狼算法优化CEEMDAN时间序列信号分解 目录 时序分解 | Matlab实现GWO-CEEMDAN基于灰狼算法优化CEEMDAN时间序列信号分解效果一览基本介绍程序设计参考资料 效果一览 基本介绍 Matlab实现GSWOA-VMD改进鲸鱼优化算法优化变分模态分解时间序…...
css- 4
1.浮动 1. 浮动最初用于实现文字环绕效果 2. 现在,浮动是主流的布局方式之一 1.1元素浮动之后的特点 元素浮动之后,称为浮动元素,具有如下特点: 1. 浮动元素脱离文档流 2. 多个浮动的元素会水平排列,一行放不下自动换…...
22.括号生成
题目描述 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例 1: 输入:n 3 输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”] 示例 2: 输入…...
JAVA八股--redis
JAVA八股--redis 如何保证Redis和数据库数据一致性redisson实现的分布式锁的主从一致性Redis脑裂现象及解决方案介绍I/O多路复用模型undo log 和 redo log(没掌握MyISAM 和 InnoDB 有什么区别? 如何保证Redis和数据库数据一致性 关于异步通知中消息队列…...
[图像处理] MFC载入图片并绘制ROI矩形
上一篇: [图像处理] MFC载入图片并进行二值化处理和灰度处理及其效果显示 文章目录 前言完整代码重要代码效果 前言 上一篇实现了MFC通过Picture控件载入图片。 这一篇实现ROI功能的第一部分,在Picture控件中,通过鼠标拖拽画出一个矩形。 完…...
Godot 4 教程《勇者传说》依赖注入 学习笔记(0):环境配置
文章目录 前言相关地址环境配置初始化环境配置文件夹结构代码结构代码运行 资源文件导入像素风格窗口环境设置背景设置,Tileap使用自动TileMap 人物场景动画节点添加站立节点添加移动动画添加 通过依赖注入获取Godot的全局属性项目声明 当前项目逻辑讲解角色下降添加代码位置问…...
强行让Java和Go对比一波[持续更新]
概述 很多Java开发如果想转Golang的话,比较让Java开发蛋疼的第一是语法,第二是一些思想和设计哲学的Gap,所以我这儿强行整理一波Java和Golang的对比,但是由于GO和Java在很多方面都有不同的设计,所以这些对比的项可以更…...
理解七层网络协议
osi体系结构 上三路(管数据) 应用层 通过http等,把传输的格式,数据打包 处理网络应用。直接为端用户服务,提供各类应用过程的接口和用户接口。例如:HTTP、Tenlent、FTP、SMTP、NFS等。基于TCP的FTP、HTTP…...
网络协议——HTTP协议
目录 编辑 一,HTTP协议基本认识 二,认识URL 三,http协议的格式 1,发送格式 2,回应格式 四,服务端代码 五,http报文细节 1,Post与Get方法 2,Content_lenth 3&…...
八股面试——数据库——索引
索引的概念 B树的概念: 索引的作用 聚簇索引与非聚簇索引 聚簇索引就是主键值,在B树上,通过主键大小(数据在B树叶子节点按主键顺序排序)寻找对应的叶子节点,叶子节点保存的一整条记录。 非聚簇索引&#x…...
【二分查找】Leetcode 二分查找
题目解析 二分查找在数组有序可以使用,也可以在数组无序的时候使用(只要数组中的一些规律适用于二分即可) 704. 二分查找 算法讲解 当left > right的时候,我们循环结束,但是当left和right缩成一个点的时候&#x…...
Python+Vuecil笔记
Nginx 进入目录: C:\nginx-1.20.2\nginx-1.20.2 start nginx 开始 nginx -s stop 停止 nginx -s quit 退出CSS 通过标签去写css 循环展示数据 JS 点击时执行事件 Django 配置media 在seetings里面修改 STATIC_URL /static/ MEDIA_URL /upload/ MEDIA_ROOT os.pat…...
C语言关于随机数知识点的总结
在C语言中,随机数的生成通常依赖于特定的库函数,最常用的是 <stdlib.h> 头文件中的 rand() 函数。以下是对随机数知识点的总结、举例和分析: 随机数知识点总结 1.随机数种子:rand() 函数生成的随机数是伪随机数࿰…...
网络应用层和传输层
网络中有很多协议这些协议的不同导致了分层这一现象,不同层的主要功能不一样。 应用层:应用程序。数据具体如何使用 传输层:关注起点和终点 网络层:关注路径规划 数据链路层:关注相邻节点的转发 物理层࿱…...
Vue3:优化-从响应式数据中获取纯数据
一、情景说明 我们知道,Vue3中,创建变量时,常用ref、reactive来包裹,这样,这个变量就是响应式数据 然而,有时候,我们只需要纯数据 例如,我们在调用后端接口的时候,我们只…...
C#.手术麻醉系统源码 手麻系统如何与医院信息系统进行集成?
C#.手术麻醉系统源码 手麻系统如何与医院信息系统进行集成? 手术麻醉系统与医院信息系统的集成是一个关键步骤,它有助于实现信息的共享和流程的协同,从而提高医疗服务的效率和质量。手麻系统与lis、his、pacs等系统的对接是医院信息化建设的重…...
学习CSS Flexbox 玩flexboxfroggy flexboxfroggy1-24关详解
欢迎来到Flexbox Froggy,这是一个通过编写CSS代码来帮助Froggy和朋友的游戏! justify-content 和 align-items 是两个用于控制 CSS Flexbox 布局的属性。 justify-content:该属性用于控制 Flexbox 容器中子项目在主轴(水平方向)…...
springboot项目如何配置跨域?
在Spring Boot项目中配置跨域(CORS,Cross-Origin Resource Sharing)主要是为了允许来自不同源(不同的协议、域名或端口)的前端应用能够访问后端API。Spring Boot提供了多种方式来配置跨域支持。 1. 使用CrossOrigin注…...
实现第一个动态链接库 游戏插件 成功在主程序中运行 dll 中定义的类
devc 5.11编译环境 dll编译环境设置参考 Dev c C语言实现第一个 dll 动态链接库 创建与调用-CSDN博客 插件 DLL代码和主程序代码如下 注意 dll 代码中的class 类名需要 和主程序 相同 其中使用了函数指针和强制类型转换 函数指针教程参考 以动态库链接库 .dll 探索结构体…...
算法第三十九天-验证二叉树的前序序列化
验证二叉树的前序序列化 题目要求 解题思路 方法一:栈 栈的思路是「自底向上」的想法。下面要结合本题是「前序遍历」这个重要特点。 我们知道「前序遍历」是按照「根节点-左子树-右子树」的顺序遍历的,只有当根节点的所有左子树遍历完成之后…...
iis停止单个网站/平台推广方式方法是什么
最近要用到XML文件,网络上也有很多处理XML文件的方法,但最终还是选择了TinyXML,因为它的小巧。在网络了查找了很多相关的资料,记录下来。 TinyXML文件的基础使用比较简单,网络上也有很多相关的例子和教程,在…...
小程序嵌套wordpress/百度竞价点击软件
程序员必备简捷开发辅助工具总结 写在前面: 工欲善其事必先利其器,拥有简捷的开发辅助工具能大大提高我们程序猿的开发效率。Melo刚到学校就给大家总结了一些常用的辅助开发的工具,希望大家能喜欢,闲话不多说,马上开…...
吴中区做网站/软文广告投放平台
├1.初识JVM.mp4├2.JVM运行机制.mp4├3.常用JVM配置参数.mp4├4.GC算法与种类.mp4├5.GC参数.mp4├6.类装载器.mp4├7.性能监控工具.mp4├8.Java堆分析.mp4├9.锁.mp4├10.Class文件结构.mp4├11.字节码执行.mp4├│ ├JVM的垃圾回收机制详解和调优.docx│ ├深入Java核心 J…...
招远网站/海外网站推广的公司
Visual Studio 2015开了个小玩笑...
长沙移动网站建设/目前最火的推广平台
深入浅出Pandas读书笔记 C7 Pandas数据合并与对比 7.1 数据追加 df.append The frame.append method is deprecated and will be removed from pandas in a future version. Use pandas.concat instead. 7.2 数据链接 pd.concat 7.2.1 基本语法 pd.concat(objs, axis0, jo…...
vue网站开发/爱站网关键词搜索
我们设计的HTML电子邮件中如果含有图片,在一些客户端中默认无法显示图片,这种情况是ISP(邮件服务商)为保护邮箱安全设置的一种策略。下面列出几个收到的电子邮件显示的示例:示例1图示例2图示例3图这3个电子邮件的设计都非常具有视觉吸引力&am…...