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

【蓝桥】线性DP--最快洗车时间

题目描述​

解题思路

完整代码

举例

总结

基于 0/1 背包思想 解决 洗车时间分配问题,本质上是子集和问题【给定一个 正整数数组 nums 和一个目标值 target,判断是否可以从 nums 选择 若干个数(每个数最多选一次),使其和 恰好等于 target

题目描述

 

解题思路

一开始用的使用了排序+贪心的方法:

  • 对洗车时间从大到小排序(先分配长时间的任务)。
  • 优先分配给当前时间较短的那个人(类似负载均衡)。
  • 遍历数组,依次分配,最终返回 max(wash1, wash2)

        但这种思路是错的,求的是局部最优解 ,局部最优不一定导致全局最优,即在每一步都选择当前看起来最好的方案,并不一定能得到最优解

正确方法:设所有洗车时间之和为 total,我们希望 找到一个子集,使得其和 best 尽可能接近 total / 2。这样 max(best, total - best) 就是两人最优的洗车时间

1. 定义状态

dp[j] 表示是否可以从数组 nums 中选取若干个数,使得它们的和为 j

  • dp[j] = true 表示存在一个子集的和恰好等于 j
  • dp[j] = false 表示无法找到这样的子集。

2. 状态转移方程

对于当前遍历的 nums[i]

  • 如果不选 nums[i],那么 dp[j] 由前一轮 dp[j] 继承;
  • 如果选 nums[i],那么 dp[j] 取决于 dp[j - nums[i]] 是否为 true,即如果 j - nums[i] 之前是可行的,那么 j 也是可行的。

状态转移方程:

3. 初始化

  • dp[0] = true(因为总和为 0 的子集是空集,肯定可以达到)。
  • 其他 dp[j] 初始设为 false

4. 遍历顺序

  • 外层循环 遍历 nums[i](每个数只能选一次,必须按顺序遍历)。
  • 内层循环 采用 逆序 for (int j = target; j >= nums[i]; j--),确保 nums[i] 只被选取 一次
  • 最终遍历最终的DP数组,从 target 开始向 0 逆序查找 最大的 i,满足 dp[i] == true

完整代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110; // 设定数组大小
bool dp[N];  // 0/1 背包 DP 数组
int car[N];  // 存储每辆车的洗车时间
int n, target, total; // 变量定义int main() {cin >> n; // 读取车辆数量for (int i = 1; i <= n; i++) {cin >> car[i];total += car[i]; // 计算洗车时间总和}target = total / 2; // 目标是尽量分成两半dp[0] = true; // 初始状态,和为 0 一定是可行的for (int i = 1; i <= n; i++) { // 遍历每辆车for (int j = target; j >= car[i]; j--) { // 逆序遍历dp[j] = dp[j] || dp[j - car[i]];}}int best = 0;// 找到最接近 total/2 的可行解for (int i = target; i >= 0; i--) { if (dp[i]) {best = i;break;}}cout << max(best, total - best); // 计算最短最大时间return 0;
}

举例

n = 4
car = [8, 6, 5, 5]
total = 8 + 6 + 5 + 5 = 24
target = total / 2 = 24 / 2 = 12

初始化dp

dp = [true, false, false, ..., false]  // 长度为 target + 1,即 13

第 1 辆车 (洗车时间 8): 

dp[12] = dp[12] || dp[12 - 8] = false || dp[4] = false
dp[11] = dp[11] || dp[11 - 8] = false || dp[3] = false
dp[10] = dp[10] || dp[10 - 8] = false || dp[2] = false
dp[9] = dp[9] || dp[9 - 8] = false || dp[1] = false
dp[8] = dp[8] || dp[8 - 8] = false || dp[0] = true   // dp[8] = true

第 2 辆车 (洗车时间 6): 

dp[12] = dp[12] || dp[12 - 6] = false || dp[6] = false
dp[11] = dp[11] || dp[11 - 6] = false || dp[5] = false
dp[10] = dp[10] || dp[10 - 6] = false || dp[4] = false
dp[9] = dp[9] || dp[9 - 6] = false || dp[3] = false
dp[8] = dp[8] || dp[8 - 6] = true  || dp[2] = false
dp[7] = dp[7] || dp[7 - 6] = false || dp[1] = false
dp[6] = dp[6] || dp[6 - 6] = false || dp[0] = true   // dp[6] = true

