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

选硬币该用动态规划

选硬币:
现有面值分别为1角1分,5分,1分的硬币,请给出找1角5分钱的最佳方案。

#include <iostream>
#include <vector>std::vector<int> findChange(int amount) {std::vector<int> coins = {11, 5, 1}; // 按面值从大到小排序的硬币面值std::vector<int> result(coins.size(), 0); // 用于存储每种硬币的数量for (int i = 0; i < coins.size(); i++) {int numCoins = amount / coins[i]; // 计算当前硬币面值的数量result[i] = numCoins; // 存储数量amount -= numCoins * coins[i]; // 更新剩余金额}return result;
}int main() {int amount = 15; // 需要找零的金额,单位为分std::vector<int> change = findChange(amount);std::cout << "找零方案为:" << std::endl;std::cout << "1角1分硬币数量:" << change[0] << std::endl;std::cout << "5分硬币数量:" << change[1] << std::endl;std::cout << "1分硬币数量:" << change[2] << std::endl;return 0;
}

一开始我想的很简单,以为是简单的求整除数。
但要是你仔细一想,这肯定是不对的,不是所有问题都能用贪心。
在求最优的过程中,贪心和动态规划一直是一对冤家,到底选择哪个,难道了很多英雄好汉,所以最好的方式就是具体问题具体分析,只有结合实际情况才能选出最适合问题的算法。
我们都知道贪心的局限性,只能求出其中一个解的,但是不是最优需要考量。
让我们来看一下用上面贪心求出来的解:
在这里插入图片描述
但这肯定不是最优解,我们在找零的时候遵循的规则是用最少的钱张数交给别人,这样才方便。
所以最佳找零方案为:
1角1分硬币数量:0
5分硬币数量:3
1分硬币数量:0
让我们来看看用动态规划写出来的代码:

#include <iostream>
using namespace std;const int N = 10005;
const int INF = 0x3f3f3f3f; 
int f[N], a[N];int main() {int n, w;cin >> n >> w;for (int i = 0; i < n; i++) {cin >> a[i];}for (int i = 1; i <= w; i++) {f[i] = INF;}for (int i = 0; i < n; i++) {for (int j = a[i]; j <= w; j++) {f[j] = min(f[j], f[j - a[i]] + 1);}}if (f[w] == INF) {cout << -1; } else {cout << f[w];}return 0;
}

在这里插入图片描述
结果和我们预期的完全一样

总结

选硬币在动态规划中是一种叫状态表示的题型,通常用一维/二维的数组组成状态转移方程,通过更新数组来达到获取最优解的目标

相关文章:

选硬币该用动态规划

选硬币&#xff1a; 现有面值分别为1角1分&#xff0c;5分&#xff0c;1分的硬币&#xff0c;请给出找1角5分钱的最佳方案。 #include <iostream> #include <vector>std::vector<int> findChange(int amount) {std::vector<int> coins {11, 5, 1}; /…...

LeetCode 2342. 数位和相等数对的最大和:哈希表

【LetMeFly】2342.数位和相等数对的最大和&#xff1a;哈希表 力扣题目链接&#xff1a;https://leetcode.cn/problems/max-sum-of-a-pair-with-equal-sum-of-digits/ 给你一个下标从 0 开始的数组 nums &#xff0c;数组中的元素都是 正 整数。请你选出两个下标 i 和 j&…...

Vulkan渲染引擎开发教程 一、开发环境搭建

一 安装 Vulkan SDK Vulkan SDK 就是我们要搞的图形接口 首先到官网下载SDK并安装 https://vulkan.lunarg.com/sdk/home 二 安装 GLFW 窗口库 GLFW是个跨平台的小型窗口库&#xff0c;也就是显示窗口&#xff0c;图形的载体 去主页下载并安装&#xff0c;https://www.glfw.…...

(带教程)商业版SEO关键词按天计费系统:关键词排名优化、代理服务、手机自适应及搭建教程

源码简介&#xff1a; 1、会员管理&#xff1a; 该系统分为三个级别的会员流程&#xff1a;总站管理员、代理与会员&#xff08;会员有普通会员、中级会员和高级会员三个等级&#xff09;。总站管理员可以添加代理用户并为其充值余额&#xff0c;代理用户可以为普通用户充值余…...

IDEA 快捷键汇总

目录 1、altinsert 2、ctrl/ 3、altenter 4、alt回车 5、ctrlD 6、ctrlaltL 7、ctrl点击 8、alt左键向下拉 9、ctrlaltv 10、ctrlaltwint 1、altinsert 快速创建代码&#xff0c;可以快速创建类中get set tostring等方法 2、ctrl/ 单行注释 3、altenter…...

目标检测YOLO实战应用案例100讲-基于机器视觉的水稻病虫害监测预警

目录 前言 国内外研究现状 国外研究现状 国内研究现状 2 相关理论与技术...

OrthoNets:正交信道注意网络

文章目录 摘要1、简介2、相关工作3、方法4、实验设置及结果5、论述6、结论摘要 链接:https://arxiv.org/pdf/2311.03071v2.pdf 设计有效的通道注意力机制要求人们找到一种有损压缩方法,以实现最佳特征表示。尽管该领域近年来取得了进展,但仍然存在一个未解决的问题。FcaNet…...

