Dada una cantidad, encuentre el número mínimo de billetes de diferentes denominaciones que suman la cantidad dada. Comenzando por el billete de mayor denominación, intente acomodar tantos billetes como sea posible para una cantidad determinada.
Podemos suponer que tenemos un suministro infinito de billetes de valores {2000, 500, 200, 100, 50, 20, 10, 5, 1}
Ejemplos:
Input : 800
Output : Currency Count
500 : 1
200 : 1
100 : 1
Input : 2456
Output : Currency Count
2000 : 1
200 : 2
50 : 1
5 : 1
1 : 1
Este problema es una variación simple del problema de cambio de moneda . Aquí, el enfoque Greedy funciona ya que el sistema dado es canónico (consulte this y this para obtener más detalles).
A continuación se muestra la implementación del programa para encontrar el número de notas:
C++
// C++ program to accept an amount
// and count number of notes
#include <bits/stdc++.h>
using namespace std;
// function to count and
// print currency notes
void countCurrency(int amount)
{
int notes[9] = { 2000, 500, 200, 100,
50, 20, 10, 5, 1 };
int noteCounter[9] = { 0 };
// count notes using Greedy approach
for (int i = 0; i < 9; i++) {
if (amount >= notes[i]) {
noteCounter[i] = amount / notes[i];
amount = amount % notes[i];
}
}
// Print notes
cout << "Currency Count ->" << endl;
for (int i = 0; i < 9; i++) {
if (noteCounter[i] != 0) {
cout << notes[i] << " : "
<< noteCounter[i] << endl;
}
}
}
// Driver function
int main()
{
int amount = 868;
countCurrency(amount);
return 0;
}
Python3
# Python3 program to accept an amount
# and count number of notes
# Function to count and print
# currency notes
def countCurrency(amount):
notes = [2000, 500, 200, 100, 50, 20, 10, 5, 1]
notesCount = {}
for note in notes:
if amount >= note:
notesCount[note] = amount//note
amount = amount % note
print ("Currency Count ->")
for key, val in notesCount.items():
print(f"{key} : {val}")
# Driver code
amount = 868
countCurrency(amount)
# Code contributed by farzams101
Java
// Java program to accept an amount
// and count number of notes
import java.util.*;
import java.lang.*;
public class GfG{
// function to count and
// print currency notes
public static void countCurrency(int amount)
{
int[] notes = new int[]{ 2000, 500, 200, 100, 50, 20, 10, 5, 1 };
int[] noteCounter = new int[9];
// count notes using Greedy approach
for (int i = 0; i < 9; i++) {
if (amount >= notes[i]) {
noteCounter[i] = amount / notes[i];
amount = amount % notes[i];
}
}
// Print notes
System.out.println("Currency Count ->");
for (int i = 0; i < 9; i++) {
if (noteCounter[i] != 0) {
System.out.println(notes[i] + " : "
+ noteCounter[i]);
}
}
}
// driver function
public static void main(String argc[]){
int amount = 868;
countCurrency(amount);
}
/* This code is contributed by Sagar Shukla */
}
C#
// C# program to accept an amount
// and count number of notes
using System;
public class GfG{
// function to count and
// print currency notes
public static void countCurrency(int amount)
{
int[] notes = new int[]{ 2000, 500, 200, 100, 50, 20, 10, 5, 1 };
int[] noteCounter = new int[9];
// count notes using Greedy approach
for (int i = 0; i < 9; i++) {
if (amount >= notes[i]) {
noteCounter[i] = amount / notes[i];
amount = amount % notes[i];
}
}
// Print notes
Console.WriteLine("Currency Count ->");
for (int i = 0; i < 9; i++) {
if (noteCounter[i] != 0) {
Console.WriteLine(notes[i] + " : "
+ noteCounter[i]);
}
}
}
// Driver function
public static void Main(){
int amount = 868;
countCurrency(amount);
}
}
/* This code is contributed by vt_m */
PHP
<?php
// PHP program to accept an amount
// and count number of notes
// function to count and
// print currency notes
function countCurrency($amount)
{
$notes = array(2000, 500, 200, 100,
50, 20, 10, 5, 1);
$noteCounter = array(0, 0, 0, 0, 0,
0, 0, 0, 0, 0);
// count notes using
// Greedy approach
for ($i = 0; $i < 9; $i++)
{
if ($amount >= $notes[$i])
{
$noteCounter[$i] = intval($amount /
$notes[$i]);
$amount = $amount % $notes[$i];
}
}
// Print notes
echo ("Currency Count ->"."\n");
for ($i = 0; $i < 9; $i++)
{
if ($noteCounter[$i] != 0)
{
echo ($notes[$i] . " : " .
$noteCounter[$i] . "\n");
}
}
}
// Driver Code
$amount = 868;
countCurrency($amount);
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// Javascript program to accept an amount
// and count number of notes
// function to count and
// print currency notes
function countCurrency(amount)
{
let notes = [ 2000, 500, 200, 100, 50, 20, 10, 5, 1 ];
let noteCounter = Array(9).fill(0);
// count notes using Greedy approach
for (let i = 0; i < 9; i++) {
if (amount >= notes[i]) {
noteCounter[i] = Math.floor(amount / notes[i]);
amount = amount % notes[i];
}
}
// Print notes
document.write("Currency Count ->" + "<br/>");
for (let i = 0; i < 9; i++) {
if (noteCounter[i] != 0) {
document.write(notes[i] + " : "
+ noteCounter[i] + "<br/>");
}
}
}
// driver code
let amount = 868;
countCurrency(amount);
</script>
Producción:
Currency Count -> 500 : 1 200 : 1 100 : 1 50 : 1 10 : 1 5 : 1 1 : 3
Publicación traducida automáticamente
Artículo escrito por shreyanshi_arun y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA