初识贪心----硬币支付问题
2023-03-14 09:45:05 时间
题目:
有1元,5元,10元,50元,100元,500元的硬币各c1,c5,c10,c50,c100,c500枚。现在要用这些硬币来支付A元,最少需要多少枚硬币?假定本题至少存在一种支付方案。0≤ci≤109,0≤A≤109
输入:第一行有六个数字,分别代表从小到大6种面值的硬币的个数,第二行为A,代表需支付的A元。
样例:
输入:
3 2 1 3 0 2 620
输出:
6
分析:如果我们每次选面值尽可能大的,就能保证硬币数越小,(可用反证法证明正确性)。因为不用大面值,将使用更多的小面值硬币,一定得不到最优解。
代码:
import java.util.Scanner; public class 硬币支付 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); for (int i = 0; i < 6; i++) { cnts[i] = sc.nextInt(); } int A = sc.nextInt(); int res = f(A, 5); System.out.println(res); } static int[] cnts = new int[6]; static int[] coins = { 1, 5, 10, 50, 100, 500 }; static int f(int A, int cur) { if (A <= 0) return 0; if (cur == 0) return A; int coinValue = coins[cur]; int x = A / coinValue;// 金额有多少个coinValue int cnt = cnts[cur];// 当前面值的硬币有cnt个 int t = Math.min(x, cnt); return t + f(A - t * coinValue, cur - 1);// 用t个当前面值,剩下的继续处理 } }
结果:
相关文章
- Python-OpenCV教程-4
- java io库_Java IO类库之PipedWriter
- keyfactory java_Java KeyFactory getAlgorithm()用法及代码示例
- python TCP通信实例
- 【Java】Java人民币单位转换:分转换成元
- java.lang.ClassNotFoundException和java.lang.NoClassDefFoundError的区别
- python:isinstance()和issubclass()
- 关于 java:MyBatis 中的多线程服务器客户端
- Python Flask教程(一)
- web python -- WSGI接口
- 17 Python - 迭代
- PYTHON2.day07
- java join yield_java多线程 join/yield
- Java UDP通信:Java DatagramSocket类和DatagramPacket类
- 1.5的java,Java 1.5新特性
- java stringbuffer原理_java String、StringBuffer、StringBuilder 的区别
- python las转txt
- hadoop java文件_使用java api操作Hadoop文件
- java model监听_Java BpmnModel.getFlowElement方法代码示例
- Unchecked assignment:'java.util.Map' to 'java.util.Map'