C_12练习题

一、单项选择题(本大题共20小题,每小题2分&#xff0c;共40分。在每小题给出的四个备选项中&#xff0c;选出一个正确的答案&#xff0c;并将所选项前的字母填写在答题纸的相应位置上。) C 风格的注释&#xff0c;也称块注释或多行注释&#xff0c;以&#xff08;&#xff09;…...

导航守卫有哪三种?

导航守卫主要分为三种&#xff1a; 全局前置守卫&#xff1a;使用 router.beforeEach 注册&#xff0c;作用是在路由切换开始前进行拦截和处理&#xff0c;可以用来进行一些全局的权限校验、登录状态检查等操作。 全局解析守卫&#xff1a;使用 beforeResolve 注册&#xff0c…...

强烈 推荐 13 个 Web前端在线代码IDE

codesandbox.io&#xff08;国外&#xff0c;提供免费空间&#xff09; 网址&#xff1a;https://codesandbox.io/ CodeSandbox 专注于构建完整的 Web 应用程序&#xff0c;支持多种流行的前端框架和库&#xff0c;例如 React、Vue 和 Angular。它提供了一系列增强的功能&…...

网络协议 WebSocket

一、介绍 WebSocket 是基于 TCP 的一种新的网络协议。它实现了浏览器与服务器全双工通信——浏览器和服务器只需要完成一次握手&#xff0c;两者之间就可以创建持久性的连接&#xff0c; 并进行双向数据传输 1、HTTP协议和WebSocket协议对比 HTTP 是短连接WebSocket 是长连接H…...

路径操作 合法路径名

python中路径的三种合法表示&#xff1a;在路径前面加上r、分隔符使用/。 在路径前面加上r python中在前面加上r&#xff0c;是防止字符转义。 例如&#xff1a;这样一个路径&#xff1a; \Undergraduate\School\Programme\Python_Learnpython会将这个字符串的**\和\后面的…...

JavaEE初阶 01 计算机是如何工作的

前言 今天开始进行对JavaEE的一些基本总结,希望大家能在阅读中有所收获,如有错误还望多多指正. 1.冯诺依曼体系结构 这个体系结构相信学计算机的同学都不陌生,但是你真的知道这个体系结构说的是什么嘛?请听我娓娓道来.首先我先给出一张冯诺依曼体系结构的简图 你可以理解为当前…...

【shell 常用脚本30例】

先了解下编写Shell过程中注意事项 开头加解释器&#xff1a;#!/bin/bash语法缩进&#xff0c;使用四个空格&#xff1b;多加注释说明。命名建议规则&#xff1a;全局变量名大写、局部变量小写&#xff0c;函数名小写&#xff0c;名字体现出实际作用。默认变量是全局的&#xf…...

【我和Python算法的初相遇】——体验递归的可视化篇

&#x1f308;个人主页: Aileen_0v0 &#x1f525;系列专栏:PYTHON数据结构与算法学习系列专栏&#x1f4ab;"没有罗马,那就自己创造罗马~" 目录 递归的起源 什么是递归? 利用递归解决列表求和问题 递归三定律 递归应用-整数转换为任意进制数 递归可视化 画…...

【C语言的秘密】密探—深究C语言中多组输入的秘密!

场景引入&#xff1a; 你是否在刷题过程中&#xff0c;经常遇到以下场景呢&#xff1f; 场景一&#xff1a; 场景二&#xff1a; 从这些题上都能看见输入描述中提出了一条多组输入&#xff0c;那啥是多组输入&#xff1f;如何实现它呢&#xff1f; 多组输入&#xff1a;在输入…...

ClickHouse 语法优化规则

ClickHouse 的 SQL 优化规则是基于RBO(Rule Based Optimization)&#xff0c;下面是一些优化规则 1 准备测试用表 1&#xff09;上传官方的数据集 将visits_v1.tar和hits_v1.tar上传到虚拟机&#xff0c;解压到clickhouse数据路径下 // 解压到clickhouse数据路径 sudo tar -xvf…...

3-运行第一个docker image-hello world

CentOS7.9下安装完成docker后,我们开始部署第一个docker image-hello world 1.以root用户登录CentOS7.9服务器,拉取centos7 images 命令: docker pull hello-world [root@centos79 ~]# docker pull hello-world Using default tag: latest latest: Pulling from library…...

【漏洞复现】泛微e-Weaver SQL注入

漏洞描述 泛微e-Weaver&#xff08;FANWEI e-Weaver&#xff09;是一款广泛应用于企业数字化转型领域的集成协同管理平台。作为中国知名的企业级软件解决方案提供商&#xff0c;泛微软件&#xff08;广州&#xff09;股份有限公司开发和推广了e-Weaver平台。 泛微e-Weaver旨在…...

「git 系列」git 如何存储代码的?

这里写自定义目录标题 git 文件存储位置git 数据模型示例分析分析前准备命令哈希值 具体示例 不同版本的提交&#xff0c;git 做了什么工作&#xff1f;snapshot vs delta-based vs backup参考资料 git 文件存储位置 想要了解如何存储&#xff0c;首先需要知道存储位置。 当我…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

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…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...