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

洛谷 P2842 纸币问题 1 -普及-

题目描述

某国有 nnn 种纸币,每种纸币面额为 aia_iai 并且有无限张,现在要凑出 www 的金额,试问最少用多少张纸币可以凑出来?

输入格式

第一行两个整数 n,wn,wn,w,分别表示纸币的种数和要凑出的金额。
第二行一行 nnn 个以空格隔开的整数 a1,a2,a3,…ana_1, a_2, a_3, \dots a_na1,a2,a3,an 依次表示这 nnn 种纸币的面额。

输出格式

一行一个整数,表示最少使用的纸币张数。

输入输出样例 #1

输入 #1

6 15
1 5 10 20 50 100

输出 #1

2

输入输出样例 #2

输入 #2

3 15
1 5 11

输出 #2

3

说明/提示

对于 40%40\%40% 的数据,满足 n≤10n\le 10n10w≤100w\le 100w100
对于 100%100\%100% 的数据,满足 1≤n≤1031\le n\le 10^31n1031≤ai,w≤1041\le a_i , w\le 10^41ai,w104

solution

动态规划:

  • 1 定义公式:
    • 设 f[i][j]: 如果只用前 i 种纸币,最少需要多少张才能拼成 j 元。
  • 2 递推关系:
    • f[i][j] = min(f[i][j], f[i][j - a[i]] + 1, f[i-1][j])
    • 因为 i 只影响 i + 1,所以只需要保存一个,可以省略一个维度
      递推公式 f[j] = min(f[j], f[j - a[i]] + 1)
  • 3 结果
    f[w]

代码

#include<iostream>
#include "unordered_map"
#include "unordered_set"
#include "stack"
#include "queue"
#include "cstring"
#include "algorithm"using namespace std;
const int N = 1e3 + 5, INF = 1e4, M = 1e4 + 5;int a[N], n, w, f[M];int main() {cin >> n >> w;for (int i = 0; i < n; i++) cin >> a[i];for (int j = 1; j <= w; j++) {f[j] = INF;for (int i = 0; i < n; i++) {if (j >= a[i]) {f[j] = min(f[j], f[j - a[i]] + 1);}}}cout << f[w];return 0;
}

结果

在这里插入图片描述

http://www.xdnf.cn/news/1306369.html

相关文章:

  • 系统时钟配置
  • 《WINDOWS 环境下32位汇编语言程序设计》第1章 背景知识
  • ​Visual Studio 2013.5 ULTIMATE 中文版怎么安装?iso镜像详细步骤
  • 斯诺登:数据迷雾中的哨兵与棱镜裂痕的永恒回响
  • 【Python办公】Excel转json(极速版)-可自定义累加字段(如有重复KEY)
  • 疏老师-python训练营-Day46通道注意力(SE注意力)
  • w484扶贫助农系统设计与实现
  • redis-sentinel基础概念及部署
  • HarmonyOS 实战:用 @Observed + @ObjectLink 玩转多组件实时数据更新
  • ConRFT--RSS2025--中科院自动化所--2025.4.14
  • 10.0 UML的介绍以及VisualStudio中查看类图
  • 强制从不抱怨环境。
  • 电源测试系统ATECLOUD-Power,让您告别电源模块测试痛点!
  • Vue模板引用(Template Refs)全解析1
  • sqlsever的sql转postgresql的sql的方言差异
  • Java-包装类
  • 机械学习---词向量转化评价,附代码实例
  • pyecharts可视化图表-pie:从入门到精通(进阶篇)
  • ETH持续上涨推动DEX热潮,交易活跃度飙升的XBIT表现强势出圈
  • uniapp纯前端绘制商品分享图
  • 访问者模式C++
  • Android RxJava 过滤与条件操作详解
  • 数据结构初阶(17)排序算法——非比较排序、排序算法总结
  • Flink的状态管理
  • SpringCloud学习
  • 【完整源码+数据集+部署教程】孔洞检测系统源码和数据集:改进yolo11-RetBlock
  • 自适应UI设计解读 | Fathom 企业人工智能平台
  • ​​金仓数据库KingbaseES V9R1C10安装教程 - Windows版详细指南​
  • 力扣习题:基本计算器
  • 从 “碳足迹“ 到 “零碳圈“:上海零碳园区的改造密码