代码随想录算法训练营第四十二天|01背包问题、416. 分割等和子集
动态规划
文章目录
- 一、01背包问题
- 二、分割等和子集
- 总结
一、01背包问题
1.在有限的背包内放入最高价值的东西
2.二维数据和一维数据都可以解决
3.二维数据,递推公式为dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]),分为两个状态,放入第i个物品和不放入第i个物品,取其中的最大值。表示遍历到第i个物品时可以得到的最大价值,当前i的最大价值由i上边和左边的物品决定。递推公式不算很难,难点在于数组初始化以及遍历顺序。
4.一维数组,也就是滑动数组,当前遍历结果受到上层结果影响。递推公式为dp[j] = max(dp[j], dp[j-weight[i]]+value[i]),表示在j容量下,可以获得的最大价值。因为是一维数组,同时当前的遍历结果受到上一层的影响,所以遍历顺序需要从后往前。如果从前往后的话,上层遍历结果要先于当前遍历物品改变,所以要从后往前。
二、分割等和子集
01背包问题,将问题抽象为01背包问题。
class Solution {
public:bool canPartition(vector<int>& nums) {//两个子集的元素和相同,也就是如果能组成一个sum/2,那其他的元素也能组成sum/2//sum/2相等于背包容量//1.dp数组及下标含义vector<int>dp(10001, 0);int sum = 0;for (int i = 0; i < nums.size(); i++) {sum += nums[i];}if (sum % 2 == 1) return false;int target = sum / 2;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;}
};
总结
有点宕机,感觉总有点不对,某个节点一直没整明白,明天再好好理一下
学习时间90min。
学习资料:《代码随想录》。
相关文章:
代码随想录算法训练营第四十二天|01背包问题、416. 分割等和子集
动态规划 文章目录 一、01背包问题二、分割等和子集总结 一、01背包问题 1.在有限的背包内放入最高价值的东西 2.二维数据和一维数据都可以解决 3.二维数据,递推公式为dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]]value[i]),分为两个状态࿰…...
JVM主要知识点详解
目录 1. 性能监控和调优 1.1 调优相关参数 1.2 内存泄漏排查 1.3 cpu飙⾼ 2. 内存与垃圾回收 2.1JVM的组成(面试题) 2.2 Java虚拟机栈的组成 2.3 本地方法栈 2.4 堆 2.5 方法区(抽象概念) 2.5.1 方法区和永久代以及元空…...
hot100 -- 链表(中)
不要觉得力扣核心代码模式麻烦,它确实比不上ACM模式舒服,可以自己处理输入输出 只是你对 链表 和 return 的理解不到位 👂 ▶ 屿前世 (163.com) 👂 ▶ see you tomorrow (163.com) 目录 🎂两数相加 🚩删…...
数据结构面试常见问题
数据结构是计算机科学中非常重要的一部分,也是面试中经常被考察的内容。以下是一些在数据结构面试中常见的问题: 1. 数组 (Array): 描述数组和链表的区别。如何在数组中实现循环队列?给定一个数组,如何找到两个数的和等于给定值…...
蓝桥杯2024年第十五届省赛真题-R 格式(高精度乘法 + 加法)
本题链接:蓝桥杯2024年第十五届省赛真题-R 格式 - C语言网 题目: 样例: 输入 2 3.14 输出 13 思路: 根据题意,结合数据范围,这是一道模板的高精度乘以低精度问题。 题意是double 类型 d 与…...
普通人做抖音小店真的能赚钱吗?可以,但更取决于个人
大家好,我是电商花花。 现在做抖音小店的基本上都是一些新商家,对于我们众多零基础的朋友来说,是期待也是一份挑战。 抖音小店作为一个充满机会的新兴平台,许多人都欣喜的投入其中,期望能够借此来改变自己的命运&…...
基于单链表实现通讯管理系统!(有完整源码!)
个人主页:秋风起,再归来~ 文章专栏:C语言实战项目 个人格言:悟已往之不谏,知来者犹可追 克心守己,律己则安! 1、前言 友友们,这篇文章是基于单链…...
MATLAB入门介绍
MATLAB是由MathWorks公司开发的一款专业的数学计算软件,主要用于算法开发、数据可视化、数据分析以及数值计算等领域。它提供了一个易于使用的环境,让用户可以通过矩阵计算、函数和数据绘图、用户界面的创建以及编程和文档编写来解决各种数学问题。 MATL…...
【k8s】:深入理解 Kubernetes 中的污点(Taints)与容忍度(Tolerations)
【k8s】:深入理解 Kubernetes 中的污点(Taints)与容忍度(Tolerations) 1、污点(Taints)2、容忍度(Tolerations)3、示例演示-测试污点的具体应用场景3.1 给节点打污点&…...
Angular 使用DomSanitizer防范跨站脚本攻击
跨站脚本Cross-site scripting 简称XSS,是代码注入的一种,是一种网站应用程序的安全漏洞攻击。它允许恶意用户将代码注入到网页上,其他用户在使用网页时就会收到影响,这类攻击通常包含了HTML和用户端脚本语言(JS&…...
(八)PostgreSQL的数据库管理
PostgreSQL的数据库管理 基础信息 OS版本:Red Hat Enterprise Linux Server release 7.9 (Maipo) DB版本:16.2 pg软件目录:/home/pg16/soft pg数据目录:/home/pg16/data 端口:57771 创建数据库 CREATE DATABASE创建一…...
外包干了30天,技术倒退明显
先说情况,大专毕业,18年通过校招进入湖南某软件公司,干了接近6年的功能测试,今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落! 而我已经在一个企业干了四年的功能…...
ruoyi-nbcio-plus基于vue3的flowable的自定义业务单表例子的升级修改
更多ruoyi-nbcio功能请看演示系统 gitee源代码地址 前后端代码: https://gitee.com/nbacheng/ruoyi-nbcio 演示地址:RuoYi-Nbcio后台管理系统 http://122.227.135.243:9666/ 更多nbcio-boot功能请看演示系统 gitee源代码地址 后端代码:…...
【ENSP】华为三层交换机配置AAA认证,开启telnet服务
配置步骤 1.给交换机配置ip地址,以便登陆 2.配置AAA,用户名,密码,服务类型,用户权限 3.配置接入设备的数量 4.开启telnet服务 LSW2交换机配置 u t m #关闭提示 sys …...
collections模块下的Counter函数讲解
📚博客主页:knighthood2001 ✨公众号:认知up吧 (目前正在带领大家一起提升认知,感兴趣可以来围观一下) 🎃知识星球:【认知up吧|成长|副业】介绍 ❤️感谢大家点赞👍&…...
HarmonyOS开发实例:【分布式邮件】
概述 基于TS扩展的声明式开发范式编程语言编写的一个分布式邮件系统,可以由一台设备拉起另一台设备,每次改动邮件内容,都会同步更新两台设备的信息。效果图如下: 搭建OpenHarmony开发环境 完成本篇Codelab我们首先要完成开发环境…...
llama2.c与chinese-baby-llama2语言模型本地部署推理
文章目录 简介Github文档克隆源码英文模型编译运行中文模型(280M)main函数 简介 llama2.c是一个极简的Llama 2 LLM全栈工具,使用一个简单的 700 行 C 文件 ( run.c ) 对其进行推理。llama2.c涉及LLM微调、模型构建、推理端末部署(…...
008、Python+fastapi,第一个后台管理项目走向第8步:ubutun 20.04下安装vscode+python环境配置
一、说明 白飘了3个月无影云电脑,开始选了个windows server 非常不好用,后台改为ubuntu想升级到22,没成功,那就20.04吧。 今天先安装下开发环境,后续2个月就想把他当做开发服务器,不知道行不行,…...
2024.4.16 驱动开发
思维导图...
如何在 Ubuntu 14.04 上更改 PHP 设置
简介 PHP 是一种服务器端脚本语言,被许多流行的 CMS 和博客平台如 WordPress 和 Drupal 所使用。它也是流行的 LAMP 和 LEMP 堆栈的一部分。更新 PHP 配置设置是设置基于 PHP 的网站时的常见任务。定位确切的 PHP 配置文件可能并不容易。通常在服务器上会有多个 PH…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
Oracle11g安装包
Oracle 11g安装包 适用于windows系统,64位 下载路径 oracle 11g 安装包...
深入浅出WebGL:在浏览器中解锁3D世界的魔法钥匙
WebGL:在浏览器中解锁3D世界的魔法钥匙 引言:网页的边界正在消失 在数字化浪潮的推动下,网页早已不再是静态信息的展示窗口。如今,我们可以在浏览器中体验逼真的3D游戏、交互式数据可视化、虚拟实验室,甚至沉浸式的V…...
网页端 js 读取发票里的二维码信息(图片和PDF格式)
起因 为了实现在报销流程中,发票不能重用的限制,发票上传后,希望能读出发票号,并记录发票号已用,下次不再可用于报销。 基于上面的需求,研究了OCR 的方式和读PDF的方式,实际是可行的ÿ…...
