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

代码随想录算法训练营第四十六天(动态规划篇)|01背包(滚动数组方法)

01背包(滚动数组方法)

学习资料:代码随想录 (programmercarl.com)

题目链接(和上次一样):题目页面 (kamacoder.com)

思路

使用一维滚动数组代替二维数组。二维数组的解法记录在:代码随想录算法训练营第四十五天(动态规划篇)|01背包-CSDN博客

1. dp[j]定义

容量为j的背包可以背的物品的最大价值。

2. 递推公式

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

3. 初始条件:

dp[0] = 0, 根据递推公式,dp[j]取当前和前面的值的最大值,题目给的价值都是正整数,那么非0下标都初始化为0就可以了。

4. 遍历顺序

先遍历物品,再从大到小遍历背包。之所以要从大到小遍历,是为了防止物品被重复放入。 

e.g. i = 0: dp[1] = 15, dp[2] = max(dp[2] = 0, dp[2-weight[1]] + value[1] = dp[1] + value[1] = 15 + 15 = 30)。 而当从后往前遍历时, i = 0: dp[4] = 15 dp[3] = max(0, dp[2] + value[0]) = max(0, 0 + 15) = 15,是正确的。

二维数组可以从小到大遍历,是因为当前的dp[i][j]不包括当前的物品i,是从[0, i-1]中选取物品。

5. 举例推导dp数组

代码实现

objNum, bagWeight=map(int,input().split())weight= [int(i) for i in input().split()]
value = [int(i) for i in input().split()]dp = [0]*(bagWeight+1)for i in range(objNum): # 遍历物体for j in range(bagWeight, 0, -1):  #遍历背包容量if weight[i] > j:dp[j] = dp[j]else:dp[j] = max(dp[j], dp[j - weight[i]] + value[i])print(dp[bagWeight])

相关文章:

代码随想录算法训练营第四十六天(动态规划篇)|01背包(滚动数组方法)

01背包(滚动数组方法) 学习资料:代码随想录 (programmercarl.com) 题目链接(和上次一样):题目页面 (kamacoder.com) 思路 使用一维滚动数组代替二维数组。二维数组的解法记录在:代码随想录算…...

【QT+QGIS跨平台编译】之三十:【NetCDF+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

文章目录 一、NetCDF介绍二、文件下载三、文件分析四、pro文件4.1 netcdf34.2 netcdf44.3 netcdf五、编译实践一、NetCDF介绍 NetCDF(Network Common Data Form)是一种用于存储和处理科学数据的文件格式和库。它提供了一种自描述、可移植和可扩展的方式来组织多维数据,并支…...

从0开始图形学(光栅化)

前言 说起图形学,很多人就会提到OpenGL,但其实两者并不是同一个东西。引入了OpenGL加重了学习的难度和成本,使得一些原理并不直观。可能你知道向量,矩阵,纹理,重心坐标等概念,但就是不知道这些概…...

B站弹幕分析系统

视频展示,请点击。 尚硅谷案例 utllib的基本使用 # 使用urllib来获取百度首页的源码 import urllib.request# (1)定义一个url 就是你要访问的地址 url http://www.baidu.com# (2)模拟浏览器先服务器发送请求 response响应 response urllib.request.urlopen(url)…...

戴上HUAWEI WATCH GT 4,解锁龙年新玩法

春节将至,华为WATCH GT 4作为一款颜值和实力并存的手表,能为节日增添了不少趣味和便利。无论你是钟情于龙年表盘或定制属于自己的表盘,还是过年用来抢红包或远程操控手机拍全家福等等,它都能成为你的“玩伴”。接下来,…...

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之StepperItem组件

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之StepperItem组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、StepperItem组件 用作Stepper组件的页面子组件。 子组件 无。 接口 St…...

2024-02-08 Unity 编辑器开发之编辑器拓展1 —— 自定义菜单栏与窗口

文章目录 1 特殊文件夹 Editor2 在 Unity 菜单栏中添加自定义页签3 在 Hierarchy 窗口中添加自定义页签4 在 Project 窗口中添加自定义页签5 在菜单栏的 Component 菜单添加脚本6 在 Inspector 为脚本右键添加菜单7 加入快捷键8 小结 1 特殊文件夹 Editor ​ Editor 文件夹是 …...

Intellij IDEA各种调试+开发中常见bug

Intellij IDEA中使用好Debug,主要包括如下内容: 一、Debug开篇 ①、以Debug模式启动服务,左边的一个按钮则是以Run模式启动。在开发中,我一般会直接启动Debug模式,方便随时调试代码。 ②、断点:在左边行…...

