当前位置: 首页 > 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;还有就是无插件了。浏览器装插…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...