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

01背包问题合集 蓝桥OJ

一、蓝桥OJ 1174小明的背包1 模板题

思路:

用二维数组dp判断最大价值,i表示物品数量,j表示物品体积,如果 j > V 则无需继续, j >= w 物品还能再增加,同样价值也增加,否则继承之前的价值,在之间找Max,最大价值。

#include<bits/stdc++.h>
using namespace std;const int N = 1e3 + 4;
int dp[N][N];int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n, V; cin >> n >> V;for(int i = 1; i <= n; i++){int w, v; cin >> w >> v;for (int j = 1; j <= V; j++){if (j >= w)dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);else dp[i][j] = dp[i-1][j];}}cout << dp[n][V] << '\n';return 0;
}

优化思路:

避免新数据更新为新数据。上面的代码每次j的下标都是从小到大, 故可以直接当作一个数组,每次更新时,从后往前更新。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 4;
int dp[N];int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n, V; cin >> n >> V;for (int i = 1; i <= n; i++){int w, v;cin >> w >> v;for (int j = V; j >= w; j--){dp[j] = max(dp[j], dp[j-w]+v);}}cout << dp[V] << '\n';return 0;
}

二、蓝桥OJ 2223背包与魔法

思路:

这道题可以分成三类,1.不选 2.选但不用魔法 3.选且用魔法, 三种中取最大价值的。 

#include<bits/stdc++.h>
using namespace std;const int N = 1e4+5;
int dp[N][2]; // 0的时候表示魔法已用,1表示魔法没用int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n, m, k; cin >> n >> m >> k;for (int i = 1; i <= n; i++){int w, v; cin >> w >> v;for (int j = m; j >= 0; --j){if (j >= w){dp[j][0] = max(dp[j][0],dp[j-w][0]+v);dp[j][1] = max(dp[j][1],dp[j-w][1]+v);}if (j >= w + k){dp[j][1] = max(dp[j][1], dp[j-w-k][0]+2*v);}}}cout << max(dp[m][0], dp[m][1]) << '\n';return 0;
}

三、蓝桥OJ 3741倒水

思路:

用一个二维dp数组记录所有满意度之和的最大值,dp[i][j]中的i表示1~i个客人,j表示 倒水j毫升。

分3种情况,是否倒着写要看情况:

1.当j < a时,dp[i][j] = dp[i-1][j]+e

2.当j >= a and j < c时, dp[i][j] = max(dp[i-1][j]+e, dp[i-1][j-a]+b)

3.当j>=c时, dp[i][j] = max(dp[i-1][j-c]+d , max(dp[i-1][j]+e, dp[i-1][j-a]+b))

下面的代码第一次写忘记了开long long!!!一定要记住 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e3 + 8;
ll dp[N][N];int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n, m; cin >> n >> m;for (int i = 1; i <= n; i++){int a, b, c, d, e;cin >> a >> b >> c >> d >> e;for (int j = 0; j <= m; j++){if (j < a) dp[i][j] = dp[i-1][j]+e;else if (j >= a && j < c) dp[i][j] = max(dp[i-1][j]+e,dp[i-1][j-a]+b);else if (j >= c) dp[i][j] = max(dp[i-1][j-c]+d, max(dp[i-1][j]+e,dp[i-1][j-a]+b));}}cout << dp[n][m] << '\n';return 0;
}

 四、蓝桥OJ 3637盗墓分赃2

尽量把数组开大一点,不然会有测试点错误。

思路:

01背包的变形,宝藏的重量即宝藏的价值,当宝藏的重量和为奇数,一定不能平均的分成两份。后面跟01背包一样

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 8;
int a[N],dp[N];int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n;cin >> n;int sum = 0;for (int i = 1; i <= n; i++){cin >> a[i];sum += a[i];}if (sum&1){cout << "no" << '\n';return 0;}sum = sum / 2;for (int i = 1; i <= n; i++){for (int j = sum; j >= a[i]; j--){dp[j] = max(dp[j],dp[j-a[i]]+a[i]);}}string res = (dp[sum] == sum) ? "yes": "no";cout << res << '\n';return 0;
}

五、蓝桥OJ 5118小兰的神秘礼物

