01背包(换汤不换药)

news/2024/12/23 17:06:30/

链接:登录—专业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;}


http://www.ppmy.cn/news/1080731.html

相关文章

CCF-CSP 30次 第二题【矩阵运算】

计算机软件能力认证考试系统 #include<bits/stdc.h> using namespace std; const int N1e410; #define int long long int n,d; int q[N][22],k[22][N],v[N][22],w[N]; int ans1[N][22],ans2[N][22]; signed main() {scanf("%lld %lld",&n,&d);for(in…

MQTT异常掉线原因

一、业务场景 我们在使用MQTT协议的时候&#xff0c;有些伙伴可能会遇到MQTT客户端频繁掉线、上线问题 二、原因分析及异常处理 1.原因&#xff1a;使用相同的clientID 方案&#xff1a;全局使用的clientID保证唯一性&#xff0c;可以采用UUID等方式 2.原因: 当前用户没有Top…

解决小程序中textarea ios端样式不兼容的方法

问题描述 &#xff0c;今天在调试小程序的时候有个需求需要textarea与标题对其&#xff0c;微信开发工具和安卓系统都没有问题 但是ios系统textarea存在内边距。出现不兼容的情况 解决方法&#xff1a;我们看官网的textarea的属性 textarea | uni-app官网 disable-default-p…

CVE-2023-25157:GeoServer OGC Filter SQL注入漏洞复现

CVE-2023-25157&#xff1a;GeoServer OGC Filter SQL注入漏洞复现 前言 本次测试仅供学习使用&#xff0c;如若非法他用&#xff0c;与本文作者无关&#xff0c;需自行负责&#xff01;&#xff01;&#xff01; 一.GeoServer简介 GeoServer 是用 Java 编写的开源软件服务…

Django传递dataframe对象到前端网页

在django前端页面上展示的数据&#xff0c;还是使用django模板自带的语法 方式1 不推荐使用 直接使用 【df.to_html(indexFalse)】 使用to_html他会生成一个最基本的表格没有任何的样式&#xff0c;一点都不好看&#xff0c;如果有需要的话可以自行修改表格的样式&#xff0c;…

前端面试中Vue的有经典面试题二

7. Vue中给data中的对象属性添加一个新的属性时会发生什么&#xff0c;如何解决&#xff1f; 示例&#xff1a; 点击button会发现&#xff0c; obj.b 已经成功添加&#xff0c;但是视图并未刷新&#xff1a; 原因在于在Vue实例创建时&#xff0c; obj.b 并未声明&#xff0c;因…

HTTP协议概述

HTTP 协议定义 HTTP协议&#xff0c;直译为超文本传输协议&#xff0c;是一种用于分布式、协作、超媒体的信息系统的应用协议。HTTP协议是万维网数据通信的基础。HTTP协议在客户端-服务器计算模型中充当请求-响应协议。客户端向服务器提交HTTP请求消息。服务器提供HTML文件和其…

基于Open3D和PyTorch3D读取三维数据格式OBJ

本节将讨论另一种广泛使用的3D数据文件格式,即OBJ文件格式。OBJ文件格式最初由Wavefront Technologies Inc.开发。与PLY文件格式类似,OBJ格式也有ASCII版本和二进制版本。二进制版本是专有的且未记录文档。本章主要讨论ASCII版本。 与之前类似,将通过示例来学习文件格式。第…