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

典范硬币系统（Canonical Coin System）→ 贪心算法

news 来源：原创 2025/7/13 14:02:09

【典范硬币系统】
● 典范硬币系统（Canonical Coin System）是指使用贪心算法总能得到最少硬币数量解‌的货币面值组合‌。

● 给定一个硬币系统 $S={S_1,S_2,\cdots,S_i,S_{i+1},\cdots,S_n}$ ，若使其为典范硬币系统，则要求其各相邻面值比例 ${\textcolor{red}{S_{i+1}/S_i \geq 2}}$ ，及各开区间 $(S_i,S_{i+1})$ 内各金额 $r$ （非面值）的余数覆盖成本 $f(r)$ 小于相邻面值比例 $S_{i+1}/S_i$ ，即 ${\textcolor{red}{f(r) \leq S_{i+1}/S_i}}$ ，其中， $r\in (S_i,S_{i+1})$ 。当余数覆盖成本大于相邻面值比例时，即 $f(r)>S_{i+1}/S_i$ 时，需插入相邻面值构成的开区间 $(S_i,S_{i+1})$ 之间的某个金额作为新增面值优化原硬币系统。若优化后导致相邻面值比例不达标，即小于 2 了，需整体重构层级。

● 余数覆盖成本，是指位于相邻硬币面值 $S_i$ 与 $S_{i+1}$ 之间的金额 $r$ ，通过更小面值硬币覆盖该金额所需的最小硬币数量 $f(r)$ 。余数覆盖成本是判断贪心算法有效性的关键指标，需通过层级比例约束与动态调整机制控制其阈值。满足条件的硬币系统（如人民币硬币系统）可高效使用贪心算法，否则需依赖动态规划‌。

● 相邻面值比例优先级，高于余数覆盖成本。即典范硬币系统，必须先满足相邻面值比例 ≥2 的约束条件。

【实例分析】
给定一个硬币系统 {1,5,11}，判断其是否为典范硬币系统。
首先，其各相邻面值比例均大于等于 2（5/1=5≥2，11/5=2.2≥2），符合要求。
其次，分析其各余数覆盖成本，列表如下。

硬币系统 {1,5,11}区间	余数覆盖成本 $f(r)$	相邻面值比例 $S_{i+1}/S_i$	$f(r) \leq S_{i+1}/S_i$
相邻面值 1 元和 5 元构成的开区间（1,5）	f(2)=2（2枚1元）	5/1=5	2≤5？（√）
	f(3)=3（3枚1元）	5/1=5	3≤5？（√）
	f(4)=4（4枚1元）	5/1=5	4≤5？（√）
相邻面值 5 元和 11 元构成的开区间（5,11）	f(6)=2（1枚5元，1枚1元）	11/5=2.2	2≤2.2？（√）
	f(7)=3（1枚5元，2枚1元）	11/5=2.2	3≤2.2？（错误）
	f(8)=4（1枚5元，3枚1元）	11/5=2.2	4≤2.2？（错误）
	f(9)=5（1枚5元，4枚1元）	11/5=2.2	5≤2.2？（错误）
	f(10)=2（2枚5元）	11/5=2.2	2≤2.2？（√）

据表可知，此硬币系统 {1,5,11} 不满足典范硬币系统，故其不能通过利用贪心法求得最优解，只能采用动态规划求最优解。

典范硬币系统（Canonical Coin System）→ 贪心算法

【典范硬币系统】 ● 典范硬币系统（Canonical Coin System）是指使用贪心算法总能得到最少硬币数量解‌的货币面值组合‌。 ● 给定一个硬币系统 ，若使其为典范硬币系统，则要求其各相邻面值比例 ，及各开区间内各金额…...

编程日记 2025/7/13 14:02:09

hbuilderx打包iOS上传苹果商店的最简流程

无需Mac电脑，无需安装xcode和transporter，其实使用hbuilderx开发的ios软件，也可以上架到苹果的app store商店的。只需要有苹果开发者中心的苹果开发者账号就行了。假如你还在了解上架阶段，还没打包，也还没有创建任…...

编程日记 2025/7/13 13:42:41

DeepSeek详解：探索下一代语言模型

