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

各类背包问题

1、0-1背包问题

(1)用二维数组动态规划

#include<bits/stdc++.h>
using namespace std;
int m,n;
int w[50],c[50];
int dp[210][210];
int main()
{cin>>m>>n;for(int i=1;i<=n;i++){cin>>w[i]>>c[i];}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(w[i]<=j) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);else dp[i][j]=dp[i-1][j];}cout<<dp[n][m];return 0;
}

(2)一维数组解法

#include <bits/stdc++.h>
using namespace std;int m,n;
int w[100],v[100];
int dp[200];
int main()
{cin>>m>>n;for(int i=1; i<=n; i++){cin>>w[i]>>v[i];}for(int i=1; i<=n; i++){//01背包用一维数组,要从数组右边开始循环for(int j=m; j>=1; j--){if(j>=w[i]){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}}cout<<dp[m];
}

2、完全背包问题

(1)二维数组解法

#include <bits/stdc++.h>
using namespace std;
int m,n;
int w[210],c[210];
int f[210][210];
int main()
{cin>>m>>n;for(int i=1;i<=n;i++)cin>>w[i]>>c[i];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(w[i]>j) f[i][j]=f[i-1][j];else{f[i][j]=max(f[i-1][j],f[i][j-w[i]]+c[i]);}}}cout<<"max="<<f[n][m]<<endl;return 0;
}

(2)一维数组解法

完全背包用一维数组,要从数组左边开始循环

