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

代码随想录算法训练营第四十一天 | 01背包问题-二维数组滚动数组,416. 分割等和子集

一、参考资料

01背包问题 二维

https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html

视频讲解:https://www.bilibili.com/video/BV1cg411g7Y6

01背包问题 一维

https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html

视频讲解:https://www.bilibili.com/video/BV1BU4y177kY

分割等和子集

本题是 01背包的应用类题目

https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html

视频讲解:https://www.bilibili.com/video/BV1rt4y1N7jE

二、动态规划:01背包理论基础

背包问题:

01背包-二维数组 完整C++测试代码!
void test_2_wei_bag_problem1() {vector<int> weight = {1, 3, 4};vector<int> value = {15, 20, 30};int bagweight = 4;// 二维数组vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));// 初始化for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];}// weight数组的大小 就是物品个数for(int i = 1; i < weight.size(); i++) { // 遍历物品for(int j = 0; j <= bagweight; j++) { // 遍历背包容量if (j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}cout << dp[weight.size() - 1][bagweight] << endl;
}int main() {test_2_wei_bag_problem1();
}

Tip1:关于二维遍历的顺序,先遍历背包重量还是先遍历物品都可以,影响的是一个是先生成行再生成下一行的某一个位置的值,另一个是先生成列再生成下一列某一个位置的值。

Tip2:初始化需要注意!背包重量为0所对应的行或者列应该全部初始化为0,编号为0的物品所对应的行或列的初始化需要根据当前背包所能承受的最大重量,与当前物品的重量相比,能放下就初始化为当前物品的value。

Tip3:双层for循环,内层是正序或倒序遍历均可以,这是因为二维数组的行和列的数值是相互独立不受影响的。以物品为行,重量为列举例,下一行装物品的dp[i][j]与dp[i-1][j]是完全独立的值,每一个新的行i都会根据历史信息更新,因此不受遍历顺序的影响。

01背包-一维数组 完整C++测试代码!(滚动数组)
void test_1_wei_bag_problem() {vector<int> weight = {1, 3, 4};vector<int> value = {15, 20, 30};int bagWeight = 4;// 初始化vector<int> dp(bagWeight + 1, 0);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]);}}cout << dp[bagWeight] << endl;
}int main() {test_1_wei_bag_problem();
}

Tip:特别注意!!此时的内层循环一定要倒序遍历,这是为了防止重复拿物品。因为状态压缩后,当前行的数组是动态变化的,某一个位置dp[j]的产生或受到新旧数据的共同影响。因此,采用倒序遍历的方式,保证物品只拿一次,满足01背包的基本需求。

三、LeetCode416. 分割等和子集

https://leetcode.cn/problems/partition-equal-subset-sum/description/