跟 盗墓分赃 一模一样 

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 8;
int x[N], dp[N];int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int V; cin >> V;//箱子的容量int n; cin >> n;//收集的小物件总数for (int i = 1; i <= n; i++) cin >> x[i];for (int i = 1; i <= n; i++)for (int j = V; j >= x[i]; j--) dp[j] = max(dp[j],dp[j-x[i]]+x[i]);cout << V-dp[V] << '\n';return 0;
}

相关文章:

01背包问题合集 蓝桥OJ

一、蓝桥OJ 1174小明的背包1 模板题 思路&#xff1a; 用二维数组dp判断最大价值&#xff0c;i表示物品数量&#xff0c;j表示物品体积&#xff0c;如果 j > V 则无需继续&#xff0c; j > w 物品还能再增加&#xff0c;同样价值也增加&#xff0c;否则继承之前的价值&am…...

Nuxt3 实战 (三):使用 release-it 自动管理版本号和生成 CHANGELOG

release-it 能做什么&#xff1f; 增加版本号并提交 Git生成变更日志&#xff08;Changelog&#xff09;并提交到 Git创建 Git 标签并推送到远程仓库发布到 npm 等软件仓库在 GitHub、GitLab 等平台创建发行版 前置知识 在看这篇文章之前&#xff0c;我们有必要了解一下 Sem…...

鸿蒙OS开发实战:【自动化测试框架】使用指南

概述 为支撑HarmonyOS操作系统的自动化测试活动开展&#xff0c;我们提供了支持JS/TS语言的单元及UI测试框架&#xff0c;支持开发者针对应用接口进行单元测试&#xff0c;并且可基于UI操作进行UI自动化脚本的编写。 本指南重点介绍自动化测试框架的主要功能&#xff0c;同时…...

算法(二分查找)

1.给你一个非负整数 x &#xff0c;计算并返回 x 的 算术平方根 。 由于返回类型是整数&#xff0c;结果只保留 整数部分 &#xff0c;小数部分将被 舍去 。 注意&#xff1a;不允许使用任何内置指数函数和算符&#xff0c;例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1&#xf…...

运筹学基础(六)列生成算法(Column generation)

文章目录 前言从Cutting stock problem说起常规建模Column generation reformulation 列生成法核心思想相关概念Master Problem (MP)Linear Master Problem (LMP)Restricted Linear Master Problem (RLMP)subproblem&#xff08;核能预警&#xff0c;非常重要&#xff09; 算法…...

[阅读笔记] 电除尘器类细分市场2023年报

0.原始链接&#xff1a; 2023年除尘行业评述及2024年发展展望-北极星大气网 中国环保产业协会 供稿 1.重要信息摘录 市场占有率最大的是电除尘和袋式除尘行业装备产品名录: 国家鼓励发展的重大环保技术装备目录&#xff08;2023年版&#xff09;权威评审机构&#xff1a;…...

Kubernetes学习笔记11

k8s集群核心概念&#xff1a;pod&#xff1a; 在K8s集群中是不能直接运行容器的&#xff0c;K8s的最小调度单元是Pod&#xff0c;我们要使用Pod来运行应用程序。 学习目标&#xff1a; 了解pod概念&#xff1a; 了解查看pod方法 了解创建pod方法 了解pod访问方法 了解删除…...

✌2024/4/3—力扣—无重复字符的最长子串

代码实现&#xff1a; 解法一&#xff1a;暴力法 int lengthOfLongestSubstring(char *s) {int hash[256] {0};int num 0;for (int i 0; i < strlen(s); i) {int count 0;for (int j i; j < strlen(s); j) {if (hash[s[j]] 0) {hash[s[j]];count;num num > cou…...

Tauri 进阶使用与实践指南

Tauri 进阶使用与实践指南 调试技术 在 Tauri 应用开发中&#xff0c;调试分为两大部分&#xff1a;Web 端与 Rust 控制台。 Web 端调试 在 Web 端界面&#xff0c;可以直接采用浏览器内置的开发者工具进行调试。在 Windows 上&#xff0c;可以通过快捷键 Ctrl Shift i 打…...

2024年最新社交相亲系统源码下载