文件上传-Webshell

Webshell简介 webshell就是以aspphpjsp或者cgi等网页文件形式存在的一种命令执行环境,也可以将其称做为一种网页木马后门。 攻击者可通过这种网页后门获得网站服务器操作权限,控制网站服务器以进行上传下载文件、查看数据库、执行命令等… 什么是木马 …...

掌握虚拟化与网络配置之道:深入浅出VMware及远程管理技巧

目录 虚拟机介绍 虚拟机的关键字 服务器架构的发展 为什么用虚拟机VMware 虚拟机和阿里云的区别 功能角度 价格因素 应用场景 优势方面 找到windows的服务管理 配置VMware 关于VMware安装的几个服务 vmware如何修改各种网络配置 关于NAT的详细信息(了解) NAT(网…...

【漏洞复现】狮子鱼CMS某SQL注入漏洞

Nx01 产品简介 狮子鱼CMS(Content Management System)是一种网站管理系统,它旨在帮助用户更轻松地创建和管理网站。该系统拥有用户友好的界面和丰富的功能,包括页面管理、博客、新闻、产品展示等。通过简单直观的管理界面&#xf…...

Python学习之路-Tornado基础:安全应用

Python学习之路-Tornado基础:安全应用 Cookie 对于RequestHandler,除了在初始Tornado中讲到的之外,还提供了操作cookie的方法。 设置 set_cookie(name, value, domainNone, expiresNone, path‘/’, expires_daysNone) 参数说明: 参数名…...

6.0 Zookeeper session 基本原理详解教程

客户端与服务端之间的连接是基于 TCP 长连接,client 端连接 server 端默认的 2181 端口,也就 是 session 会话。 从第一次连接建立开始,客户端开始会话的生命周期,客户端向服务端的ping包请求,每个会话都可以设置一个…...

生成式人工智能攻击的一年:2024

趋势科技最近公布了其关于预期最危险威胁的年度研究数据。生成人工智能的广泛可用性和质量将是网络钓鱼攻击和策略发生巨大变化的主要原因。 趋势科技宣布推出“关键可扩展性”,这是著名年度研究的新版本,该研究分析了安全形势并提出了全年将肆虐的网络…...

K8S之Namespace的介绍和使用

Namespace的理论和实操 Namespace理论说明Namespace实操创建、查看命名空间使用ResouceQuota 对Namespace做资源限额更多ResouceQuota 的使用 Namespace理论说明 命名空间定义 K8s支持多个虚拟集群,它们底层依赖于同一个物理集群。 这些虚拟集群被称为命名空间&…...

封装sku组件

1. 准备模板渲染规格数据 使用Vite快速创建一个Vue项目&#xff0c;在项目中添加请求插件axios&#xff0c;然后新增一个SKU组件&#xff0c;在根组件中把它渲染出来&#xff0c;下面是规格内容的基础模板 <script setup> import { onMounted, ref } from vue import axi…...

Unity笔记:相机移动

基础知识 鼠标输入 在Unity中&#xff0c;开发者在“Edit” > “Project Settings” > “Input Manager”中设置输入&#xff0c;如下图所示&#xff1a; 在设置了Mouse X后&#xff0c;Input.GetAxis("Mouse X")返回的是鼠标在X轴上的增量值。这意味着它会…...

Java项目管理01-Maven基础

一、Maven的常用命令和生命周期 1.Maven的常用命令使用方式 complie&#xff1a;编译&#xff0c;将java文件编译为class字节码文件 clean&#xff1a;清理&#xff0c;删除字节码文件 test&#xff1a;测试&#xff0c;运行项目中的test类 package&#xff1a;打包&#x…...

计算机网络(第六版)复习提纲30

B HTTP 名词解释&#xff1a;协议HTTP定义了浏览器怎样向万维网服务器请求万维网文档&#xff0c;以及服务器怎样把文档传给浏览器。从层次的角度看&#xff0c;HTTP是面向事务的应用层协议&#xff0c;它是万维网上可靠地交换文件的重要基础&#xff0c;不仅能够传送完成超文本…...

基于SSM的图书管理系统

点击以下链接获取资源&#xff1a; https://download.csdn.net/download/qq_64505944/88820548?spm1001.2014.3001.5503 Java项目-6 librarySystem 开发完毕 万一你要作为课程设计或者毕设&#xff0c;不太会配&#xff0c;可以到下面我博客中私信&#xff0c;我帮你远程部…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...