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

0/1背包问题

例题HDU-2602

Problem Description
Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?
Input
The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
Output
One integer per line representing the maximum of the total value (this number will be less than 231).
Sample Input
1
5 10
1 2 3 4 5
5 4 3 2 1
Sample Output
14

二维数组dp[][]

以下是代码

#include<vector>
#include<iostream>
using namespace std;int maxBoneValue(int n,int V,vector<int>& value,vector<int>& volumes)
{vector<vector<int>> dp(n+1,vector<int>(V+1,0));//i表示前i个骨头for(int i = 1;i<=n;i++){//j代表当前背包的容量,当j=0时,意味着背包的容量为0//dp[i][0]都是0,当我们数组初始化时,已经隐含了j=0的情况,所以从1开始for(int j= 1;j<=V;j++){//不选这个骨头,如果装不下if(j<volumes[i-1]){//这个判断 j < volumes[i-1] 是为了检查当前的背包容量 j 是否足够来装下第 i 个骨头。//volumes[i-1] 是第 i 个骨头的体积(因为数组是从0开始的,所以第 i 个骨头的体积在 volumes 数组中的索引是 i-1)    //j代表当前背包容量  dp[i][j] = dp[i-1][j];}else{//考虑这个骨头情况dp[i]

相关文章:

0/1背包问题

例题HDU-2602 Problem Description Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave … The bone collector had a big bag wi…...

Redis入门到精通——00数据类型

1、String 1.1、介绍 String 是最基本的 key-value 结构&#xff0c;key 是唯一标识&#xff0c;value 是具体的值&#xff0c;value其实不仅是字符串&#xff0c; 也可以是数字&#xff08;整数或浮点数&#xff09;&#xff0c;value 最多可以容纳的数据长度是 512M 1.2、…...

PADS9.5使用记录

目录 一、概述 二、PADS Logic IN4148二极管封装 SOD-123封装 SOD-323封装 SOD-523封装 2N3904 1AM 三极管封装 78L05 7533-1 一、概述 PADS Logic 原理图绘制PADS Layout PCB 封装设计PADS Router 布线 二、PADS Logic …...

Axios post请求出现500错误

笔者在编写前端form表单传后端数据的时候&#xff0c;出现了以下问题 一、问题场景 当我用axios发送post请求的时候&#xff0c;出现了500错误 笔者找了很长时间错误&#xff0c;代码没问题&#xff0c;后端接口也没问题&#xff0c;后来发现问题出在实体类上了 当前端post请…...

【Leetcode】171.Excel 表列序号

一、题目 1、题目描述 给你一个字符串 columnTitle ,表示 Excel 表格中的列名称。返回 该列名称对应的列序号 。 例如: A -> 1 B -> 2 C -> 3 … Z -> 26 AA -> 27 AB -> 28 … 示例1: 输入: columnTitle = "A" 输出: 1示例2: 输入: colu…...

2023湖南省赛游记/题解

省赛拖了大哥们的后腿&#xff0c;感觉随便补个正常一队水平的人&#xff0c;我们一队肯定能AK。只能说自己真的菜&#xff0c;全程帮不上什么忙&#xff0c;还负贡献&#xff0c;真的想笑 B 暴力sg #include <bits/stdc.h> #define ll long long #define ull unsigned…...

海信电视U8KL使用体验:参数卷,画质技术也独有!

每个家庭成员对电视都有不同需求&#xff0c;如何能做到兼顾&#xff1f;看似需求众口难调&#xff0c;其实一台海信电视就能满足所有啦。 海信电视的参数不仅是最卷的&#xff0c;同时画质技术还是国内独有的&#xff0c;能把这样一台优秀的电视搬回家&#xff0c;无论电影、…...

E. Mishap in Club

题目&#xff1a; 样例1&#xff1a; 输入 --输出 1 样例2&#xff1a; 输入 --- 输出 3 思路&#xff1a; 数学贪心模拟思路&#xff0c;由于不知道在俱乐部的人数和在外面的人数&#xff0c;又要尽可能少的人数&#xff0c;那么定义两个变量&#xff0c;一个是里面的人数 i…...

UE4 自带体积云应用

新建空关卡 点击该选项 全部点击一遍 拖进场景...

RTP/RTCP 协议讲解

文章目录 前言一、RTP 协议1、RTP 协议概述2、RTP 工作机制3、RTP 协议的报文结构4、wireshark 抓取 RTP 报文 二、RTCP 协议1、RTCP 协议概述2、RTCP 工作机制3、RTCP 数据报4、wireshark 抓取 RTCP 报文 三、RTSP 和 RTP 的关系四、易混淆概念1、RTP over UDP 和 RTP over RT…...

倒计时15天!百度世界2023抢先看

近日消息&#xff0c;在10月17日即将举办的百度世界2023上&#xff0c;百度创始人、董事长兼首席执行官李彦宏将带来主题演讲&#xff0c;“手把手教你做AI原生应用”。 增设社会报名&#xff0c;有机会获得精美伴手礼 目前&#xff0c;百度世界大会已经开放公众参会报名&…...

Redis 哈希(Hash)数据类型和命令(数据类型 二)

基本概念 Hash是一个键值对的集合&#xff0c;其中每个键都是唯一的。每个键都可以关联多个字段和值&#xff0c;这使得Hash非常适合存储对象或结构化数据。 常用命令 存储、获取、删除&#xff1a;hset、hget、hdel # 添加键为name值为lin hset student name lin # 获取 h…...

[Linux]线程互斥

[Linux]线程互斥 文章目录 [Linux]线程互斥线程并发访问问题线程互斥控制--加锁pthread_mutex_init函数pthread_mutex_destroy函数pthread_mutex_lock函数pthread_mutex_unlock函数锁相关函数使用示例使用锁的细节加锁解锁的实现原理 线程安全概念常见的线程不安全的情况常见的…...

leetcode-239-滑动窗口最大值

题意描述&#xff1a; 给你一个整数数组 nums&#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例&#xff1a; 输入&#xff1a;nums [1,3,-1,…...

基于大语言模型的智能问答系统应该包含哪些环节?

一个完整的基于 LLM 的端到端问答系统&#xff0c;应该包括用户输入检验、问题分流、模型响应、回答质量评估、Prompt 迭代、回归测试&#xff0c;随着规模增大&#xff0c;围绕 Prompt 的版本管理、自动化测试和安全防护也是重要的话题&#xff0c;本篇文章就来探索下这个过程…...

【Cesium创造属于你的地球】相机系统

相机系统里面有setView&#xff0c;flyTo&#xff0c;lookAt&#xff0c;viewBoundingsphere这几种方法&#xff0c;以下是相关的使用方法&#xff0c;学起来&#xff01;&#xff01;&#xff01; setView 该方法可以直接切换相机视口&#xff0c;从而不需要通过一个飞入的效…...

运维困局下确保系统稳定的可行性

业务高速发展背后的困局 随着业务的快速发展&#xff0c;运维体系也逐步的完善起来。业务的稳定性和服务质量也在监控、可用性等体系的相互环抱下健康地成长。所有的问题、故障及影响稳定性的因素都在可控、可收敛的范围内&#xff0c;一切都向着好的方向发展。 这一切的背后…...

springmvc中DispatcherServlet关键对象

以下代码为 spring boot 2.7.15 中自带的 spring 5.3.29 RequestMappingInfo 请求方法相关信息封装&#xff0c;对应的信息解析在 RequestMappingHandlerMapping 的 createRequestMappingInfo() 中实现。 对于 RequestMapping 赋值的相关信息进行解析 protected RequestMappi…...

某微e-office协同管理系统存在任意文件读取漏洞复现 CNVD-2022-07603

目录 1.漏洞概述 2.影响版本 3.漏洞等级 4.漏洞复现 5.Nuclei自动化扫描POC 某微e-office协同管理系统存在任意文件读取漏洞分析 CNVD-2022-07603https://blog.csdn.net/qq_41490561/article/details/133469649...

消息驱动 —— SpringCloud Stream

Stream 简介 Spring Cloud Stream 是用于构建消息驱动的微服务应用程序的框架&#xff0c;提供了多种中间件的合理配置 Spring Cloud Stream 包含以下核心概念&#xff1a; Destination Binders&#xff1a;目标绑定器&#xff0c;目标指的是 Kafka 或者 RabbitMQ&#xff0…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...