01背包(换汤不换药)
链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
有一个箱子容量为V(正整数,0 ≤ V ≤ 20000),同时有n个物品(0<n ≤ 30),每个物品有一个体积(正整数)。
要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。
分析:
不还是01背包求最大价值嘛,只是每个物体的价值与所占体积一样。
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve()
{ll v;cin>>v;ll n;cin>>n;ll dp[v+1];memset(dp,0,sizeof dp);ll a[n+1];for(ll i=1;i<=n;i++)cin>>a[i];for(ll i=1;i<=n;i++){for(ll j=v;j>=a[i];j--){dp[j]=max(dp[j],dp[j-a[i]]+a[i]);}}cout<<v-dp[v]<<'\n';
}int main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll t=1;while(t--)solve();return 0;}
相关文章:
01背包(换汤不换药)
链接:登录—专业IT笔试面试备考平台_牛客网 来源:牛客网 有一个箱子容量为V(正整数,0 ≤ V ≤ 20000),同时有n个物品(0<n ≤ 30),每个物品有一个体积…...
c++ folly::baton
Baton folly::Baton 是 Facebook 开源的一个同步原语,它提供了一种简单而灵活的方式来进行线程间的同步。它属于 Folly 库,是 C 编程语言的一个组件。 Baton 通常用作线程间同步、等待、通知的标识符号,常用姿势是,一些线程调用…...
05.sqlite3学习——DML(数据管理:插入、更新、删除)
目录 DML(数据管理:插入、更新、删除) 插入 更新 删除整个表 语法 实例 DML(数据管理:插入、更新、删除) 数据操纵(DML):用于增、删、改数据 作用:负…...
Netty-ChannelPipeline
EventLoop可以说是 Netty 的调度中心,负责监听多种事件类型:I/O 事件、信号事件、定时事件等,然而实际的业务处理逻辑则是由 ChannelPipeline 中所定义的 ChannelHandler 完成的,ChannelPipeline 和 ChannelHandler应用开发的过程…...
从入门到精通,30天带你学会C++【第六天:与或非三兄弟和If判断语句(博主目前最长文章,2514字)】(学不会你找我)
目录 前言 计算机里的真和假 与或非三兄弟 编辑与运算(&&) 具体说明表格: 举个栗子1: 或运算(||) 具体说明表格: 举个栗子2: 非运算(!)…...
如何快速找出占用空间最大的文件?
分析&回答 使用 find 命令找到大于指定大小的文件: 当前目录大于500M文件 find ./ -size 500M用户目录大于500M文件 find ~ -type f -size 500M根目录大于500M文件 find / -type f -size 500M 复制代码 让文件按大小排序 du -h * | sort -n 喵呜面试助手&am…...
算法:分治思想处理归并递归问题
文章目录 算法原理实现思路典型例题排序数组数组中的逆序对计算右侧小于当前元素的个数 总结 算法原理 利用归并思想进行分治也是很重要的一种思路,在解决逆序对的问题上有很大的需求空间 于是首先归并排序是首先的,归并排序要能写出来: c…...
小白学Go 基础02-了解Go语言的诞生与演进
Go语言诞生于何时?它的最初设计者是谁?它为什么被命名为Go?它的设计目标是什么?它如今发展得怎么样?带着这些问题,我们一起穿越时空,回到2007年9月Go语言诞生的那一历史时刻吧。 Go语言的诞生 …...
python中如何将十进制转成二进制
python中如何将十进制转成二进制 在 Python 中,你可以使用内置的 bin() 函数将十进制数转换为二进制表示形式。以下是使用 bin() 函数进行转换的示例: decimal_number 10binary_number bin(decimal_number)print(binary_number) # 输出:…...
数据结构--5.0.1图的存储结构
目录 一、邻接矩阵(无向图) 二、邻接矩阵(有向图) 三、邻接矩阵(网) 四、邻接表(无向图) 五、邻接表(有向图) ——图的存储结构相比较线性表与树来说就复…...
解决win10 wsl子系统安装的ubuntu环境中lsof,netstat命令查看端口没有任何输出的问题
最近有个以前的ssm项目需要在新电脑上运行测试一下,发现需要redis环境,看了官网说:有两种选择: 1. 要么在虚拟机比如vmware安装linux基础环境,然后再安装redis 2. 要么可以利用win10的wsl linux子系统安装ubuntu&…...
【OpenFeign】OpenFeign结合Hystrix和Sentinel实现熔断降级
OpenFeign可以与Hystrix和Sentinel结合使用,实现降级和熔断。 OpenFeign与Hystrix结合使用 使用OpenFeign需要引入OpenFeign的依赖: <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-sta…...
软件工程(十) 需求工程之需求开发与管理
前面我们学习到了需求工程的概念与分类,我们知道了需求工程主要分为需求开发和需求管理,但是没有说明到底该如何开发需求,有哪些方法去开发需求。到底该如何进行需求管理,又有哪些进行需求管理的方式。具体是如何去做的。下面我们将会详细进行描述。 1、需求开发 1.1、需…...
C++网狐服务器引入开源日志库spdlog
很多人对日志库不以为然,包括网狐这种十几年的公司都不重视,其实日志库记录的东西能在线上出问题时高效解决,特别是别人写的东西,人又走了,出了问题,还可以用日志分析快速解决。要是没有日志记录࿰…...
【C++】—— c++11之智能指针
前言: 本期,我们将要学习的是在c11中新提出的概念——异常指针! 目录 (一)智能指针的引入 (二)内存泄漏 1、什么是内存泄漏,内存泄漏的危害 2、内存泄漏分类(了解&a…...
html5——前端笔记
html 一、html51.1、理解html结构1.2、h1 - h6 (标题标签)1.3、p (段落和换行标签)1.4、br 换行标签1.5、文本格式化1.6、div 和 span 标签1.7、img 图像标签1.8、a 超链接标签1.9、table表格标签1.9.1、表格标签1.9.2、表格结构标签1.9.3、合并单元格 1.10、列表1.10.1、ul无序…...
如何在 Vue TypeScript 项目使用 emits 事件
Vue是构建出色的Web应用程序的最灵活、灵活和强大的JavaScript框架之一。Vue中最重要的概念和关键特性之一是能够促进应用程序组件之间的通信。让我们深入探讨一下Vue中的“emits”概念,并了解它们如何以流畅和无缝的方式实现父子组件之间的通信。 Vue中的emits是什…...
文件操作 黑马教程(04)
1.文本文件 写文件 #include "iostream" #include "fstream" using namespace std; /** 文件操作** 程序运行时产生的数据都属于临时数据,程序一旦结束都会被释放* 通过文件可以将数据持久化* C中对文件操作需要包含头文件<fstream>** 文…...
Jmeter(二十七):BeanShell PostProcessor跨线程全局变量使用
在性能测试中,两个相关联的接口不一定都在同一个线程组,遇见这种情况时,我们要进行跨线程组传参,此处用登录和查询配送单两个请求举例; 1、登录请求中配置json提取器,将接口返回的token保存在变量中&#…...
手写表格OCR识别并与大模型ChatGPT交互?
这是一张手写表格,姓名做了脱敏处理。现在需要对其识别,并分析。 直接粘贴剪切板中的表格原始图片,在网页中ctlV进行识别。识别结果列用分隔符|,可以直接粘贴到excel,进行数据列分隔。为了美观期间,也可以用…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
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> …...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