.......

最终

dp = [true, false, false, false, false, true, true, false, true, true, true, true, false]

总结

转换成 0/1 背包问题,利用 动态规划 解决。
dp[j] 表示是否能凑出 j 这个和,递推转移 dp[j] = dp[j] || dp[j - car[i]]
时间复杂度 O(n * sum/2),适用于 sum ≤ 10^4
贪心方法可能失效,而动态规划保证最优解

相关文章:

【蓝桥】线性DP--最快洗车时间

题目描述​ 解题思路 完整代码 举例 总结 基于 0/1 背包思想 解决 洗车时间分配问题&#xff0c;本质上是子集和问题【给定一个 正整数数组 nums 和一个目标值 target&#xff0c;判断是否可以从 nums 选择 若干个数&#xff08;每个数最多选一次&#xff09;&#xff0c;使…...

Spring Boot比Spring多哪些注解?

Spring Boot 相比 Spring 多了很多自动化配置和简化开发的注解&#xff0c;主要包括以下几类&#xff1a; Spring Boot 启动与自动配置相关Spring Boot 配置相关Spring Boot Web 相关Spring Boot 测试相关Spring Boot 条件装配相关Spring Boot 监控与 Actuator 相关 1. Spring…...

springboot021校园周边美食探索及分享平台

版权声明 所有作品均为本人原创&#xff0c;提供参考学习使用&#xff0c;如需要源码数据库配套文档请移步 www.taobysj.com 搜索获取 技术实现 开发语言&#xff1a;Javavue。 框架&#xff1a;后端spingboot前端vue。 模式&#xff1a;B/S。 数据库&#xff1a;mysql。 开…...

【网络通信】传输层之UDP协议

【网络通信】传输层之UDP协议 传输层端对端通信实现端到端通信的关键技术 UDP协议再谈端口号端口号划分关于端口号的两个问题 UDP协议基本格式UDP通信的特点UDP的缓冲区UDP数据报的最大长度基于UDP的应用层协议如何封装UDP报文以及如何交付UDP报文进一步理解封装和解包 传输层 …...

Python环境搭建与量化交易开发:从基础到实战

Python环境搭建与量化交易开发&#xff1a;从基础到实战 在量化交易领域&#xff0c;Python因其强大的数据处理能力和丰富的库支持而成为首选编程语言。本文将指导您如何在本地搭建一个适合量化交易的Python环境&#xff0c;并介绍一些实用的工具和技巧。 《QMT开通规则分享》…...

软著申请(六)软著返修流程【2025年最新版】

软著申请(六)软著返修流程【2025年最新版】 一、软著返修流程1、软著返修流程须知2、相关细节二、针对大模型特殊补正条件三、备注本服务提供详细的软件著作权申请流程指导。申请人严格按照指导步骤完成申请,若最终未能成功获得著作权登记,可联系服务提供方进行免费咨询和指…...

SOUI基于Zint生成Code11码

Code 11 是一种高密度的数字条形码&#xff0c;主要用于标识电信设备和电子元件。它的名称来源于其能够编码 11 种字符&#xff1a;数字 0-9 和连接符 -。Code 11 是一种双向可读的条形码&#xff0c;支持校验位以提高数据准确性。 在使用BARCODE_CODE11码制生成code 11码时可指…...

sqlilabs第八关

?id1 and sleep(2)-- 发现页面存在注点&#xff0c;使用时间盲注脚本进行注入--- import requestsdef inject_database(url):name #name用于存储猜测出的数据库名称 for i in range(1, 20): # 假设数据库名称长度不超过20low 48 # 0high 122 # zmiddle (low high…...

基于HAL库的按钮实验

实验目的 掌握STM32 HAL库的GPIO输入配置方法。 实现通过按钮控制LED亮灭&#xff08;支持轮询和中断两种模式&#xff09;。 熟悉STM32CubeMX的外部中断&#xff08;EXTI&#xff09;配置流程。 实验硬件 开发板&#xff1a;STM32系列开发板&#xff08;如STM32F103C8T6、N…...

DeepSeek 突然来袭,AI 大模型变革的危机与转机藏在哪?