#include <bits/stdc++.h>
using namespace std;int m,n;
int w[100],v[100];
int dp[200];
int main()
{cin>>m>>n;for(int i=1; i<=n; i++){cin>>w[i]>>v[i];}for(int i=1; i<=n; i++){//完全背包用一维数组,要从数组左边开始循环for(int j=1; j<=m; j++){if(j>=w[i]){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}}cout<<"max="<<dp[m];
}

相关文章:

各类背包问题

1、0-1背包问题 &#xff08;1&#xff09;用二维数组动态规划 #include<bits/stdc.h> using namespace std; int m,n; int w[50],c[50]; int dp[210][210]; int main() {cin>>m>>n;for(int i1;i<n;i){cin>>w[i]>>c[i];}for(int i1;i<n;…...

《练习100》91~95

题目91 # 自动生成字符串 # a [小马,小羊,小鹿] # b [草地上,电影院,家里] # c [看电影,听音乐,吃晚饭] # 随机生成三个0~2的数字&#xff0c;若是1&#xff0c;0&#xff0c;2 &#xff0c;则输出&#xff1a; 小羊在草地上吃晚饭 import random a [小马,小羊,小鹿] b […...

3.6 Spring MVC文件上传

1. 文件上传到本地 实现方式 Spring MVC使用commons-fileupload实现文件上传&#xff0c;注意事项如下&#xff1a; l HTTP请求方法是POST。 l HTTP请求头的Content-Type是multipart/form-data。 SpringMVC配置 配置commons-fileupload插件的文件上传解析器CommonsMultip…...

# X11、Xlib、XFree86、Xorg、GTK、Qt、Gnome和KDE之间的关系

X11、Xlib、XFree86、Xorg、GTK、Qt、Gnome和KDE之间的关系 很多人对于他们是啥是傻傻分不清的&#xff0c;我做了个表格供大家参考。 摘抄&#xff1a; X11是X Window System Protocol, Version 11&#xff08;RFC1013&#xff09;&#xff0c;是X server和X client之间的通…...

rknn3588如何查看npu使用情况

cat /sys/kernel/debug/rknpu/load在Linux中&#xff0c;你可以使用一些工具和命令来绘制某一进程的实时内存折线图。一个常用的工具是gnuplot&#xff0c;它可以用来绘制各种图表&#xff0c;包括折线图。 首先&#xff0c;你需要收集进程的实时内存数据。你可以使用pidstat命…...

“Can‘t open perl script configure : No such file or directory”的解决办法

编译OpenSSL的时候执行到 perl configure 时提示找不到configure&#xff0c; 然后在网上搜了搜&#xff0c;大家给的解决办法一般都是说设置环境变量或者指定configure路径再执行&#xff1b;我试了都不行&#xff0c; 最后我把perl卸了重装就正常了&#xff1b; 然后我换了…...

ChatGLM2-6B在windows下的部署

2023-08-10 ChatGLM2-6B在windows下的部署 一、部署环境 1、Windows 10 专业版&#xff0c; 64位&#xff0c;版本号&#xff1a;22H2&#xff0c;内存&#xff1a;32GB 2、已安装CUDA11.3 3、已安装Anaconda3 64bit版本 4、有显卡NVIDIA GeForce RTX 3060 Laptop GPU …...

nodejs+vue+elementui学生档案信息管理系统_06bg9

利用计算机网络的便利&#xff0c;开发一套基于nodejs的大学生信息管理系统&#xff0c;将会给人们的生活带来更多的便利&#xff0c;而且在经济效益上&#xff0c;也会有很大的便利!这可以节省大量的时间和金钱。学生信息管理系统是学校不可缺少的一个环节&#xff0c;其内容直…...

Nginx location

location块是nginx配置文件中&#xff0c;配置在http块中的server块中&#xff0c;匹配的是uri location匹配uri的方式 &#xff1a; 精确匹配: location /[ ...} 正则匹配: location - /{ ...} 一般匹配: location /{ ....} 匹配的规则&#xff1a; &#xff1a;精确匹…...

数据库字段命名导致的SQL报错

1.表设计 create table variables (id bigint not null comment 主键,business_key varchar(128) null comment 业务key,key varchar(128) null comment Map中的key,value varchar(255) null comment…...

【办公自动化】使用Python一键提取PDF中的表格到Excel

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…...

【基础类】—原型链系统性知识

一、创建对象有几种方法 字面量创建对象 1-1. 什么是字面量 字面量就是所见即所&#xff0c;指的是常量&#xff1b;用来为变量赋值时的常数量 代码例子&#xff1a;123&#xff1b;‘ABC’, {name: ‘张三’}, undefined &#xff0c; true 生活例子&#xff1a;门店的招牌&a…...

ddia(3)----Chapter3. Storage and Retrieval

However, first we’ll start this chapter by talking about storage engines that are used in the kinds of databases that you’re probably familiar with: traditional relational databases, and also most so-called NoSQL databases. We will examine two families o…...

SpringBoot自定义拦截器interceptor使用详解

Spring Boot拦截器Intercepter详解 Intercepter是由Spring提供的Intercepter拦截器&#xff0c;主要应用在日志记录、权限校验等安全管理方便。 使用过程 1.创建自定义拦截器&#xff0c;实现HandlerInterceptor接口,并按照要求重写指定方法 HandlerInterceptor接口源码&am…...

AI抠图使用指南:Stable Diffusion WebUI Rembg实用技巧

抠图是图像处理工具的一项必备能力&#xff0c;可以用在重绘、重组、更换背景等场景。最近我一直在探索 Stable Diffusion WebUI 的各项能力&#xff0c;那么 SD WebUI 的抠图能力表现如何呢&#xff1f;这篇文章就给大家分享一下。 安装插件 作为一个生成式AI&#xff0c;SD…...

gitlab-Runner搭建

root wget https://packages.gitlab.com/runner/gitlab-runner/packages/fedora/29/gitlab-runner-12.6.0-1.x86_64.rpm/download.rpm rpm -ivh download.rpm ---- 安装 rpm -Uvh download.rpm -----更新升级 然后运行&#xff1a; gitlab-runner register --url https://git…...

【ChatGPT 指令大全】销售怎么借力ChatGPT提高效率

目录 销售演说 电话销售 产出潜在客户清单 销售领域计划 销售培训计划 总结 随着人工智能技术的不断进步&#xff0c;我们现在有机会利用ChatGPT这样的智能助手来改进我们的销售工作。在接下来的时间里&#xff0c;我将为大家介绍如何运用ChatGPT提高销售效率并取得更好的…...

计算机网络 网络层 路由 路由信息协议RIP

...

【Spring】-Spring项目的创建

作者&#xff1a;学Java的冬瓜 博客主页&#xff1a;☀冬瓜的主页&#x1f319; 专栏&#xff1a;【Framework】 主要内容&#xff1a;创建spring项目的步骤&#xff1a;先创建一个maven项目&#xff0c;再在pom.xml中添加spring框架支持&#xff0c;最后写一个启动类。 文章目…...

SQL | 使用通配符进行过滤

6-使用通配符进行过滤 6.1-LIKE操作符 前面介绍的所有操作符都是通过已知的值进行过滤&#xff0c;或者检查某个范围的值。但是如果我们想要查找产品名字中含有bag的数据&#xff0c;就不能使用前面那种过滤情况。 利用通配符&#xff0c;可以创建比较特定数据的搜索模式。 …...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...