最新相亲系统源码功能介绍 参考&#xff1a;相亲系统源码及功能详细介绍 相亲系统主要功能 &#xff08;已完成&#xff09; 相亲系统登录注册 相亲系统会员列表 相亲系统会员搜索 相亲系统会员详情 相亲系统会员身份认证 - 对接阿里云 相亲系统资源存储 - 对接七…...

git知识

如何将develop分支合并到master分支 #简单版 git checkout master git pull origin master git merge origin/develop # 解决可能的冲突并提交 git push origin master#复杂版 git checkout master # 拉取远程 master 分支的最新代码并合并到本地 git pull origin master # 拉…...

代码随想录算法训练营第三十五天|860.柠檬水找零、406.根据身高重建队列、452.用最少数量的箭引爆气球

代码随想录算法训练营第三十五天|860.柠檬水找零、406.根据身高重建队列、452.用最少数量的箭引爆气球 860.柠檬水找零 在柠檬水摊上&#xff0c;每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品&#xff0c;&#xff08;按账单 bills 支付的顺序&#xff09;一次购买一杯…...

golang defer实现

derfer : 延迟调用&#xff0c;函数结束返回时执行&#xff0c;多个defer按照先进后出的顺序调用 原理&#xff1a;底层通过链表实现&#xff0c;每次新增的defer调用&#xff0c;通过头插法插入链表&#xff1b;defer执行时&#xff0c;从链表头开始遍历&#xff0c;相当于实…...

数据仓库实践

什么是数据仓库&#xff1f; 数据仓库是一个用于存储大量数据并支持数据分析与报告的系统。它通常用于集成来自不同来源的数据&#xff0c;提供一个统一的视图&#xff0c;以便进行更深入的分析和决策。 数据仓库的主要优势&#xff1f; 决策支持&#xff1a;为企业决策提供可靠…...

深入浅出 -- 系统架构之微服务标准组件及职责

我们来认识一下微服务架构在Java体系中依托哪些组件实现的。 相对于单体架构的简单粗暴&#xff0c;微服务的核心是将应用打散&#xff0c;形成多个独立提供的微服务&#xff0c;虽然从管理与逻辑上更符合业务需要。但微服务架构也带来了很多急需解决的核心问题&#xff1a; 1…...

IP协议中的四大支柱:DHCP、NAT、ICMP和IGMP的功能剖析

DHCP动态获取 IP 地址 我们的电脑通常都是通过 DHCP 动态获取 IP 地址&#xff0c;大大省去了配 IP 信息繁琐的过程。 客户端首先发起 DHCP 发现报文&#xff08;DHCP DISCOVER&#xff09; 的 IP 数据报&#xff0c;由于客户端没有 IP 地址&#xff0c;也不知道 DHCP 服务器的…...

基于Socket简单的UDP网络程序

⭐小白苦学IT的博客主页 ⭐初学者必看&#xff1a;Linux操作系统入门 ⭐代码仓库&#xff1a;Linux代码仓库 ❤关注我一起讨论和学习Linux系统 1.前言 网络编程前言 网络编程是连接数字世界的桥梁&#xff0c;它让计算机之间能够交流信息&#xff0c;为我们的生活和工作带来便利…...

计算机思维

计算机思维是一种运用计算机科学的基础概念和方法来解决问题、设计系统和理解人类行为的思维方式。它包括以下几个方面&#xff1a; 1. 抽象和建模&#xff1a;将复杂的现实问题抽象为计算机可以处理的模型&#xff0c;通过定义对象、属性和关系来构建问题的逻辑结构。 2. 算法…...

如何判断一个linux机器是物理机还是虚拟机

https://blog.csdn.net/qq_32262243/article/details/132571117 第一种方式&#xff1a;dmesg命令 [rootnshqae01adm03 ~]# dmesg | grep -i hypervisor [ 0.000000] Hypervisor detected: Xen PV [ 1.115297] VPMU disabled by hypervisor. 在我的机器上 dmesg也是能够用来判…...

python用requests的post提交data数据以及json和字典的转换

环境&#xff1a;python3.8.10 python使用requests的post提交数据的时候&#xff0c;代码写法跟抓包的headers里面的Content-Type有关系。 &#xff08;一&#xff09;记录Content-Type: application/x-www-form-urlencoded的写法。 import requestsurlhttps://xxx.comheade…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...