【算法作业】均分卡牌,购买股票
问题描述
-
John 有两个孩子,在 John病逝后,留下了一组价值不一定相同的魔卡, 现在要求你设计一种策略,帮John的经管人将John的这些遗产分给他的两个孩子,使得他们获得的遗产差异最小(每张魔卡不能分拆)。
-
假设已知某股票连续若干天的股价,并且如何时候你手上只能由一支股票,即如果你要买入就得先将手上股票卖出,设计一个算法来计算你所能获取的最大利润。你最多可以完成 k笔交易。也就是说,你最多可以买k 次,卖 k 次。
输入:k = 2, prices = [3,2,7,5,1,4] 输出:87-2 + 4-1
解题思路
T1
这是一个经典的贪心算法问题:
- 将所有的魔卡按照价值从大到小排序。
- 从价值最高的魔卡开始,依次分配给两个孩子中当前遗产较少的那个孩子。
- 重复步骤2直到所有的魔卡都被分配完毕。
这种贪心分东西的思路非常常见,一眼望穿
类似的题目还有捡大小垃圾放两个垃圾袋呀等等。
T2
那么这道题到底是贪心还是动规呢?
我们知道动规有一道经典例题,就是非升子序列,不觉得这题有几分相似,都是必须从前往后求最优。其实要证明贪心算法不行只要举个反例就行了。
于是就根据经验按照动规的思路来思考。考虑使用二维数组dp[i][j]
,代表当前状态的最大利润,i
代表当前是第i次买卖,j
代表当前是第j天。
对于每个状态都有买和不买。为什么是买和不买呢,不是还有卖吗?其实是赚钱和不赚钱这两种选择,赚钱是卖与买之间的差值。所以这道题比一般的动态规划要更复杂些。
对于每一次买卖,必须有买才有卖,先用maxDiff
包括因为买股票亏的钱,一开始由于没有股票,就等于-prices[1]
。这个亏的钱也完全不是负数亏的钱,还要包括之前(上一次买卖)因为赚钱累计的成本,这个maxDiff
就是代表本次买卖状态下的累计成本(比较难理解)。所以 m a x D i f f = m a x ( m a x D i f f , d p [ i − 1 ] [ j ] − p r i c e s [ j ] ) maxDiff = max(maxDiff, dp[i-1][j] - prices[j]) maxDiff=max(maxDiff,dp[i−1][j]−prices[j])
对于每一天,都有去赚钱和不赚钱。不赚钱利润等于昨天的利润,去赚钱的利润等于累计成本maxDiff
加上prices[j]
,因此 d p [ i ] [ j ] = m a x ( d p [ i ] [ j − 1 ] , p r i c e s [ j ] + m a x D i f f ) dp[i][j] = max(dp[i][j-1], prices[j] + maxDiff) dp[i][j]=max(dp[i][j−1],prices[j]+maxDiff)
在样例下,dp运算结果如下所示。
prices | 3 | 2 | 7 | 5 | 1 | 4 |
---|---|---|---|---|---|---|
dp[1][j] | 0 | 0 | 5 | 5 | 5 | 5 |
dp[2][j] | 0 | 0 | 5 | 5 | 5 | 8 |
这个dp[k][n]就是answer。
完整代码
T1
#include <iostream>
#include <algorithm>using namespace std;// 分配遗产的函数
void distributeInheritance(int cards[], int n) {// 排序魔卡sort(cards, cards + n, greater<int>());// 初始化两个孩子的遗产值int child1_inheritance = 0;int child2_inheritance = 0;// 分配遗产for (int i = 0; i < n; ++i) {if (child1_inheritance <= child2_inheritance) {child1_inheritance += cards[i];} else {child2_inheritance += cards[i];}}// 输出两个孩子的遗产差异cout << "遗产差异最小为:" << abs(child1_inheritance - child2_inheritance) << endl;
}int main() {// 输入魔卡数量int n;cout << "请输入魔卡数量:";cin >> n;// 输入每张魔卡的价值int cards[n];cout << "请输入每张魔卡的价值:" << endl;for (int i = 0; i < n; ++i) {cin >> cards[i];}// 调用分配遗产函数distributeInheritance(cards, n);return 0;
}/* sample input
8
2 5 6 7 1 7 4 3
*/
输出结果
请输入魔卡数量:8
请输入每张魔卡的价值:
2 5 6 7 1 7 4 3
遗产差异最小为:1
T2
#include<bits/stdc++.h>
using namespace std;
int main(){int n,k,prices[100],dp[101][101]; // 动态规划数组大小修改为dp[101][101]cin>>n>>k;memset(dp,0,sizeof(dp));memset(prices,0,sizeof(prices));for(int i=1;i<=n;i++)cin>>prices[i];for(int i=1;i<=k;i++){int maxDiff = -prices[1]; // 数组prices的下标从1开始for(int j=1;j<=n;j++){ dp[i][j] = max(dp[i][j-1],prices[j] + maxDiff);maxDiff = max(maxDiff, dp[i-1][j] - prices[j]);}}cout<<dp[k][n]<<endl;// 打印dp数组cout<<"|dp|";for(int i=1;i<=n;i++)cout<<i<<"|";cout<<endl;cout<<"|";for(int i=1;i<=n+1;i++)cout<<"-|";cout<<endl;for(int i=1;i<=k;i++){cout<<"|"<<i<<"|";for(int j=1;j<=n;j++)cout<<dp[i][j]<<"|";cout<<"\n";}return 0;
}/* simple input
6 2
3 2 7 5 1 4
*/
输出结果
6 2
3 2 7 5 1 4
8
|dp|1|2|3|4|5|6|
|-|-|-|-|-|-|-|
|1|0|0|5|5|5|5|
|2|0|0|5|5|5|8|
相关文章:
【算法作业】均分卡牌,购买股票
问题描述 John 有两个孩子,在 John病逝后,留下了一组价值不一定相同的魔卡, 现在要求你设计一种策略,帮John的经管人将John的这些遗产分给他的两个孩子,使得他们获得的遗产差异最小(每张魔卡不能分拆&#…...
python作业
题目 分析 步骤: 判断先画空格还是数字 当有n层时,第i层有多少个空格第i层的起始数字是几,结尾是几,即数字取值范围当有n层时,第i层有多少个数字 代码 模式A n int(input("请输入行数:")) for i in range(…...
【Linux的文件篇章 - 管道文件】
Linux学习笔记---013 Linux的管道文件1、进程间通信1.1、进程为什么要通信?1.2、进程如何通信?1.3、进程通信的方式? 2、匿名管道2.1、理解一种现象2.2、基本概念和管道原理 3、管道的使用3.1、代码样例3.2、如何使用管道通信呢?3…...
C# 局部静态函数,封闭方法中的最佳选择
C# 局部静态函数,封闭方法中的最佳选择 简介特性 应用场景辅助计算递归与尾递归优化筛选与过滤操作查找与映射操作 生命周期静态局部函数 vs 普通局部函数性能封装性可读性 简介 C# 局部静态函数(Local Static Functions)是一种函数作用域内…...
【MySQL】MySQL 8.4.0 长期支持版(LTS)安装
就在2024年 “5.1” 节前,MySQL官方发布了8.4.0长期支持版(LTS - Long Term Support)。根据官方提供的文档,在本地虚拟机进行安装测试。 安装、配置和启动过程记录如下: 第一步,上传到安装包(my…...
nest中的ORM
在 Nest.js 中执行 SQL 查询通常涉及使用 TypeORM 或 Sequelize 这样的 ORM(对象-关系映射)库。这些库使得在 Nest.js 应用程序中连接和操作 SQL 数据库变得更加简单和直观。 以下是一个使用 TypeORM 在 Nest.js 中执行 SQL 查询的示例代码:…...
TCP(Transmission Control Protocol,传输控制协议)如何保证数据的完整性?
TCP(Transmission Control Protocol,传输控制协议)通过一系列机制来保证数据传输的可靠性和无错性,这些机制主要包括: 校验和:TCP报文段包含一个校验和字段,用于检测数据在传输过程中是否出错。…...
Numpy库介绍
NumPy(Numerical Python的缩写)是Python中用于科学计算的一个强大的库。它提供了高性能的多维数组对象(即ndarray)、用于处理这些数组的工具以及用于数学函数操作的函数。让我为你介绍一下它的一些主要功能: 1. 多维数…...
临时有事无法及时签字盖章?试试用契约锁设置“代理人”
遇到“领导休假中、在开重要会议、外出考察或者主任医生手术中等”一段时间内不方便或者无法及时签字盖章的情况怎么办?业务推进不了只能干等? 契约锁电子签及印控平台支持印章、签名“临时授权”、“代理签署”,实现指定人、指定时间段、指定…...
数据库权限管理
1.查看系统级权限(global level) Select * from mysql.user\G; 2.查看数据库中所有表的权限 Select * from mysql.db\G 3.远程连接数据库 第一步在有数据库服务上的主机上:授权 grant all on *.* to root192.168.40.83 identified by Zxy20234; 第…...
如何创建一个 Django 应用并连接到数据库
简介 Django 是一个用 Python 编写的免费开源的 Web 框架。这个工具支持可扩展性、可重用性和快速开发。 在本教程中,您将学习如何为一个博客网站建立与 MySQL 数据库的初始基础。这将涉及使用 django-admin 创建博客 Web 应用程序的骨架结构,创建 MyS…...
【算法刷题day44】Leetcode:518. 零钱兑换 II、377. 组合总和 Ⅳ
文章目录 Leetcode 518. 零钱兑换 II解题思路代码总结 Leetcode 377. 组合总和 Ⅳ解题思路代码总结 草稿图网站 java的Deque Leetcode 518. 零钱兑换 II 题目:518. 零钱兑换 II 解析:代码随想录解析 解题思路 先遍历物品,再遍历背包。 代码…...
『51单片机』AT24C02[IIC总线]
存储器的介绍 ⒈ROM的功能⇢ROM的数据在程序运行的时候是不容改变的,除非你再次烧写程序,他就会改变,就像我们的书本,印上去就改不了了,除非再次印刷,这个就是ROM的原理。 注→在后面发展的ROM是可以可写可…...
Jenkins与Rancher的配合使用
Jenkins和Rancher是两个常用的DevOps工具,可以很好地配合使用来实现持续集成和持续部署。 Jenkins是一个开源的自动化构建工具,可以实现自动化的代码构建、测试和部署等一系列操作。可以通过Jenkins来触发构建任务,例如从代码仓库中拉取最新的…...
GIS入门,常用的多边形平滑曲线算法介绍和JavaScript的多边形平滑曲线算法库chaikin-smooth的实现原理和使用
前言 本章介绍一下常用的多边形平滑曲线算法及其使用案例。 多边形平滑算法通常用于图形处理或计算机图形学中,以使线条或曲线在连接处平滑过渡,而不出现明显的棱角或断裂。多边形平滑算法有多种实现方法,其中一些常见的有下面几种: 贝塞尔曲线插值(Bezier Curve Interpo…...
气膜体育馆内部的采光效果如何?—轻空间
气膜体育馆内部的采光效果如何?这是许多人对这种创新建筑的一个关键关注点。 首先,气膜体育馆的采光性非常好。阳光透过屋顶时以漫射光的方式进入室内,这种透射方式使得室内的光线柔和而均匀。从内部观察,整个屋顶就像一个连续的明…...
矩阵的对称正定性判决(复习)
文章目录 本科学的数学知识忘的太快了 如何判断一个实矩阵是否是对称正定 在线性代数中,一个实对称矩阵是否为正定可以通过以下方法判断: 对称性: 首先,确认矩阵是否对称,即矩阵的转置是否等于其本身。 特征值检查&…...
网络安全之DHCP详解
DHCP:Dynamic Host Configration Protocol 动态主机配置协议 某一协议的数据是基于UDP封装的,当它想确保自己的可靠性时,这个协议要么选确认重传机制,要么选周期性传输。 DHCP是确认重传,【UDP|DHCP】,当DHCP分配完地…...
【Proteus】LED呼吸灯 直流电机调速
1.LED呼吸灯 #include <REGX51.H> sbit LEDP2^0; void delay(unsigned int t) {while(t--); } void main() {unsigned char time,i;while(1){for(time0;time<100;time){for(i0;i<20;i){LED0;delay(time);LED1;delay(100-time);}}for(time100;time>0;time--){fo…...
今天遇到一个GPT解决不了的问题
问题描述 你好,postman的一个post请求,编辑器里面放了一个很长的json数据,报Tokenization is skipped for long lines for performance reasons. This can be configured via editor.maxTokenizationLineLength.,但是同样的数据&a…...
优化SQL的方法
来自组内分享,包含了比较常使用到的八点: 避免使用select * union all代替union 小表驱动大表 批量操作 善用limit 高效的分页 用连接查询代替子查询 控制索引数量 一、避免使用select * 消耗数据库资源 消耗更多的数据库服务器内存、CPU等资源。 消…...
库存管理系统开源啦
软件介绍 ModernWMS是一个针对小型物流仓储供应链流程的开源库存管理系统。该系统的开发初衷是为了满足中小型企业在有限IT预算下对仓储管理的需求。通过总结多年ERP系统研发经验,项目团队开发了这套适用于中小型企业的系统,以帮助那些有特定需求的用户。…...
【java】接口
什么是接口 接口当中存在的是对方法的定义,而不是对方法的具体实现。 为什么不实现这个方法呢? 继承的本质是代码的复用。当一个父类会经常被继承,并且子类都要自己实现方法时,父类中的方法就会显得累赘,并且占用了…...
Java中的类型转换
一、类型转换 对类型转换来说分为向上类型转换和向下类型转换: 向上类型转换是自动完成的,一般是小类型向大类型转换。在引用类型中是子类型向父类型转换。向下类型转换是强制完成的,一般是大类型向小类型转换。在引用类型中是父类型向子类…...
定义范围对PFMEA分析的重要性——SunFMEA软件
在进行PFMEA分析时,定义范围是一个至关重要的步骤。这是因为,通过明确分析的范围,可以确保团队关注到最关键、最可能影响产品质量的过程,从而更有效地识别和解决潜在问题。今天SunFMEA软件和大家一起讨论定义范围对PFMEA操作的重要…...
json返回工具类|世界协调时间(UTC)
一、问题 世界协调时间(UTC)是一个标准的时间参考,通常被用于跨越不同时区的时间标准。要将 UTC 时间转换为中国时间(中国标准时间),你需要将时间加上8个小时,因为中国位于 UTC8 时区。 初中知…...
MySQL·内置函数
目录 函数 日期函数 案例1:创建一张表,记录生日 案例2:创建一个留言表 案例3:请查询在2分钟内发布的帖子 字符串函数 案例1: 获取emp表的ename列的字符集 案例2:要求显示exam_result表中的信息&am…...
vue根据文字动态判断溢出...鼠标悬停显示el-tooltip展示
使用自定义el- tooltip 组件 定义 Tooltip是一种小型弹出框,它显示有关特定页面元素的信息,例如按钮、链接或图标。Tooltip通常以半透明的气泡形式呈现,并出现在页面元素的旁边或下方。 它可以改善用户体验,使用户更容易理解页面元素的功能和意图。用户可以通过将鼠标悬停…...
使用Tkinter实现数据预测工具的GUI界面展示
如果构建好预测模型后,想将预测模型通过一个交互式的页面显示,可以通过下边两种方式实现。 本文中代码有详细解析注释,便不再如往期一样分开讲解了,有需要的朋友可以直接拿去使用,代码可以直接运行,把预测…...
机器学习笔记-22
终章 至此吴恩达老师的机器学习课程已经完成啦,总结一下: 1.监督学习的算法:线性回归、逻辑回归、神经网络和向量机 2.无监督学习的算法:K-Means、PCA、异常检测 3.推荐系统、大规模数据处理、正则化、如何评估算法 4.上限分析、…...
车间为什么选择蒸发式冷风机?
蒸发式冷风机具有以下特点: 节能环保:蒸发式冷风机不使用压缩机和化学制冷剂,而是通过水的蒸发来降低温度,因此它是无压缩机、无冷媒、无污染的环保型产品。降温效果显著:在较潮湿地区,它一般能达到5-9℃的…...
5分钟速通大语言模型(LLM)的发展与基础知识
✍️ 作者:哈哥撩编程(视频号同名) 博客专家全国博客之星第四名超级个体COC上海社区主理人特约讲师谷歌亚马逊演讲嘉宾科技博主极星会首批签约作者 🏆 推荐专栏: 🏅 程序员:职场关键角色通识宝…...
vue项目开发流程
vue项目开发流程 环境配置 asdf plugin add nodejs asdf install nodejs 16.20.2创建项目 npm create vitelatest my-vue-app -- --template vue npm install npm run dev修改调试端口 修改vite.config.js,修改如下所示,添加server的host和port。 import { de…...
【Django学习笔记(十)】Django的创建与运行
Django的创建与运行 前言正文1、安装Django2、创建项目2.1 基于终端创建项目2.2 基于Pycharm创建项目2.3 两种方式对比 3、默认项目文件介绍4、APP5、启动运行Django5.1 激活App5.2 编写URL和视图函数对应关系5.3 启动Django项目5.3.1 命令行启动5.3.2 Pycharm启动5.3.3 views.…...
即时通讯技术文集(第37期):IM代码入门实践(Part1) [共16篇]
为了更好地分类阅读 52im.net 总计1000多篇精编文章,我将在每周三推送新的一期技术文集,本次是第37 期。 [- 1 -] 一种Android端IM智能心跳算法的设计与实现探讨(含样例代码) [链接] http://www.52im.net/thread-783-1-1.html […...
UV胶具有哪些特点和优势
1. 快速固化:UV胶在紫外线照射下能够迅速固化,固化时间通常在几秒钟到几分钟之间,大大提高了生产效率。 2. 高粘接强度:UV胶固化后,具有较高的粘接强度,能够在各种材料上实现可靠的粘接,提供持…...
python面试之mysql引擎选择问题
MySQL数据库提供了多种存储引擎,每种存储引擎有其特定的优势和场景适用。以下是几种常见的MySQL存储引擎及其特点: InnoDB: 支持事务,有回滚和提交事务的功能。 支持行级锁定,提供更高的并发。 支持外键约束&#…...
MT3031 AK IOI
思路:把每个节点存到堆(大根堆)里。 如果节点放入后总时间没有超过m则放入堆中;如果总时间超过了,就看堆头元素是否比新元素大。如果大,则删除堆头(反悔贪心)。 注意别忘记开long l…...
UE5自动生成地形二:自动生成插件
UE5自动生成地形二:自动生成插件 Polycam使用步骤 本篇主要讲解UE5的一些自动生成地形的插件 Polycam 此插件是通过现实的多角度照片自动建模生成地形数据,也是免费的。这里感谢B站up主古道兮峰的分享 Polycam网站 插件下载地址 插件网盘下载 提取码&a…...
二分图(染色法与匈牙利算法)
二分图当且仅当一个图中不含奇数环 1.染色法 简单来说,将顶点分成两类,边只存在于不同类顶点之间,同类顶点之间没有边。 e.g. 如果判断一个图是不是二分图? 开始对任意一未染色的顶点染色。 判断其相邻的顶点中,若未…...
ReactFlow的ReactFlow实例事件传参undefined处理状态切换
1.问题 ReactFlow的ReactFlow实例有些事件我们在不同的状态下并不需要,而且有时候传参会出现其它渲染效果,比如只读状态下我们不想要拖拉拽onEdgesChange连线重连或删除的功能。 2.思路 事件名称类型默认值onEdgesChange(changes: EdgeChange[]) >…...
Dockerfile 和 Docker Compose
Dockerfile 和 Docker Compose 是 Docker 生态系统中两个重要的组成部分,它们分别服务于不同的目的,但共同协助开发者和运维人员高效地管理和部署容器化应用。 Dockerfile Dockerfile 是一个文本文件,包含了构建 Docker 镜像所需的一系列指…...
多个文件 import 的相同模块里的对象
多个文件 import 的相同模块里的对象,是否永远都是同一个对象? 在store的index.js中 import vue from ‘vue’ import Vuex from ‘vuex’ 并配置有关对象 然后再app.vue中配置vm 在不同的文件中 import一个vue对象,在任何情况下&#…...
面试经典150题——验证回文串
面试经典150题 day25 题目来源我的题解方法一 双指针方法二 双指针 空间优化 题目来源 力扣每日一题;题序:125 我的题解 方法一 双指针 首先去除掉字符串中的无用字符,并将英文字符转换为小写,然后使用双指针来判断是否是回文串…...
YOLOv8的训练、验证、预测及导出[目标检测实践篇]
这一部分内容主要介绍如何使用YOLOv8训练自己的数据集,并进行验证、预测及导出,采用代码和指令的两种方式,参考自官方文档:Detect - Ultralytics YOLOv8 Docs。实践篇不需要关注原理,只需要把流程跑通就行,…...
光伏远动通讯屏的组成
光伏远动通讯屏的组成 远动通讯屏主要用于电力系统数据采集与转发,远动通讯屏能够采集站内的各种数据,如模拟量、开关量和数字量等,并通过远动通讯规约将必要的数据上传至集控站或调度系统。这包括但不限于主变和输电线路的功率、电流、电压等…...
营销H5测试综述
H5页面是营销域最常见的一种运营形式,业务通过H5来提供服务,可以满足用户对于便捷、高效和低成本的需求。H5页面是业务直面用户的端点,其质量保证工作显得尤为重要。各业务的功能实现具有通用性,相应也有共性的测试方法࿰…...
【C++随记4】C++二进制位操作运算符
在C中,二进制位操作运算符允许你直接对整数类型的变量的位进行操作。这些运算符包括: 按位与(Bitwise AND): & 按位或(Bitwise OR): | 按位异或(Bitwise XOR): ^ 按位取反&…...
风电厂数字孪生3D数据可视化交互展示构筑智慧化电厂管理体系
随着智慧电厂成为未来电力企业发展的必然趋势,深圳华锐视点紧跟时代步伐,引领技术革新,推出了能源3D可视化智慧管理系统。该系统以企业现有的数字化、信息化建设为基础,融合云平台、大数据、物联网、移动互联、机器人、VR虚拟现实…...
大模型市场爆发式增长,但生成式AI成功的关键是什么?
进入2024年,大模型市场正在爆发式增长。根据相关媒体的总结,2024年1-4 月被统计到的大模型相关中标金额已经达到2023年全部中标项目披露金额的77%左右;其中,从项目数量来看,应用类占63%、算力类占21%、大模型类占13%、…...
数仓架构之为什么要进行数仓分层
数仓分层这个概念想必大家都很熟悉,不管是在实际的开发工作当中会用的,还是在面试官面试你的时候会问到:你之前的项目是按照什么分层的,分哪几层,数仓分层有什么好处,举个栗子说说。 简而言之,…...
在面对各种问题时,我们应该如何进行数据分析
python数据分析汇总 前言一、对比分析概念特征类型案例Matplotlib的颜色字母对照表解决遇到未知函数 二、相关性分析概念类型案例一案例二 三、时间序列分析概念类型案例 四、回归分析概念类型案例一案例二案例三 五、决策树概念计算过程案例 六、主成分分析概念计算过程案例 七…...
【WEB前端2024】开源智体世界:乔布斯3D纪念馆-第23课-烟花插件的售卖效果优化
【WEB前端2024】开源智体世界:乔布斯3D纪念馆-第23课-烟花插件的售卖效果优化 使用dtns.network德塔世界(开源的智体世界引擎),策划和设计《乔布斯超大型的开源3D纪念馆》的系列教程。dtns.network是一款主要由JavaScript编写的智…...
【Maven】Nexus私服简介_下载安装_登录
1、简介 1.1介绍 Nexus私服,也被称为Maven仓库管理器,是许多公司在自己的局域网内搭建的远程仓库服务器。提供了强大的仓库管理功能和构件搜索功能,使得开发人员能够更方便地管理和使用Maven项目中的依赖库。 1.2作用 内网访问࿱…...
C语言简要(一)
总得让她开心吧 helloworld #include <stdio.h>int main() {printf("hello world!\n");return 0; } 程序框架 #include <stdio.h> int main {return 0; }输出 printf("hello world!\n"); "里面的内容叫做“字符串”,prin…...
设计模式与软件体系结构课后练习参考答案
目录 软件设计模式第二章 创建型软件设计模式1. 工厂模式2. 生成器模式3. 单例模式 第三章 结构型软件设计模式1. 组合模式2. 适配器模式3. 外观模式4. 桥接模式 第四章 行为型软件设计模式1. 迭代器模式2. 访问者模式3. 中介者模式4. 策略模式5. 状态模式 案例分析工厂模式案例…...