【贪心策略】硬币问题

绝地灬酷狼 2022-04-02 04:18 283阅读 0赞

**问题描述：**

有vi=1元、5元、10元、50元、100元、500元的硬币c1、c2、c3、c4、c5枚。若用这些硬币来凑出A元，最少需要多少枚硬币？

**贪心策略：**

初始化numOfCoins=0，若A>0

每一次都优先挑金额最大的硬币 i

若该硬币金额大于A，则挑金额次之的硬币

若该硬币金额小于A & 该硬币的剩余数量 ci 不为0，则A=A-vi，numOfCoins++

**代码实现：**

// 贪心算法————硬币问题
    
    public class CoinsTest {
    	public static void main(String[] args) {
    		int[] v = {0, 1, 5, 10, 50, 100, 500}; // 硬币的金额
    		int[] c = {0, 3, 2, 1, 3, 0, 2}; // 硬币的个数
    		int A = 620; // 数额
    		
    		int numOfCoins = 0;		  // 记录总共需要的硬币个数
    		int[] flag = new int[7];  // 记录对应的硬币被选择的次数 
    		for (int i=6; i>0; i--) {
    			// A == 0 
    			if (A == 0) {  // 代码出口
    				break;
    			}
    			// A > 0
    			while (c[i] > 0) {
    				if (v[i] > A) {
    					break;
    				} else {
    					A -= v[i];
    					c[i]--;
    					numOfCoins++;
    					flag[i]++;
    				}
    			}
    		}
    		
    		//打印方案选择的硬币个数
    		System.out.println("要凑出A元，至少需要"+ numOfCoins +"枚硬币");
    		//打印方案
    		System.out.print("所选择的硬币为：");
    		for (int i=6; i>0; i--) {
    			while (flag[i] > 0) {
    				System.out.print(v[i]+"\t");
    				flag[i]--;
    			}
    		}
    	}
    }

** 运行结果：**

![20181225122026987.png][]

[20181225122026987.png]: /images/20220402/d46c707602d14ed6ac4aa2f05142df85.png

发表评论取消回复

表情：

评论列表（有 0 条评论，283人围观）

还没有评论，来说两句吧...

相关阅读

相关硬币问题

include <bits/stdc++.h> using namespace std; const int maxn = 2e5+10;...

女爷i/ 2024年04月17日 17:52/ 0 赞/ 74 阅读

相关贪心策略入门

贪心策略入门适用场景：贪心算法贪心选择最优子结构举例（活动安排问题）

电玩女神/ 2023年07月24日 11:44/ 0 赞/ 3 阅读

相关贪心-硬币分配

硬币问题问题描述：有1元、5元、10元、50元、100元、500元的硬币各C1，C5，C10，C50，C100，C500枚。现在要用这些硬币来支付A元，最少需要多少

绝地灬酷狼/ 2023年07月17日 09:49/ 0 赞/ 15 阅读

相关 [每日一道小算法（一）][贪心算法] 硬币问题

前言：今天看到了一个有意思的算法题，准备在这里记录一下，方便以后查阅。自己的算法能力挺差的，准备开个专栏专门写算法，每天至少一篇，提升一下自己算法的能力，就从这一篇开始吧

布满荆棘的人生/ 2023年06月28日 08:55/ 0 赞/ 30 阅读

相关凑硬币问题

/ 给出k中面值的硬币，每种硬币的数量无限，再给一个总金额amount，问最少需要几枚硬币凑出这个金额，如果凑不出，返回-1 dp[i]定义：当目标金额为i时，至少

迷南。/ 2022年10月27日 13:54/ 0 赞/ 194 阅读

相关算法——硬币选择问题（dp、贪心）

`本题来自2015级算法第四次上机` `A` 怠惰的王木木Ⅱ 时间限制：1000ms 内存限制：65536kb 通过率：1/165 `(0.61%)` 正确率：1/4

绝地灬酷狼/ 2022年06月05日 23:45/ 0 赞/ 218 阅读

相关蓝桥翻硬币（贪心思维）

历届试题翻硬币时间限制：1.0s 内存限制：256.0MB 问题描述小明正在玩一个“翻硬币”的游戏。桌上放着排成一排的若干硬币。我

本是古典何须时尚/ 2022年05月29日 12:37/ 0 赞/ 213 阅读

相关【贪心策略】背包问题

问题描述：给定n个物体（它们的重量为：w1，w2，......，wn，价值为：v1，v2，......，vn）和一个承受重量为W的背包，每种物体都可以分割。问怎么选取这

た入场券/ 2022年04月10日 03:49/ 0 赞/ 229 阅读

相关【贪心策略】硬币问题

问题描述：有vi=1元、5元、10元、50元、100元、500元的硬币c1、c2、c3、c4、c5枚。若用这些硬币来凑出A元，最少需要多少枚硬币？贪心策略：初始化n

绝地灬酷狼/ 2022年04月02日 04:18/ 0 赞/ 284 阅读

相关 [算法提高] 贪心算法翻硬币

\[问题背景\] [蓝桥杯历届试题 PREV-6 翻硬币][_ PREV-6] 小明正在玩一个“翻硬币”的游戏。桌上放着排成一排的若干硬币。我们用 \ 表示正面，用

梦里梦外;/ 2022年03月02日 04:39/ 0 赞/ 242 阅读