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

笔记:代码随想录算法训练营第35天: 01背包问题 二维、 01背包问题 一维 、LeetCode416. 分割等和子集

 学习资料:代码随想录

这一块儿学得挺痛苦

注:文中含大模型生成内容

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

卡码网第46题

思路:五部曲

定义:dp[i][j]为第i个物品背包容量为j,能装下的最大价值

递推公式:dp[i][j]的值等于dp[i-1][j]的值和dp[i-1][j-weight[i]]+value相比的最大值,后者为看放下当前物品+减去当前物品的容量能放下什么价值,当然,要是放不下当前物品,就算了,保持原来的值把

初始化:左边(dp[i][0]背包容量为0)都初始化为0,挺好的,就是不用管了

dp[0][j],容量j能把物品0放上就放上,放不上就是0

遍历顺序:怎么着都行

打印:略

#include <bits/stdc++.h>
using namespace std;int main(){int materials,N;cin>>materials>>N;vector<int> space(materials,0);for(int i=0;i<materials;i++){cin>>space[i];}vector<int> value(materials,0);for(int i=0;i<materials;i++){cin>>value[i];}vector<vector<int>> dp(materials,vector<int>(N+1,0));    //dp[i][j]表示有i个材料可以放,背包能装的空间为j时的最大价值,从行李空间为0开始递推for(int j=space[0];j<=N;j++) dp[0][j] = value[0];for(int i=1;i<materials;i++){     //i从1开始,否则在递推函数处会索引负数for(int j=0;j<=N;j++){if(j<space[i]) dp[i][j] = dp[i-1][j];       //防止下面出现负索引else{dp[i][j] = max(dp[i-1][j],dp[i-1][j-space[i]]+value[i]);  //递推公式得画图模拟一下}}}cout << dp[materials-1][N]<<endl;    //第materials个物品下标为materials-1   }

动态规划:01背包理论基础(滚动数组)

卡码网第46题

 滚动数组是把原先的二维dp数组压缩成一维了,就等于看新一个物品能不能装上的时候就按规矩累计之前的结果然后把之前的覆盖掉

主要在遍历方向上很难:

一是j要倒着遍历:

TA说得很清楚:二维是根据上一个物品更新的。而一维数组是在本行根据本物品更新的。正序的化就会产生能多次放该物品的错觉,实际上该物品只能放一次

 为什么不能先遍历背包,还是让TA帮我模拟一下,不行啊,先遍历背包的话只能加上一个物品。

啊,这不就是我的贾维斯吗!!我能获得一份开发贾维斯的工作吗

我自己模拟了一下正向遍历j在外层,不行,会出现重复放一个物品的问题。总之,根据递推公式来看,还是要提取上一轮的信息,不要让上一轮的信息被本轮信息覆盖

416. 分割等和子集

力扣题目链接

思路:关键在于如何将其转换为背包问题;

dp[j]为背包容量为j,能装的最大价值,那么在这里,,value[i]和weight[i]都是nums[i];背包容量是数字和的一半sum/2,是那个target,如果背包容量target能装target,就是能对半儿分了

// 五部曲
// dp定义:dp[j] 容量为j的背包,能装的价值为dp[j]
// 递推公式:按背包来,价值和重量都是这个数的值
// 初始化:根据递推公式的max要选最大的,nums都是正整数,所以都初始化为最小的正整数0
// 遍历顺序:按背包来
// 打印
class Solution {
public:bool canPartition(vector<int>& nums) {vector<int> dp(100*200/2+1);   //根据题意区间写的int sum = 0;for(int num:nums){sum+=num;} if (sum%2!=0) 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]);}}return dp[target] == target;}
};

https://www.youtube.com/watch?v=bI_GJHCePlY今日发现一件艺术品,搁5、6年前我可能是他们的受众,现在的我没有耐心连着看第三遍了。Anyway,祝大家今晚睡个好觉,明天是Sunday Morning哦

相关文章:

笔记:代码随想录算法训练营第35天: 01背包问题 二维、 01背包问题 一维 、LeetCode416. 分割等和子集

学习资料&#xff1a;代码随想录 这一块儿学得挺痛苦 注&#xff1a;文中含大模型生成内容 动态规划&#xff1a;01背包理论基础 卡码网第46题 思路&#xff1a;五部曲 定义&#xff1a;dp[i][j]为第i个物品背包容量为j&#xff0c;能装下的最大价值 递推公式&#xff1…...

安装 Windows Docker Desktop - WSL问题

一、关联文章: 1、Docker Desktop 安装使用教程 2、家庭版 Windows 安装 Docker 没有 Hyper-V 问题 3、打开 Windows Docker Desktop 出现 Docker Engine Stopped 问题 二、问题解析 打开 Docker Desktop 出现问题,如下: Docker Desktop - WSL update failed An error o…...

Spring MVC 返回数据

目录 1、什么是 SpringMVC2、返回数据2.1、返回 JSON 对象2.2、请求转发2.3、请求重定向2.4、自定义返回的内容 1、什么是 SpringMVC 1、Tomcat 和 Servlet 分别是什么&#xff1f;有什么关系&#xff1f; Servlet 是 java 官方定义的 web 开发的标准规范&#xff1b;Tomcat 是…...

QT-信号与槽

1.在注册登录的练习里面&#xff0c;追加一个QListWidget项目列表 要求:点击注册之后&#xff0c;将账号显示到列表窗口小部件上面去 以及&#xff0c;在列表窗口小部件中双击某个账号的时候&#xff0c;将该账号删除 头文件 #ifndef WIDGET_H #define WIDGET_H #include <…...

版图自动化连接算法开发 00001 ------ 直接连接两个给定的坐标点

版图自动化连接算法开发 00001 ------ 直接连接两个给定的坐标点 引言正文定义坐标点的类绘图显示代码直接连接两个坐标点引言 由于人工智能的加速普及,每次手动绘制版图都会觉得特别繁琐,作者本人在想可否搞一个自动化连接器件端口的算法,后期可以根据一些设定的限制进行避…...

迷你世界脚本方块接口:Block

方块接口&#xff1a;Block 彼得兔 更新时间: 2024-08-27 11:04:56 具体函数名及描述如下&#xff1a; 序号 函数名 函数描述 1 isSolidBlock(...) 是否是固体方块 2 isLiquidBlock(...) 是否是液体方块 3 isAirBlock(...) 是否是气体方块 4 getBl…...

打造高清3D虚拟世界|零基础学习Unity HDRP高清渲染管线(第一天)

打造高清3D虚拟世界|零基础学习Unity HDRP高清渲染管线&#xff08;第一天&#xff09; 前言最后 前言 说真的&#xff0c;用Unity工作这几年&#xff0c;经历的项目大大小小&#xff0c;对于场景的渲染算是有一定的经验&#xff0c;但涉及到HDRP高清渲染管线的了解&#xff0…...

Docker项目部署-部署前端

nginx.conf文件内容如下。 worker_processes 1;events {worker_connections 1024; }http {include mime.types;default_type application/json;sendfile on;keepalive_timeout 65;server {listen 18080;# 指定前端项目所在的位置location / {root /usr/…...

【向量数据库Weaviate】与ChromaDB的差异、优劣

以下是 Weaviate 和 ChromaDB 的详细对比&#xff0c;涵盖设计目标、核心功能、性能、适用场景及优劣势分析&#xff1a; 1. 核心定位与设计目标 维度WeaviateChromaDB类型向量数据库 图数据库&#xff08;支持混合搜索&#xff09;轻量级纯向量数据库&#xff08;专注嵌入存…...

2024华为OD机试真题-热点网站统计(C++)-E卷-100分

2024华为OD机试最新E卷题库-(C卷+D卷+E卷)-(JAVA、Python、C++) 目录 题目描述 输入描述 输出描述 用例1 用例2 考点 题目解析 代码 c++ 题目描述 企业路由器的统计页面,有一个功能需要动态统计公司访问最多的网页 URL top N。 请设计一个算法,可以高效动态统计 …...

【大模型】大模型分类

大模型&#xff08;Large Models&#xff09;通常指参数量巨大、计算能力强大的机器学习模型&#xff0c;尤其在自然语言处理&#xff08;NLP&#xff09;、计算机视觉&#xff08;CV&#xff09;等领域表现突出。以下是大模型的常见分类方式&#xff1a; 1. 按应用领域分类 …...

Redis 的几个热点知识

前言 Redis 是一款内存级的数据库&#xff0c;凭借其卓越的性能&#xff0c;几乎成为每位开发者的标配工具。 虽然 Redis 包含大量需要掌握的知识&#xff0c;但其中的热点知识并不多。今天&#xff0c;『知行』就和大家分享一些 Redis 中的热点知识。 Redis 数据结构 Redis…...

【新手入门】SQL注入之getshell(木马)

木马介绍 木马其实就是一段程序&#xff0c;这个程序运行到目标主机上时&#xff0c;主要可以对目标进行远程控制、盗取信息等功能&#xff0c;一般不会破坏目标主机&#xff0c;当然&#xff0c;这也看黑客是否想要搞破坏。 按照功能分类:远控型、破坏型、流氓软件型、盗取信…...

【pytest框架源码分析二】pluggy源码分析之add_hookspecs和register

这里我们看一下_manager.py里的类和方法&#xff0c;最主要的是PluginManager类&#xff0c;类的初始化函数如下&#xff1a; class PluginManager:"""Core class which manages registration of plugin objects and 1:N hookcalling.You can register new hoo…...

四、数据存储

在爬虫项目中&#xff0c;我们需要将目标站点数据进行持久化保存&#xff0c;一般数据保存的方式有两种&#xff1a; 文件保存数据库保存 在数据保存的过程中需要对数据完成去重操作&#xff0c;所有需要使用 redis 中的 set 数据类型完成去重。 1.CSV文件存储 1.1 什么是c…...

【原创】Ollama Test API For Linux/MacOS/Unix

安装Json解析工具 Linux/Unix sudo apt-get install jq -yMacOS brew install jq -y设置环境变量 export IP"192.168.250.229" export PORT"8080" export MODEL"deepseek-r1:7b"检查Ollama版本 curl http://"$IP":"$PORT&qu…...

LeetCode-Hot100-005盛最多水的容器

不懂的可以在评论区问我。 代码 双指针&#xff0c;开始的时候一个在最左边&#xff0c;一个在最右边。每次移动矮的那头&#xff0c;因为这是矮柱子作为容器能装的水的极限了。 class Solution { public:int maxArea(vector<int>& height) {int left 0; int rig…...

电源测试系统有哪些可以利用AI工具的科技??

AI技术的发展对电源模块测试系统的影响是深远的&#xff0c;不仅协助系统提升了测试效率和精度&#xff0c;还推动了测试方法的创新和智能化。那么在电源测试系统中哪些模块可以利用AI工具实现自动化测试? 1. 自动化测试与效率提升 智能测试流程优化 AI算法可以自动优化测试…...

【3-3】springcloud

OpenFeign 启动OpenFeign 定义客户端接口 注入客户端并使用 OpenFeignhttp调用ribbon负载均衡 gateway 来自&#xff1a;https://mynamelancelot.github.io/spring-cloud/spring-cloud-gateway.html#cors https://blog.csdn.net/qingdao666666/article/details/119973771 …...

Goby 漏洞安全通告| Ollama /api/tags 未授权访问漏洞(CNVD-2025-04094)

漏洞名称&#xff1a;Ollama /api/tags 未授权访问漏洞&#xff08;CNVD-2025-04094&#xff09; English Name&#xff1a;Ollama /api/tags Unauthorized Access Vulnerability (CNVD-2025-04094) CVSS core: 6.5 风险等级&#xff1a; 中风险 漏洞描述&#xff1a; O…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...