随着人工智能技术的飞速发展&#xff0c;大模型领域不断涌现出具有创新性的成果。DeepSeek 的横空出世&#xff0c;为 AI 大模型领域带来了新的变革浪潮。本文将深入探讨 DeepSeek 出现后 AI 大模型面临的危机与转机。 冲冲冲&#xff01;&#xff01;&#xff01; 目录 一、…...

prompt技术结合大模型 生成测试用例

要利用prompt技术结合大模型对目标B/S架构软件系统进行测试,以下以使用Python调用OpenAI的GPT模型进行功能测试用例生成,再借助Selenium库执行测试为例,给出一个完整的实现示例。 前提条件 安装依赖库:你需要安装openai和selenium库,可以使用以下命令进行安装:pip insta…...

【C++ 真题】P2920 [USACO08NOV] Time Management S

P2920 [USACO08NOV] Time Management S 题目描述 Ever the maturing businessman, Farmer John realizes that he must manage his time effectively. He has N jobs conveniently numbered 1…N (1 < N < 1,000) to accomplish (like milking the cows, cleaning the …...

pip安装指定版本的包

个人博客地址&#xff1a;pip安装指定版本的包 | 一张假钞的真实世界 使用以下命令安装指定版本的包&#xff1a; # pip install pyspark2.3.3...

【pytest】获取所有用例名称并存于数据库

数据库操作包&#xff0c;引用前面创建的py文件&#xff0c;【sqlite】python操作sqlite3&#xff08;含测试&#xff09; #!/usr/bin/env python # -*- coding: utf-8 -*- # Time : 2025-02-11 8:45 # Author : duxiaowei # File : get_filename.py # Software: 这个文…...

Java中原子操作的实现原理

目录 一、处理器如何实现原子操作&#xff1f; 1.使用总线锁保证原子性 1.使用缓存锁保证原子性 二、Java如何实现原子操作&#xff1f; 1&#xff09;使用循环CAS实现原子操作 2&#xff09;CAS实现原子操作的三大问题 3&#xff09;使用锁机制实现原子操作 前言 原子&…...

25农村发展研究生复试面试问题汇总 农村发展专业知识问题很全! 农村发展复试全流程攻略 农村发展考研复试真题汇总

农村发展复试当然有好的建议&#xff01;前提是复试重点面试题背好&#xff01; 你是不是也在为农村发展考研复试发愁&#xff1f;担心自己准备不充分、表现不好&#xff1f;别急&#xff01;今天&#xff0c;学姐——复试面试拿下90分成功上岸的学姐&#xff0c;来给大家分享…...

一维前缀和与二维前缀和

前缀和&#xff08;Prefix Sum&#xff09;是一种用于高效计算数组区间和的预处理技术&#xff0c;尤其适用于需要频繁查询子数组或子矩阵和的场景。下面详细讲解一维前缀和与二维前缀和的原理、构建方法及应用。 一、一维前缀和 1. 定义 前缀和数组 prefix 的每个元素 prefi…...

3×2 MIMO系统和2×2 MIMO系统对比

从 SVD&#xff08;奇异值分解&#xff09;预编码 的角度分析&#xff0c;32 MIMO 系统相比 22 MIMO 系统在容量、功率分配灵活性和抗干扰能力方面具有潜在优势。以下是具体分析&#xff1a; 1. SVD预编码的基本原理 SVD 预编码是一种基于信道状态信息&#xff08;CSI&#xf…...

【MySQL — 数据库基础】深入解析 MySQL 的联合查询

1. 插入查询结果 语法 insert into table_name1 select* from table_name2 where restrictions ;注意&#xff1a;查询的结果集合&#xff0c;列数 / 类型 / 顺序 要和 insert into 后面的表相匹配&#xff1b;列的名字不要求相同&#xff1b; create table student1(id int , …...

【医院运营统计专题】3.解码医院运营统计:目标、原则与未来蓝图

医院成本核算、绩效管理、运营统计、内部控制、管理会计专题索引 一、医院运营统计的关键意义 在医疗行业持续发展与变革的大背景下,医院运营统计作为医院管理的关键组成部分,其重要性愈发凸显。从国内医院的普遍现状来看,运营统计已深度融入日常管理,为医院的有序运转提…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...