给你一个 只包含正整数 非空 数组 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
class Solution {
public:bool canPartition(vector<int>& nums) {// 对数组来说,重量和价值是一样int sum = 0;// dp[i]中的i表示背包内总和// 题目中说:每个数组汇总的元素不会超过100,数组的大小不会超过200// 总和不会大于20000,背包最大只需要其中一半,所以10001大小就可以了vector<int> dp(10001, 0); for (int i = 0; i < nums.size(); i++) {sum += nums[i];}// 也可以使用库函数一步求和// int sum = accumulate(nums.begin(), nums.end(), 0);if (sum % 2 == 1) return false;int target = sum / 2;// 开始01背包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]);}}// 集合中的元素正好可以凑成总和targetif (dp[target] == target) return true;return false;}
};

补题哇~继续Day41 √

相关文章:

代码随想录算法训练营第四十一天 | 01背包问题-二维数组滚动数组,416. 分割等和子集

一、参考资料01背包问题 二维 https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html 视频讲解&#xff1a;https://www.bilibili.com/video/BV1cg411g7Y6 01背包问题 一维 https://programmercarl.com/%E8%83%8C%E5…...

VMware NSX 4.1 发布 - 网络安全虚拟化平台

请访问原文链接&#xff1a;VMware NSX 4 - 网络安全虚拟化平台&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页&#xff1a;www.sysin.org VMware NSX 提供了一个敏捷式软件定义基础架构&#xff0c;用来构建云原生应用程序环境。NSX 专注于为具有异…...

计算理论 复杂度预备知识

文章目录计算理论 复杂度预备知识符号递归表达式求解通项公式主方法Akra-Bazzi 定理计算理论 复杂度预备知识 符号 f(n)o(g(n))f(n)o(g(n))f(n)o(g(n)) &#xff1a;∃c\exists c∃c &#xff0c;当 nnn 足够大时&#xff0c; f(n)<cg(n)f(n)\lt cg(n)f(n)<cg(n) &#…...

二叉树——二叉搜索树中的插入操作

二叉搜索树中的插入操作 链接 给定二叉搜索树&#xff08;BST&#xff09;的根节点 root 和要插入树中的值 value &#xff0c;将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 &#xff0c;新值和原始二叉搜索树中的任意节点值都不同。 注意&#xff0c…...

C# if break,if continue,if return的区别和使用

故事部分&#xff1a; 现在你肚子饿了&#xff0c;想要去&#xff1a; 1.吃个三菜一汤。 2.吃个蛋糕。 3.喝个奶茶。 结果&#xff0c;你吃饭的时候&#xff0c;吃到一个虫子。 你会有几种做法&#xff1f; 1.把有虫子这道菜拿走&#xff0c;继续吃下一道菜 。 2.算了&#xff…...

力扣-第二高的薪水

大家好&#xff0c;我是空空star&#xff0c;本篇带大家了解一道中等的力扣sql练习题。 文章目录前言一、题目&#xff1a;176. 第二高的薪水二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.正确示范④提交SQL运行结果5.其他总结…...

I - 太阳轰炸(组合数学Cnk n固定)

2023河南省赛组队训练赛&#xff08;二&#xff09; - Virtual Judge (vjudge.net) 背景&#xff1a;阿塔尼斯&#xff0c;达拉姆的大主教&#xff0c;在艾尔又一次沦陷之后指挥着星灵的最后一艘方舟舰&#xff1a;亚顿之矛。作为艾尔星灵数千年来的智慧结晶&#xff0c;亚顿之…...

centos安装gitlab

更新系统 sudo yum -y update安装所需要的包 sudo yum -y install epel-release curl vim policycoreutils-python如果要安装并使用本地Postfix服务器发送通知&#xff0c;请安装Postfix&#xff0c;这里就不安装了&#xff1a; sudo yum -y install postfix安装后启动并启用…...

【洛谷 P1093】[NOIP2007 普及组] 奖学金 题解(结构体排序)

[NOIP2007 普及组] 奖学金 题目描述 某小学最近得到了一笔赞助&#xff0c;打算拿出其中一部分为学习成绩优秀的前 555 名学生发奖学金。期末&#xff0c;每个学生都有 333 门课的成绩:语文、数学、英语。先按总分从高到低排序&#xff0c;如果两个同学总分相同&#xff0c;再…...

【Hello Linux】进程优先级和环境变量

作者&#xff1a;小萌新 专栏&#xff1a;Linux 作者简介&#xff1a;大二学生 希望能和大家一起进步&#xff01; 本篇博客简介&#xff1a;简单介绍下进程的优先级 环境变量 进程优先级环境变量进程的优先级基本概念如何查看优先级PRI与NINI值的设置范围NI值如何修改修改方式…...

日期:Date,SimpleDateFormat常见API以及包装类

一.Date类 package com.gch.d1_date;import java.util.Date;/**目标:学会使用Date类处理时间,获取时间的信息*/ public class DateDemo1 {public static void main(String[] args) {// 1.创建一个Date类的对象:代表系统此刻日期时间对象Date d new Date();System.out.println(…...

嵌入式之ubuntu终端操作与shell常用命令详解

目录 文件和目录列表 基本列表功能 显示列表长度 过滤输出列表 浏览文件系统 Linux 文件系统 遍历目录 处理文件 创建文件 复制文件 制表键自动补全 重命名文件 删除文件 处理目录 创建目录 删除目录 ​编辑其他常用命令与操作 Uname命令 clear命令 返回上一级命令 显…...

【Shell学习笔记】6.Shell 流程控制

前言 本章介绍Shell的流程控制。 Shell 流程控制 和 Java、PHP 等语言不一样&#xff0c;sh 的流程控制不可为空&#xff0c;如(以下为 PHP 流程控制写法)&#xff1a; 实例 <?php if (isset($_GET["q"])) {search(q); } else {// 不做任何事情 }在 sh/bash…...

27k入职阿里测开岗那天,我哭了,这5个月付出的一切总算没有白费~

先说一下自己的个人情况&#xff0c;计算机专业&#xff0c;16年普通二本学校毕业&#xff0c;经历过一些失败的工作经历后&#xff0c;经推荐就进入了华为的测试岗&#xff0c;进去才知道是接了个外包项目&#xff0c;不太稳定的样子&#xff0c;可是刚毕业谁知道什么外包不外…...

服务端开发之Java备战秋招面试篇5

努力了那么多年,回头一望,几乎全是漫长的挫折和煎熬。对于大多数人的一生来说,顺风顺水只是偶尔,挫折、不堪、焦虑和迷茫才是主旋律。我们登上并非我们所选择的舞台,演出并非我们所选择的剧本。继续加油吧&#xff01; 目录 1.ArrayList与LinkedList区别&#xff0c; 应用场景…...

有趣的 Kotlin 0x11: joinToString,你真的了解嘛?

前言 之前使用 joinToString 函数也就是用逗号连接集合元素形成字符串&#xff0c;也没有细看它的参数&#xff0c;但是今天和 ChatGPT 聊天时&#xff0c;发现它给我输出了诸多内容。 joinToString joinToString()是Kotlin中一个非常有用的函数&#xff0c;它可以将集合的元…...

代码随想录算法训练营day46 | 动态规划之背包问题 139.单词拆分

day46139.单词拆分1.确定dp数组以及下标的含义2.确定递推公式3.dp数组如何初始化4.确定遍历顺序5.举例推导dp[i]139.单词拆分 题目链接 解题思路&#xff1a;单词就是物品&#xff0c;字符串s就是背包&#xff0c;单词能否组成字符串s&#xff0c;就是问物品能不能把背包装满。…...

DPDK中的无锁共享数据结构

目录背景解决方法共享内存无锁操作新/老共享数据结构rte_ringrefcnt延迟释放方法1&#xff1a;读的线程来释放方法2&#xff1a;释放线程等到读线程轮询一轮参考背景 dpvs多线程&#xff0c;如何做到节约内存、高性能之间的均衡。 解决方法 共享内存 多线程共享内存&#x…...

【使用两个栈实现队列】

文章目录一、栈和队列的基本特点二、基本接口函数的实现1.栈的接口2.创建队列骨架3.入队操作4.取出队列元素5.返回队首元素6.判断队列是否为空7.销毁队列总结一、栈和队列的基本特点 栈的特点是后进先出&#xff0c;而队列的特点是先进先出。 使用两个栈实现队列&#xff0c;必…...

web,h5海康视频接入监控视频流记录一

项目需求&#xff0c;web端实现海康监控视频对接接入&#xff0c;需实现实时预览&#xff0c;云台功能&#xff0c;回放功能。 web端要播放视频&#xff0c;有三种方式&#xff0c;一种是装浏览器装插件&#xff0c;一种是装客户端exe&#xff0c;还有就是无插件了。浏览器装插…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

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…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...