代码随想录算法训练营打卡第35天:背包问题
前言
zaccheo打卡代码随想录第35天
由于这段时间工作太忙了(加上我的懒病犯了)导致迟打卡了好几天555555.。。。
今天的主要是动态规划中的背包问题,这个真的是蛮难理解的,我把我自己强行按在椅子上半个小时一点一点的看卡哥文章才理解透彻最后又在纸上复盘了一遍
这是卡哥原文章链接:代码随想录
我就直接写我的理解了,dp[i][j],其中i为物品索引,j为背包重量,dp[i][j]代表的是在加入物品i的时候背包重量为j的最大总价值
当遍历到物品i的时候,取此时背包重量的最大值有两种可能,第一加上物品i,第二不加上物品i,如果不加上物品i背包价值的最大值为dp[i-1][j]
加上物品i此时背包价值的最大值为dp[i-1][j-weight[i]]+value[i],因为此时背包可以装j的重量,而物品i的重量为weight[i],则如果加上物品i,背包剩余的重量j-weight[i],而dp数组又表示代表的是在加入物品i的时候背包重量为j的最大总价值,所以加入物品i时,背包最大价值为dp[i-1][j-weight[i]]+value[i]
最后比较dp[i-1][j]和dp[i-1][j-weight[i]]+value[i]的价值哪个大即为背包的最大总价值
这是二维数组的解法,同时还有一维数组的解法,首先要理解什么是滚动数组,此文章有详细解释:滚动数组(简单说明)_滚动数组思想-CSDN博客
这是卡哥对一维数组解决背包问题的文章:代码随想录
Leetcode416.分割等和子集
这道题可以抽象成背包问题,使用背包问题的思路取解答,二维数组和一维数据解法如下:
class Solution {public boolean canPartition(int[] nums) {Arrays.sort(nums);int sum=0;for(int i=0;i<nums.length;i++){sum+=nums[i];}if(sum%2!=0){return false;}int[][] dp=new int[nums.length][sum/2];for(int i=0;i<nums.length;i++){dp[i][0]=0;}for(int j=0;j<sum/2;j++){if(nums[0]<j){dp[0][j]=0;}else{dp[0][j]=nums[0];}}for(int i=1;i<nums.length;i++){for(int j=0;j<sum/2;j++){if(j<nums[i]){dp[i][j]=dp[i-1][j];}else{dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);}if(dp[i][j]==sum/2){return true;}else if(dp[i][j]>sum/2){continue;}}}return false;}
}
class Solution {public boolean canPartition(int[] nums) {Arrays.sort(nums);int sum=0;for(int i=0;i<nums.length;i++){sum+=nums[i];}if(sum%2!=0){return false;}int[] dp=new int[sum/2+1];for(int i=0;i<nums.length;i++){for(int j=sum/2;j>=nums[i];j--){dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);if(dp[j]==sum/2){return true;}}}return false; }
}
相关文章:
代码随想录算法训练营打卡第35天:背包问题
前言 zaccheo打卡代码随想录第35天 由于这段时间工作太忙了(加上我的懒病犯了)导致迟打卡了好几天555555.。。。 今天的主要是动态规划中的背包问题,这个真的是蛮难理解的,我把我自己强行按在椅子上半个小时一点一点的看卡哥文章…...
【MySQL】数据库 Navicat 可视化工具与 MySQL 命令行基本操作
💯 欢迎光临清流君的博客小天地,这里是我分享技术与心得的温馨角落 💯 🔥 个人主页:【清流君】🔥 📚 系列专栏: 运动控制 | 决策规划 | 机器人数值优化 📚 🌟始终保持好奇心&…...
vscode(一)安装(ubuntu20.04)
1、更新软件包列表 sudo apt update2、安装依赖包 sudo apt install software-properties-common apt-transport-https wget3、导入Microsoft GPG密钥 wget -q https://packages.microsoft.com/keys/microsoft.asc -O- | sudo apt-key add -4、向系统添加VSCode存储库 sudo…...
利用永恒之蓝对win7进行键盘记录
打开kali中的msfconsole 找到永恒之蓝,设置靶机ip,后可以exploit,也可以run 连接成功 查看进程,选择监听靶机win7上的cmd.exe进程 当前进程不是1484,需要迁移到1484 cmd.exe,进程迁移 键盘监听,…...
万字长文解读深度学习——dVAE(DALL·E的核心部件)
🌺历史文章列表🌺 深度学习——优化算法、激活函数、归一化、正则化 深度学习——权重初始化、评估指标、梯度消失和梯度爆炸 深度学习——前向传播与反向传播、神经网络(前馈神经网络与反馈神经网络)、常见算法概要汇总 万字长…...
RL仿真库pybullet
1. 介绍 PyBullet是一个基于Bullet Physics引擎的物理仿真Python接口,主要用于机器人仿真模拟。 1.1 主要特点 提供大量预设的机器人模型,例如URDF(统一机器人描述格式)、SDF、MJCF 格式。适用于训练和评估强化学习算法,提供了大量的强化学…...
file_get_contents函数导致网站卡死响应超时
宝塔控制面板系统下运行包含file_get_contents函数的php文件时候,发生以下报错: PHP Warning: file_get_contents():php_network_getaddresses: getaddrinfo failed: 解决方法: 一:需要检查请求的远程主机是否在本机的/etc/host…...
如何使用C#与SQL Server数据库进行交互
一.创建数据库 用VS 创建数据库的步骤: 1.打开vs,创建一个新项目,分别在搜素框中选择C#、Windows、桌面,然后选择Windows窗体应用(.NET Framework) 2.打开“视图-服务器资源管理器”,右键单击“数据连接”࿰…...
#渗透测试#红蓝对抗#SRC漏洞挖掘# Yakit(5)进阶模式-MITM中间人代理与劫持(上)
免责声明 本教程仅为合法的教学目的而准备,严禁用于任何形式的违法犯罪活动及其他商业行为,在使用本教程前,您应确保该行为符合当地的法律法规,继续阅读即表示您需自行承担所有操作的后果,如有异议,请立即停…...
vue3 项目搭建-9-通过 router 在跳转页面时传参
第一步,在跳转链接处挂载方法,将要传输的数据传入: <a href"#" click.prevent"goToArticle(obj.id)" class"click"><h1>{{obj.title}}</h1><p>作者:{{obj.author}}</p&…...
Java、python标识符命名规范
Java 包名所有字母一律小写。例如cn.com.test类名和接口名每个单词的首字母都要大写。例如ArrayList、Iterator常量名所有字母都大写,单词之间用下划线连接,例如:DAY_OF_MONTH变量名和方法名的第一个单词首字母小写,从第二个单词…...
高效职场人
文章目录 1.时间效能 ABCD2.高效员工的习惯之 自我掌控的秘诀3.学会做主4.学会互赢5.学会沟通、学会聆听6.学会可持续发展:四个方面更新自我(1)更新身体(2)更新精神(3)更新智力(4)更新人际情感 1.时间效能 ABCD 时间四象限: A类任务:重要且紧…...
深入探索现代 IT 技术:从云计算到人工智能的全面解析
目录 1. 云计算:重塑 IT 基础设施 2. 大数据:挖掘信息的价值 3. 物联网(IoT):连接物理世界 4. 区块链:重塑信任机制 5. 人工智能(AI):智能未来的驱动力 结语 在当今…...
【AI学习】苹果技术报告《Apple Intelligence Foundation Language Models》
文章地址:https://machinelearning.apple.com/papers/apple_intelligence_foundation_language_models.pdf 这篇文章介绍了苹果公司开发的基础语言模型(Apple Foundation Language Models,简称AFM),这些模型旨在为苹果…...
深度相机获取实时图像总结
问题详情:之前一直把曝光调整到50000,画面一直很流畅,知道领导要求将曝光改成500000时整个程序卡死了 问题解决: 首先怀疑是帧率太低的原因,控制变量后发现不是帧率的问题,看着代码很迷茫,领导…...
Nginx限流实践-limit_req和limit_conn的使用说明
注意: 本文内容于 2024-12-07 19:38:40 创建,可能不会在此平台上进行更新。如果您希望查看最新版本或更多相关内容,请访问原文地址:Nginx限流实践。感谢您的关注与支持! 一、限流 之前我有记录通过CentOS7定时任务实…...
Unity在运行状态下,当物体Mesh网格发生变化时,如何让MeshCollider碰撞体也随之实时同步变化?
旧版源代码地址:https://download.csdn.net/download/qq_41603955/90087225?spm1001.2014.3001.5501 旧版效果展示: 新版加上MeshCollider后的效果: 注意:在Unity中,当你动态地更改物体的Mesh时,通常期望…...
记一次由docker容器使得服务器cpu占满密码和密钥无法访问bug
Bug场景: 前几天在服务器上部署了一个免费影视网站,这个应用需要四个容器,同时之前的建站软件workpress也是使用docker部署的,也使用了三个容器。在使用workpress之前,我将影视软件的容器全部停止。 再使用workpress…...
前端TS基础
文章目录 一、类型1、定义类型2、any、unknown、never3、基础类型4、联合类型5、交叉类型6、type、typeof7、作用域 二、数据结构1、数组2、元组3、函数类型4、对象类型 三、接口四、泛型五、enum六、断言七、工具1、模块2、namespace3、装饰器4、declare5、运算符6、映射类型7…...
前端面经每日一题day06
Cookie有什么字段 Name:cookie的唯一标识符 Value:与Name对应,存储Cookie的信息 Domain:可以访问cookie的域名 Path:可以访问cookie的路径 Expires/Max-Age:超时时间 Size:cookie大小 Ht…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
