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

蓝桥杯刷题第二天——背包问题

news 来源：原创 2025/6/16 21:36:53

题目描述

有N件物品和一个容量是V的背包。每件物品只能使用一次。第i件物品的体积是Vi价值是Wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有N行，每行两个整数,W，用空格隔开，分别表示第件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0< N,V≤ 1000
0<v,W≤1000

解题思路

此题可用动态规划来解决。

1.首先定义一个二维数组组dp[i][j]，表示前i个物品放入容量为j的背包中能获得的最大价值。

2.状态转移方程为：dp[i][j]=max(dp[i－1][j]，dp[i－1][j－v[i]]+w[i]]，其中v[i] 和 w[i] 分别是第i个物品的体积和价值。这个方程的含义是，对于第i个物品，有两种选择：不放入背包（价值为dp[i－1][j]），或者放入背包（价值为dp[i－1][j－v[i]]+w[i]），取两者中的较大值。

3.边界条件：当i=或=时，dp[i][j］=，即没有物品或者背包容量为0时，最大价值为 0。

代码示例

N, V = map(int, input().split())
dp = [[0] * (V + 1) for _ in range(N + 1)]
for i in range(1, N + 1):v, w = map(int, input().split())for j in range(1, V + 1):dp[i][j] = dp[i - 1][j]if j >= v:dp[i][j] = max(dp[i][j], dp[i - 1][j - v] + w)
print(dp[N][V])

结果展示

相关文章：

蓝桥杯刷题第二天——背包问题

题目描述 有N件物品和一个容量是V的背包。每件物品只能使用一次。第i件物品的体积是Vi价值是Wi。 求解将哪些物品装入背包&#xff0c;可使这些物品的总体积不超过背包容量&#xff0c;且总价值最大。 输出最大价值。 输入格式 第一行两个整数&#xff0c;N&#xff0c;V&am…...

编程日记 2025/6/4 4:44:01

DM达梦启用及收集AWR报告

1.创建DBMS_WORKLOAD_REPOSITORY系统包 查看DBMS_WORKLOAD_REPOSITORY系统包启用状态 SQL> SELECT SF_CHECK_AWR_SYS;LINEID SF_CHECK_AWR_SYS ---------- ---------------- 1 0SF_CHECK_AWR_SYS 返回值 0&#xff1a;未启用&#xff1b;1&#xff1a;已启…...

编程日记 2025/6/4 9:38:45

【git】如何删除本地分支和远程分支？

1.如何在 Git 中删除本地分支 本地分支是您本地机器上的分支&#xff0c;不会影响任何远程分支。 &#xff08;1&#xff09;在 Git 中删除本地分支 git branch -d local_branch_name git branch 是在本地删除分支的命令。-d是一个标志&#xff0c;是命令的一个选项&#x…...

编程日记 2025/6/1 8:29:53

pix2pix mmgeneration通用场景黑白图片上色模型训练，Docker

https://www.dong-blog.fun/post/1924 对于机器学习和深度学习感兴趣的读者来说，OpenMMLab 提供的 MMGeneration 库是一个绝佳的选择。最近我在阅读一篇关于 MMGeneration 的博客文章，尤其是在使用 Docker 环境进行模型和算法测试方面，受益匪浅。以下是我对目标博客内容的概…...

编程日记 2025/6/3 16:12:35

【Redis入门到精通六】在Spring Boot中集成Redis（含配置和操作演示）

目录 Spring Boot中集成Redis 1.项目创建和环境配置 2.基本操作演示 Spring Boot中集成Redis Spring社区也自定义了一套Redis的客户端&#xff0c;与jedis的操作方式有所差异&#xff0c;Spring中把每个类型的操作都单独封装了起来。下面就让我来带大家了解如何在Spring Bo…...

编程日记 2025/6/3 13:59:10

js使用qrcode与canvas生成带logo的二维码

qrcode库 文档 https://www.npmjs.com/package/qrcode 安装 npm i qrcode 使用 errorCorrectionLevel: H // 容错率&#xff08;H是最高&#xff0c;其它看文档&#xff09; width: 200 // 大小 margin: 2 // 边距 import QRCode from qrcodeconst testFn async () > {c…...

编程日记 2025/5/29 21:45:48

【STM32】LED状态翻转函数

1.利用状态标志位控制LED状态翻转 在平常编写LED状态翻转函数时&#xff0c;通常利用状态标志位实现LED状态的翻转。如下所示&#xff1a; unsigned char led_turn_flag; //LED状态标志位&#xff0c;1-点亮&#xff0c;0-熄灭/***************************************函…...

编程日记 2025/5/28 3:44:07

FreeRTOS 简介

FreeRTOS 是一个小型、实时操作系统内核&#xff0c;专为嵌入式设备设计。它支持多任务操作、任务优先级、互斥机制和队列管理&#xff0c;是轻量级嵌入式开发中的热门选择。以下是其主要特点&#xff1a; 特点 实时性能&#xff1a;提供确定性的任务调度&#xff0c;适用于对…...

编程日记 2025/6/3 8:03:17

Java并发编程中的synchronized和volatile：用途解析与使用场景

目录 一、synchronized关键字&#xff1a;互斥与同步的保障 二、volatile关键字&#xff1a;轻量级的变量可见性保证 三、synchronized与volatile的区别与选择 四、总结 在Java并发编程中&#xff0c;synchronized和volatile是两个非常重要的关键字&#xff0c;它们在多线程…...

编程日记 2025/6/3 18:05:19

将 AzureBlob 的日志通过 Azure Event Hubs 发给 Elasticsearch（1）

问题 项目里使用了 AzureBlob 存储了用户上传的各种资源文件&#xff0c;近期 AzureBlob 的流量费用增长很快&#xff0c;想通过分析Blob的日志&#xff0c;获取一些可用的信息&#xff0c;所以有了这个需求&#xff1a;将存储账户的日志&#xff08;读写&#xff0c;审计&…...

编程日记 2025/6/3 15:27:07

程序设计：排版、检验报告的上下标解决几种办法

【啰嗦两句】 本文重点在于提供几个针对排版文档、各种检验报告系统等程序设计时&#xff0c;遇到的上下标录入、绘制展示等问题的应对办法&#xff0c;但是准确地说&#xff0c;并没有非常优秀的方案。 【上下标难题】 一般的行业或许对上下标并没有严格要求&#xff0c;多数…...

编程日记 2025/6/2 13:58:04

【2024年华为OD机试】 (C卷,100分)- 求字符串中所有整数的最小和（Java JS PythonC/C++）

一、问题描述 题目解析 题目描述 输入字符串 s&#xff0c;输出 s 中包含所有整数的最小和。 说明 字符串 s 只包含 a-z、A-Z、、-。合法的整数包括&#xff1a; 正整数&#xff1a;一个或多个 0-9 组成&#xff0c;如 0、2、3、002、102。负整数&#xff1a;负号 - 开头&…...

编程日记 2025/6/3 4:13:58

MBox20网关：数字化工厂的智能加速器

在当今这个日新月异的数字化时代&#xff0c;企业对于生产效率、数据管理和网络安全的追求已经达到了前所未有的高度。特别是在制造业领域&#xff0c;随着“工业4.0”和“智能制造”概念的深入实践&#xff0c;数字化工厂已成为产业升级的必然趋势。在这场深刻的变革中&#x…...

编程日记 2025/5/29 6:40:04

NodeJS | 搭建本地/公网服务器 live-server 的使用与安装

目录 介绍 安装 live-server 安装方法 安装后的验证 环境变量问题 Node.js 环境变量未配置正确 全局安装的 live-server 路径未添加到环境变量 运行测试 默认访问主界面 访问文件 报错信息与解决 问题一&#xff1a;未知命令 问题二&#xff1a;拒绝脚本 公网配置…...

编程日记 2025/6/4 1:49:52

用C++实现一个基于模板的观察者设计模式

观察者模式 定义 观察者模式（Observer Pattern）是一种行为型设计模式，用于定义对象间的一对多依赖关系，使得当一个对象状态发生变化时，其所有依赖它的对象都会收到通知并自动更新。 核心概念 角色定义 Subject（被观察者）： 持有观察者列表，维护观察者的注册和移除。 …...

编程日记 2025/6/2 13:54:05

LabVIEW开发X光图像的边缘检测

在医疗影像处理中&#xff0c;X光图像的分析对于骨折、肿瘤等病变的检测非常重要。X光图像中包含许多关键信息&#xff0c;然而&#xff0c;由于图像噪声的干扰&#xff0c;直接从图像中提取有用的特征&#xff08;如骨折的边缘&#xff09;变得非常困难。边缘检测作为图像处理…...

编程日记 2025/6/4 16:12:20

GitEE

版本控制 cvs svn git 等等 一、团队开发过程中的问题 1、备份【Release】 2、代码还原 3、协同修改 4、多版本文件管理 5、追溯问题代码的编写人和编写时间 6、权限控制 二、版本控制 版本控制就是维护工程蓝图标准做法&#xff0c;能追踪工程蓝图从诞生一直到定案的过程…...

编程日记 2025/6/3 12:53:21

Ubuntu配置python环境

前言 Ubuntu22.04自带python3&#xff0c;仅需要安装pip3即可。 也可以安装Anaconda使用虚拟环境。 本地Python环境 查看python3是否已安装&#xff1a; python3 -V若已安装python3&#xff0c;继续安装pip3&#xff1a; sudo apt install python3-pip查看pip版本&#xf…...

编程日记 2025/5/30 3:58:21

数据库的DML

1.insert 数据库于表创建成功后&#xff0c;需要向数据库的表中插入数据。在MySQL中可以使用insert语句向数据库已有的表中插入一行或者多行元组数据 基本语法&#xff1a; insert 语句有两种语法形式&#xff0c;分别是insert…values语句和insert…set语句 insert into&l…...

编程日记 2025/6/1 19:24:18

什么是SSL及SSL的工作流程

什么是 SSL SSL（Secure Sockets Layer，安全套接层）是一种保护互联网通信安全的加密协议，用于确保数据在客户端和服务器之间传输时的保密性、完整性和身份验证。它已被TLS（Transport Layer Security，传输层安全协议）取代，但很多场景仍习惯称其为SSL。 SSL/TLS 的主要目…...

编程日记 2025/6/3 10:27:09

RabbitMQ---消息确认和持久化

&#xff08;一&#xff09;消息确认 1.概念 生产者发送消息后&#xff0c;到达消费端会有以下情况&#xff1a; 1.消息处理成功 2.消息处理异常 如果RabbitMQ把消息发送给消费者后就把消息删除&#xff0c;那么就可能会导致&#xff0c;消息处理异常想要再获取这条消息的时…...

编程日记 2025/6/4 6:11:46

4 AXI USER IP

前言 使用AXI Interface封装IP&#xff0c;并使用AXI Interface实现对IP内部寄存器进行读写实现控制LED的demo&#xff0c;这个demo是非常必要的&#xff0c;因为在前面的笔记中基本都需哟PS端与PL端就行通信互相交互&#xff0c;在PL端可以通过中断的形式来告知PS端一些事情&…...

编程日记 2025/6/4 1:49:56

windows下安装并使用node.js

一、下载Node.js 选择对应你系统的Node.js版本下载 Node.js官网下载地址 Node.js中文网下载地址??? 这里我选择的是Windows64位系统的Node.js20.18.0&#xff08;LTS长期支持版本&#xff09;版本的.msi安装包程序 官网下载&#xff1a; 中文网下载&#xff1a; 二、安…...

编程日记 2025/5/30 14:29:13

【报错解决】Sql server 2022连接数据库时显示证书链是由不受信任的颁发机构颁发的

SSMS 20在连接Sql server 2022数据库时有如下报错&#xff1a; A connection was successfully established with the server, but then an error occurred during the login process. (provider: SSL Provider, error: 0 - 证书链是由不受信任的颁发机构颁发的。 原因是尝试使…...

编程日记 2025/4/29 7:52:27

VSCode 的部署

一、VSCode部署 (1)、简介 vsCode 全称 Visual Studio Code&#xff0c;是微软出的一款轻量级代码编辑器&#xff0c;免费、开源而且功能强大。它支持几乎所有主流的程序语言的语法高亮、智能代码补全、自定义热键、括号匹配、代码片段、代码对比Diff、版本管理GIT等特性&…...

编程日记 2025/5/30 15:53:01

淘宝、京东联盟数字ID转加密ID接口

该接口可以将主站的数字ID转换为加密ID 例如&#xff1a;123456789 转换为 xxxxxxxxxx-xxxxxxxxx PHP示例 // 接口地址&#xff1a;https://www.haodanku.com/openapi/api_detail?id103 $app_secret 你的appSecret, //替换成自己的 $x [app_id > 你的appid, //替换成…...

编程日记 2025/5/30 18:04:33

【物联网】keil仿真环境设置 keilV5可以适用ARM7

文章目录 一、ARM指令模拟器环境搭建1. keil软件2. Legacy Support 二、Keil仿真环境设置1. 创建一个项目2. 编译器介绍(1)arm-none-eabi-gcc(2)arm-none-linux-gnueabi-gcc(3)arm-eabi-gcc(4)grmcc(5)aarch64-linux-gnu-gcc 3. 安装编译器(1)设置调试 一、ARM指令模拟器环境搭…...

编程日记 2025/5/20 4:09:05

Oracle 可观测最佳实践

简介 Oracle 数据库是一种广泛使用的商业关系数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;由甲骨文公司&#xff08;Oracle Corporation&#xff09;开发。它支持 SQL 语言&#xff0c;能够存储和管理大量数据&#xff0c;并提供高级数据管理功能&#xff0c;如数…...

编程日记 2025/5/31 0:54:38

上传自己的镜像到docker hub详细教程

上传自己的镜像到docker hub详细教程 本博客通B站视频一致&#xff1a; 上传自己的镜像到docker hub详细教程 1. 登录自己的hub.docker.com的账号 docker hub仓库 2. 点击Repositories&#xff0c;跳转到创建仓库页面 3. 点击Create a repository 创建repository&#xff0c…...

编程日记 2025/6/2 7:12:30

Python猜数小游戏

Python 实现的《猜数游戏》 介绍 本文将展示如何使用 Python 编写一个简单的《猜数游戏》。这个游戏将会生成一个1到10之间的随机数&#xff0c;用户有最多三次机会来猜测正确的数字。如果用户猜对了&#xff0c;游戏将结束并显示恭喜信息&#xff1b;如果没有猜对&#xff0…...

编程日记 2025/5/29 4:40:57

HackMyVM-Klim靶机的测试报告

目录 一、测试环境 1、系统环境 2、使用工具/软件 二、测试目的 三、操作过程 1、信息搜集 2、Getshell 3、提权 CVE-2008-0166 四、结论 一、测试环境 1、系统环境 渗透机&#xff1a;kali2021.1(192.168.159.127) 靶 机&#xff1a;debian(192.168.159.27) 注意事…...

编程日记 2025/6/1 19:23:31

MySQL中大量数据优化方案

文章目录 1 大量数据优化1.1 引言1.2 评估表数据体量1.2.1 表容量1.2.2 磁盘空间1.2.3 实例容量 1.3 出现问题的原因1.4 解决问题1.4.1 数据表分区1.4.1.1 简介1.4.1.2 分区限制和执行计划1.4.1.3 分区表的索引1.4.1.4 为什么分区键必须是主键的一部分1.4.1.5 操作分区1.4.1.5.…...

编程日记 2025/6/1 19:22:57

春秋杯-WEB

SSTI 可以看到主页那里有个登录测试之后为ssti {{4*4}} fenjing梭哈即可得到payload {{((g.pop.__globals__.__builtins__.__import__(os)).popen(cat flag)).read()}}file_copy 看到题目名字为file_copy&#xff0c; 当输入路径时会返回目标文件的大小&#xff0c; 通…...

编程日记 2025/6/1 14:54:17

C++多态的认识与理解

多态的定义 多态其实就是同一操作在不同的对象上可以有不同的实现方式。 多态的类型 多态分为静态多态和动态多态两种&#xff0c;而静态多态其实我们之前就了解过&#xff0c;今天主要是讲解一下动态多态。 静态多态&#xff08;编译时多态&#xff09;:静态多态其实就是在…...

编程日记 2025/6/4 9:21:18

improve-gantt-elastic（vue2中甘特图实现与引入）

1.前言 项目开发中需要使用甘特图展示项目实施进度&#xff0c;左侧为表格计划&#xff0c;右侧为图表进度展示。wl-gantt-mater&#xff0c;dhtmlx尝试使用过可拓展性受到限制。gantt-elastic相对简单&#xff0c;可操作性强&#xff0c;基础版本免费。 甘特图&#xff08;Gan…...

编程日记 2025/6/4 16:00:50

模型 笛卡尔思维

系列文章分享模型&#xff0c;了解更多&#x1f449; 模型_思维模型目录。怀疑一切&#xff0c;分析整合&#xff0c;验证真理。 1 笛卡尔思维模型的应用 1.1 笛卡尔思维模型在城市规划中的应用 背景&#xff1a;某城市计划进行新的城市规划&#xff0c;以提高城市的可持续性…...

编程日记 2025/6/4 13:22:34

LabVIEW桥接传感器数据采集与校准程序

该程序设计用于采集来自桥接传感器的数据&#xff0c;执行必要的设置&#xff08;如桥接配置、信号采集参数、时间与触发设置&#xff09;&#xff0c;并进行适当的标定和偏移校正&#xff0c;最终通过图表呈现采集到的数据信息。程序包括多个模块&#xff0c;用于配置通道、触…...

编程日记 2025/6/1 14:09:54

无人机技术架构剖析！

一、飞机平台系统 飞机平台系统是无人机飞行的主体平台&#xff0c;主要提供飞行能力和装载功能。它由机体结构、动力装置、电气设备等组成。 机体结构&#xff1a;无人机的机身是其核心结构&#xff0c;承载着其他各个组件并提供稳定性。常见的机身材料包括碳纤维、铝合金、…...

编程日记 2025/6/4 3:29:26

飞牛 使用docker部署Watchtower 自动更新 Docker 容器

Watchtower是一款开源的Docker容器管理工具&#xff0c;其主要功能在于自动更新运行中的Docker容器 Watchtower 支持以下功能&#xff1a; 自动拉取镜像并更新容器。 配置邮件通知。 定时执行容器更新任务。 compose搭建Watchtower 1、新建文件夹 先在任意位置创建一个 w…...

编程日记 2025/6/3 10:39:35

【Flink系列】4. Flink运行时架构

4. Flink运行时架构 4.1 系统架构 Flink运行时架构——Standalone会话模式为例 1&#xff09;作业管理器&#xff08;JobManager&#xff09; JobManager是一个Flink集群中任务管理和调度的核心&#xff0c;是控制应用执行的主进程。也就是说&#xff0c;每个应用都应该被…...

编程日记 2025/6/2 7:05:45

【机器学习实战入门】使用Pandas和OpenCV进行颜色检测

Python 颜色检测项目 今天的项目将非常有趣和令人兴奋。我们将与颜色打交道&#xff0c;并在项目过程中学习许多概念。颜色检测对于识别物体来说是必要的&#xff0c;它也被用作各种图像编辑和绘图应用的工具。 什么是颜色检测&#xff1f; 颜色检测是检测任何颜色名称的过程…...

编程日记 2025/6/3 5:12:17

C++ K2 （2）

提示&#xff1a;文章 文章目录 前言一、背景标准库基础知识堆栈 总结 前言 前期疑问&#xff1a; 本文目标&#xff1a; 一、背景 接上文 标准库 1、&#xff08;单选&#xff09;【STL】在以下容器中间插入一个元素&#xff0c;时间复杂度为O(1)的是&#xff08;A&#x…...

编程日记 2025/6/2 7:00:27

【React】静态组件动态组件

目录 静态组件动态组件创建一个构造函数(类)使用 class 实现组件**使用 function 实现类组件** 静态组件 函数组件是静态组件&#xff1a; 组件第一次渲染完毕后&#xff0c;无法基于内部的某些操作让组件更新「无法实现自更新」&#xff1b;但是&#xff0c;如果调用它的父组…...

编程日记 2025/6/4 7:22:13

Spring Web MVC综合案例

承接上篇文章——Spring Web MVC探秘&#xff0c;在了解Spring Web MVC背后的工作机制之后&#xff0c;我们接下来通过三个实战项目&#xff0c;来进一步巩固一下前面的知识。 一、计算器 效果展示&#xff1a;访问路径&#xff1a;http://127.0.0.1:8080/calc.html 前端代码&a…...

编程日记 2025/5/31 0:52:53

OpenCV相机标定与3D重建(60)用于立体校正的函数stereoRectify()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 为已校准的立体相机的每个头计算校正变换。 cv::stereoRectify 是 OpenCV 中用于立体校正的函数&#xff0c;它基于已知的相机参数和相对位置&am…...

编程日记 2025/6/3 3:15:41

SDL2基本的绘制流程与步骤

SDL2（Simple DirectMedia Layer 2）是一个跨平台的多媒体库，它为游戏开发和图形应用提供了一个简单的接口，允许程序直接访问音频、键盘、鼠标、硬件加速的渲染等功能。在 SDL2 中，屏幕绘制的流程通常涉及到窗口的创建、渲染目标的设置、图像的绘制、事件的处理等几个步骤。…...

编程日记 2025/6/3 9:06:43

计算机网络 （42）远程终端协议TELNET

前言 Telnet&#xff08;Telecommunication Network Protocol&#xff09;是一种网络协议&#xff0c;属于TCP/IP协议族&#xff0c;主要用于提供远程登录服务。 一、概述 Telnet协议是一种远程终端协议&#xff0c;它允许用户通过终端仿真器连接到远程主机&#xff0c;并在远程…...

编程日记 2025/6/2 3:09:53

重拾Python学习，先从把python删除开始。。。

自己折腾就是不行啊&#xff0c;屡战屡败&#xff0c;最近终于找到前辈教我 第一步 删除Python 先把前阵子折腾的WSL和VScode删掉。还是得用spyder&#xff0c;跟matlab最像&#xff0c;也最容易入手。 从VScode上搞python&#xff0c;最后安装到appdata上&#xff0c;安装插…...

编程日记 2025/5/27 10:18:03

51c大模型~合集106

我自己的原文哦~ https://blog.51cto.com/whaosoft/13115290 #GPT-5、 Opus 3.5为何迟迟不发 新猜想&#xff1a;已诞生&#xff0c;被蒸馏成小模型来卖 「从现在开始&#xff0c;基础模型可能在后台运行&#xff0c;让其他模型能够完成它们自己无法完成的壮举——就像一个老…...

编程日记 2025/6/4 15:15:23

node安装教程及环境配置

1.下载安装包 下载的网址&#xff1a;Node.js — Download Node.js 根据自己电脑系统及位数选择&#xff0c;电脑是Windows系统、64位、想下载稳定版的.msi&#xff08;LTS为长期稳定版&#xff09;这里选择windows64位.msi格式安装包。 .msi和.zip格式区别&#xff1a; .msi…...

编程日记 2025/6/4 16:45:47