文章目录前言一、什么是DeepSeek二、DeepSeek核心技术2.1 Transformer架构2.1.1 自注意力机制 (Self-Attention Mechanism)(a) 核心思想(b) 计算过程(c) 代码实现 2.1.2 多头注意力 (Multi-Head Attention)(a) 核心思想(b) 工作原理(c) 数学描述(d) 代码实现 2.1.3 位置编码 (…...

编程日记 2025/7/12 11:37:56

python的内存管理

目录 1. 引用计数 2. 垃圾收集（GC） python的内存管理主要是引用计数和垃圾回收器来进行内存管理 1. 引用计数每个 Python 对象都有一个引用计数，当引用计数为零时，对象的内存会被释放。 import sysa [] # 创建一个空列表对…...

编程日记 2025/7/4 4:33:37

【STL】list

l i s t list list 是 C C C 标准模板库（ S T L STL STL）中的一个序列容器（ S e q u e n c e C o n t a i n e r Sequence\ Container Sequence Container），它允许在容器的任意位置快速插入和删除元素，是一…...

编程日记 2025/7/13 13:54:52

证券公司主要业务分析及当前佣金最低免五情况探讨

我是StockMasterX，今日想分析证券公司主要业务，并探讨当前佣金最低且免五的证券公司情况，此议题具有一定研究价值，我从事股票交易多年，与证券公司互动频繁，前日晚间饮茶之际，浏览手机时对此深思…...

编程日记 2025/7/8 22:43:59

C++ 变量的声明与定义分离式编译与静态类型（十六）

1. 声明与定义的区别声明（declaration）：向编译器表明某个变量（或其他实体）的类型与名字，使它在后续的编译过程中可见或可用。定义（definition）：除了声明变量的名字和类…...

编程日记 2025/7/10 13:27:51

黑盒测试的等价类划分法(输入数据划分为有效的等价类和无效的等价类)

重点: 有效等价和单个无效等价各取1个即可 1、正向用例:一条尽可能覆盖多条2、逆向用例:每一条数据，都是一条单独用例。步骤: 1、明确需求 2、确定有效和无效等价 3、根据有效和无效造数据编写用例 3、适用场景针对:需要有大量数据测试输入， …...

编程日记 2025/7/13 13:04:13

通过Appium理解MCP架构

MCP即Model Context Protocol（模型上下文协议），是由Anthropic公司于2024年11月26日推出的开放标准框架，旨在为大型语言模型与外部数据源、工具及系统建立标准化交互协议，以打破AI与数据之间的连接壁垒。 MCP架构与Appi…...

编程日记 2025/7/8 8:54:43

uWebSockets开发入门

一、常用C++ WebSocket开源库一些常用的 C++ WebSocket 开源库，它们支持 WebSocket 协议的实现，适用于客户端或服务器端开发。 1. Boost.Beast (推荐) 特点：基于 Boost.Asio 的高性能库，支持 HTTP/WebSocket，属于 Boost 官方库的一部分，稳定且跨平台。适用场景：需要高…...

编程日记 2025/6/28 1:37:37

Python自动化模块：开启高效编程新时代

一、写在前面在数字化时代，自动化技术已成为提高效率、降低成本的关键手段。Python 作为一种简洁、高效且功能强大的编程语言，凭借其丰富的库和框架，在自动化领域占据了举足轻重的地位，成为众多开发者的首选工具之一。从简单的文…...

编程日记 2025/7/13 9:41:26

Android7 Input（二）Linux 驱动层输入事件管理

概述在Linux系统中，将键盘，鼠标，触摸屏等这类交互设备交由Linux Input子系统进行管理，Linux Input驱动子系统由于具有良好的和用户空间交互的接口。因此Linux Input驱动子系统，不止于只管理输入类型的设备。也可以将其…...

编程日记 2025/7/10 5:32:58

前端给后端发送数据时都需要包含哪些内容？（HTTP请求的基本组成部分）

1 [TOC](1)一、**必须传递的内容**1. **URL（请求地址）** 二、**可选内容**1. **请求方法（HTTP Method）**2. **请求头（Headers）**3. **请求体（Body）**4. **其他配置** 技术无关一、必…...

编程日记 2025/7/9 23:04:21

记录vite引入sass预编译报错error during build: [vite:css] [sass] Undefined variable.问题

vite.config.ts resolve: {alias: {: path.resolve(__dirname, src),},},css: {// css预处理器preprocessorOptions: {scss: {additionalData: use "/assets/styles/block.scss" as *;,}}},block.scss $colorGreen: #00ff00;index.vue :v-deep .font-size-14{colo…...

编程日记 2025/7/9 12:26:27

智慧运维平台：赋能未来，开启高效运维新时代

在当今数字化浪潮下，企业IT基础设施、工业设备及智慧城市系统的复杂度与日俱增，传统人工运维方式已难以满足高效、精准、智能的管理需求。停机故障、低效响应、数据孤岛等问题直接影响企业运营效率和成本控制。大型智慧运维平台（AIOps, Smart…...

编程日记 2025/7/10 1:22:46

【log4j】配置Slf4j

配置Slf4j 引入lombok包 <dependency><groupId>org.projectlombok</groupId><artifactId>lombok</artifactId><version>1.18.36</version><scope>provided</scope> </dependency>引入log4j相关api <dependency…...

编程日记 2025/7/9 8:27:07

静态网页应用开发环境搭建实战教程

1. 前言静态网页开发是前端工程师的基础技能之一，无论是个人博客、企业官网还是简单的Web应用，都离不开HTML、CSS和JavaScript。搭建一个高效的开发环境，能够极大提升开发效率，减少重复工作，并优化调试体验。本教程…...

编程日记 2025/7/9 23:04:21

AP 场景架构设计（一）：OceanBase 读写分离策略解析

说明：本文内容对应的是 OceanBase 社区版，架构部分不涉及企业版的仲裁副本功能。OceanBase社区版和企业版的能力区别详见： 官网链接。概述当两种类型的业务共同运行在同一个数据库集群上时，这对数据库的配置等条件提出了较高…...

编程日记 2025/7/10 5:49:31

未来村庄智慧灯杆：点亮乡村智慧生活

在乡村振兴与数字乡村建设的时代进程中，未来村庄智慧灯杆凭借其多功能集成与智能化特性，已成为乡村基础设施建设领域的崭新焦点，为乡村生活带来了前所未有的便利，推动着乡村生活模式的深刻变革。多功能集成：一杆多能…...

编程日记 2025/7/12 14:10:49

MySQL基础语法DDLDML

目录 #1.创建和删除数据库 #2.如果有lyt就删除,没有则创建一个新的lyt #3.切换到lyt数据库下 #4.创建数据表并设置列及其属性,name是关键词要用name包围编辑 #5.删除数据表 #5.查看创建的student表 #6.向student表中添加数据,数据要与列名一一对应 #7.查询studen…...

编程日记 2025/7/11 7:29:47

利用 VSCode 配置提升 vibe coding 开发效率

利用 VSCode 配置提升 vibe coding 开发效率 Vibe Coding（氛围编程）是一种基于AI的编程方法，其核心在于通过自然语言描述软件需求，再由大规模语言模型（LLM）自动生成代码，从而实现对传统手写编程…...

编程日记 2025/7/10 22:33:10

使用 Chromedp 监听网页请求和响应

使用 Chromedp 监听网页请求和响应在进行网络爬虫的时候，有很多网站都有反爬机制，比如你想抓点数据，结果发现每次请求都带一堆奇奇怪怪的参数 —— 什么 timestamp 签名、AES 加密的字段，还有各种 Token 令牌，跟密码…...

编程日记 2025/7/10 22:40:09

AB包介绍及导出工具实现+AB包资源简单加载

Resource原理项目中建立Resources目录，资源导入内部生成项目包资源文件存储路径结论：存储在Resources下的资源，最终会存储在游戏的主体包中，发送给用户，手机系统上，如果需要做资源的更新，是…...

编程日记 2025/7/10 12:43:04

TCP/IP协议簇

文章目录应用层http/httpsDNS补充传输层TCP1. 序列号与确认机制2. 超时重传3. 流量控制（滑动窗口机制）4. 拥塞控制5. 错误检测与校验6. 连接管理总结网络层ARP**ARP 的核心功能**ARP 的工作流程1. ARP 请求（Broadcast）2. ARP 缓…...

编程日记 2025/7/9 23:10:46

vector的模拟实现01

文章目录 vector的模拟实现构造函数析构函数迭代器容量sizecapacityreverse 遍历下标[] 修改push_backpop_backinsert 结语我们大家有又见面了，给生活加点</font color red>impetus！！开启今天的编程之路今天我们来学习vector。了解一…...

编程日记 2025/7/10 5:50:25

信息学奥赛一本通 1609：【例 4】Cats Transport | 洛谷 CF311B Cats Transport

【题目链接】 ybt 1609：【例 4】Cats Transport 洛谷 CF311B Cats Transport 【题目考点】 1. 动态规划：斜率优化动规【解题思路】解法1：设a点的前缀和输入的 d d d序列是从 d 2 d_2 d2到 d n d_n dn，共n-1个数字。人…...

编程日记 2025/7/8 14:37:49

shared_ptr和 weak_ptr的详细介绍

关于 shared_ptr 和 weak_ptr 的详细介绍及使用示例： 1. shared_ptr（共享所有权智能指针） 核心特性引用计数：记录当前有多少个 shared_ptr 共享同一个对象。自动释放：当引用计数归零时，自动释放对象内存…...

编程日记 2025/7/11 7:06:28

electron打包vue2项目流程

1，安装一个node vue2 的项目 2，安装electron： npm install electron -g//如果安装还是特比慢或不想安装cnpn 淘宝镜像查看是否安装成功：electron -v 3，进入到项目目录：cd electron-demo 进入项目目录…...

编程日记 2025/7/9 8:05:22

Baklib驱动企业知识管理数字化转型

Baklib驱动知识资产激活在信息碎片化与数据爆炸的产业环境下，企业知识中台正成为重构组织智慧的核心枢纽。Baklib通过构建全生命周期知识管理模型，将分散于邮件、文档及协作系统的非结构化数据转化为可检索、可分析的标准化资产。其内置的智能分类引擎…...

编程日记 2025/7/8 6:10:05

Elasticsearch 高级

Elasticsearch 高级建议阅读顺序： Elasticsearch 入门Elasticsearch 搜索Elasticsearch 搜索高级Elasticsearch高级（本文） 1. nested 类型 1.1 介绍 Elasticsearch 中的 nested 类型允许你在文档内存储复杂的数据结构，比如一个…...

编程日记 2025/7/11 20:04:54

1--当「穷举」成为艺术：CTF暴力破解漏洞技术从入门到入刑指南(知识点讲解版)

当「穷举」成为艺术：CTF暴力破解漏洞技术从入门到入刑指南引言：论暴力破解的哲学意义 “世界上本没有漏洞，密码设得简单了，便成了漏洞。” —— 鲁迅（并没有说过） 想象你是个不会撬锁的小偷，面…...

编程日记 2025/7/9 6:36:33

jdk 支持路线图

https://www.oracle.com/java/technologies/java-se-support-roadmap.html 按照路线图得知，在2025.09 发布openjdk 25，是一个LTS版本。...

编程日记 2025/6/28 4:24:41

VsCode启用右括号自动跳过(自动重写) - 自录制gif演示

VsCode启用右括号自动跳过(自动重写) - 自录制gif演示前言不知道大家在编程时候的按键习惯是怎样的。输入完左括号后编辑器一般会自动补全右括号，输入完左括号的内容后，是按→跳过右括号还是按)跳过右括号呢？ for (int i 0; i < a.s…...

编程日记 2025/7/3 1:08:42

Android设计模式之模板方法模式

一、定义： 定义一个操作中的算法的框架，而将一些步骤延迟到子类中，使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。二、结构： AbstractClass抽象类：定义算法的骨架，包含模板方法和若干…...

编程日记 2025/7/7 13:08:00

纯个人整理，蓝桥杯使用的算法模板day1（dfs、bfs）

算法索引 dfs（深度优先搜索）bfs（广度优先搜索）迷宫树结构 dfs（深度优先搜索） 功能： 适合搜索所有的解代码模板： class Solution{public void dfs(int[][] graph, int i, int j){i…...

编程日记 2025/7/2 16:17:00

【第34节】windows原理：PE文件的导出表和导入表

目录一、导出表 1.1 导出表概述 1.2 说明与使用二、导入表 2.1 导入表概述 2.2 说明与使用一、导出表 1.1 导出表概述 （1）导出行为和导出表用途：PE文件能把自身的函数、变量或者类，提供给其他PE文件使用，这…...

编程日记 2025/7/10 20:22:22

Spring Boot事务管理详解（附银行转账案例）

一、事务基础概念事务的ACID特性： 原子性（Atomicity）：操作要么全部成功，要么全部失败一致性（Consistency）：数据在事务前后保持合法状态隔离性（Isolation）&…...

编程日记 2025/7/9 14:20:23

（头歌作业—python）3.2 个人所得税计算器(project)

第1关：个人所得税计算器任务描述本关任务：编写一个个人所得税计算器的小程序。相关知识个人所得税缴纳标准 2018 年 10 月 1 日以前，个税免征额为 3500 元/月，调整后，个税免征额为 5000 元/月， 7 级超…...

编程日记 2025/7/9 8:46:27

在一个scss文件中定义变量，在另一个scss文件中使用

_variables.scss文件 : $line-gradient-init-color: linear-gradient(90deg, #8057ff 0%, #936bff 50%, #b892ff 100%); $line-gradient-hover-color: linear-gradient(90deg, #936bff 0%, #b892ff 50%, #f781ce 100%); $line-gradient-active-color: linear-gradient(90deg, …...

编程日记 2025/7/12 21:58:42

相关文章：