performance - una - Encuentre la menor cantidad de monedas requerida que pueda hacer cualquier cambio de 1 a 99 centavos
la descarga de solidos suspendidos desde una mina de fosfato (27)
Aquí está mi opinión. Una cosa interesante es que necesitamos verificar las monedas mínimas necesarias para formar coin_with_max_value (25 en nuestro caso) - 1 solamente. Después de eso simplemente calcula la suma de estas monedas mínimas. A partir de ese punto, solo tenemos que agregar cierta cantidad de coin_with_max_value, para formar cualquier número hasta el costo total, dependiendo de la diferencia entre el costo total y la suma descubierta. Eso es.
Entonces, para los valores que hemos tomado, una vez que se encuentran las monedas mínimas para 24: [1, 2, 2, 5, 10, 10]. Solo necesitamos seguir agregando 25 monedas por cada 25 valores que excedan 30 (suma de monedas mínimas). La respuesta final para 99 es:
[1, 2, 2, 5, 10, 10, 25, 25, 25]
9
import itertools
import math
def ByCurrentCoins(val, coins):
for i in range(1, len(coins) + 1):
combinations = itertools.combinations(coins, i)
for combination in combinations:
if sum(combination) == val:
return True
return False
def ExtraCoin(val, all_coins, curr_coins):
for c in all_coins:
if ByCurrentCoins(val, curr_coins + [c]):
return c
def main():
cost = 99
coins = sorted([1, 2, 5, 10, 25], reverse=True)
max_coin = coins[0]
curr_coins = []
for c in range(1, min(max_coin, cost+1)):
if ByCurrentCoins(c, curr_coins):
continue
extra_coin = ExtraCoin(c, coins, curr_coins)
if not extra_coin:
print -1
return
curr_coins.append(extra_coin)
curr_sum = sum(curr_coins)
if cost > curr_sum:
extra_max_coins = int(math.ceil((cost - curr_sum)/float(max_coin)))
curr_coins.extend([max_coin for _ in range(extra_max_coins)])
print curr_coins
print len(curr_coins)
Recientemente desafié a mi compañero de trabajo a escribir un algoritmo para resolver este problema:
Encuentre la menor cantidad de monedas requeridas que puedan hacer cualquier cambio de 1 a 99 centavos. Las monedas solo pueden ser centavos (1), monedas de cinco (5), diez (10) y cuartos (25), y usted debe poder hacer cada valor de 1 a 99 (en incrementos de 1 centavo) usando esas monedas.
Sin embargo, me di cuenta de que en realidad no sé cómo hacerlo yo mismo sin examinar todas las combinaciones posibles de monedas. Tiene que haber una forma mejor de resolver este problema, pero no sé cómo se llamaría el nombre genérico para este tipo de algoritmo, y no puedo encontrar una manera de simplificarlo más allá de mirar cada solución.
Me preguntaba si alguien podría señalarme en la dirección correcta u ofrecer un algoritmo que sea más eficiente.
Aquí hay una versión simple en Python.
#!/usr/bin/env python
required = []
coins = [25, 10, 5, 1]
t = []
for i in range(1, 100):
while sum(t) != i:
for c in coins:
if sum(t) + c <= i:
t.append(c)
break
for c in coins:
while t.count(c) > required.count(c):
required.append(c)
del t[:]
print required
Cuando se ejecuta, imprime lo siguiente a stdout.
[1, 1, 1, 1, 5, 10, 10, 25, 25, 25]
El código es bastante autoexplicativo (¡gracias Python!), Pero básicamente el algoritmo es agregar la moneda más grande disponible que no te coloca sobre el total actual que estás filmando en tu lista temporal de monedas (t en este caso ) Una vez que encuentre el conjunto de monedas más eficiente para un total en particular, asegúrese de que haya al menos esa cantidad de cada moneda en la lista requerida. Hazlo por cada total de 1 a 99 centavos, y listo.
Aquí va mi solución, nuevamente en Python y usando programación dinámica. Primero, genero la secuencia mínima de monedas requerida para realizar el cambio para cada cantidad en el rango de 1.99, y de ese resultado encuentro la cantidad máxima de monedas necesarias para cada denominación:
def min_any_change():
V, C = [1, 5, 10, 25], 99
mxP, mxN, mxD, mxQ = 0, 0, 0, 0
solution = min_change_table(V, C)
for i in xrange(1, C+1):
cP, cN, cD, cQ = 0, 0, 0, 0
while i:
coin = V[solution[i]]
if coin == 1:
cP += 1
elif coin == 5:
cN += 1
elif coin == 10:
cD += 1
else:
cQ += 1
i -= coin
if cP > mxP:
mxP = cP
if cN > mxN:
mxN = cN
if cD > mxD:
mxD = cD
if cQ > mxQ:
mxQ = cQ
return {''pennies'':mxP, ''nickels'':mxN, ''dimes'':mxD, ''quarters'':mxQ}
def min_change_table(V, C):
m, n, minIdx = C+1, len(V), 0
table, solution = [0] * m, [0] * m
for i in xrange(1, m):
minNum = float(''inf'')
for j in xrange(n):
if V[j] <= i and 1 + table[i - V[j]] < minNum:
minNum = 1 + table[i - V[j]]
minIdx = j
table[i] = minNum
solution[i] = minIdx
return solution
La ejecución de min_any_change() arroja la respuesta que estábamos buscando: {''pennies'': 4, ''nickels'': 1, ''dimes'': 2, ''quarters'': 3} . Como prueba, podemos tratar de eliminar una moneda de cualquier denominación y verificar si todavía es posible realizar un cambio por cualquier cantidad en el rango de 1.99:
from itertools import combinations
def test(lst):
sums = all_sums(lst)
return all(i in sums for i in xrange(1, 100))
def all_sums(lst):
combs = []
for i in xrange(len(lst)+1):
combs += combinations(lst, i)
return set(sum(s) for s in combs)
Si probamos el resultado obtenido anteriormente, obtenemos un True :
test([1, 1, 1, 1, 5, 10, 10, 25, 25, 25])
Pero si eliminamos una sola moneda, sin importar su denominación, obtendremos una False :
test([1, 1, 1, 5, 10, 10, 25, 25, 25])
Buena pregunta. Esta es la lógica que se me ocurrió. Probado con pocos escenarios, incluido el 25.
class Program
{
//Allowable denominations
const int penny = 1;
const int nickel = 5;
const int dime = 10;
const int quarter = 25;
const int maxCurrencyLevelForTest =55; //1-n where n<=99
static void Main(string[] args)
{
int minPenniesNeeded = 0;
int minNickelsNeeded = 0;
int minDimesNeeded = 0;
int minQuartersNeeded = 0;
if (maxCurrencyLevelForTest == penny)
{
minPenniesNeeded = 1;
}
else if (maxCurrencyLevelForTest < nickel)
{
minPenniesNeeded = MinCountNeeded(penny, maxCurrencyLevelForTest);
}
else if (maxCurrencyLevelForTest < dime)
{
minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
minNickelsNeeded = MinCountNeeded(nickel, maxCurrencyLevelForTest);
}
else if (maxCurrencyLevelForTest < quarter)
{
minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
minNickelsNeeded = MinCountNeeded(nickel, dime - 1);
minDimesNeeded = MinCountNeeded(dime, maxCurrencyLevelForTest);
}
else
{
minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
minNickelsNeeded = MinCountNeeded(nickel, dime - 1);
minDimesNeeded = MinCountNeeded(dime, quarter - 1);
var maxPossilbleValueWithoutQuarters = (minPenniesNeeded * penny + minNickelsNeeded * nickel + minDimesNeeded * dime);
if (maxCurrencyLevelForTest > maxPossilbleValueWithoutQuarters)
{
minQuartersNeeded = (((maxCurrencyLevelForTest - maxPossilbleValueWithoutQuarters)-1) / quarter) + 1;
}
}
var minCoinsNeeded = minPenniesNeeded + minNickelsNeeded+minDimesNeeded+minQuartersNeeded;
Console.WriteLine(String.Format("Min Number of coins needed: {0}", minCoinsNeeded));
Console.WriteLine(String.Format("Penny: {0} needed", minPenniesNeeded));
Console.WriteLine(String.Format("Nickels: {0} needed", minNickelsNeeded));
Console.WriteLine(String.Format("Dimes: {0} needed", minDimesNeeded));
Console.WriteLine(String.Format("Quarters: {0} needed", minQuartersNeeded));
Console.ReadLine();
}
private static int MinCountNeeded(int denomination, int upperRange)
{
int remainder;
return System.Math.DivRem(upperRange, denomination,out remainder);
}
}
Algunos resultados: cuando maxCurrencyLevelForTest = 25
Min Number of coins needed: 7
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 0 needed
Cuando maxCurrencyLevelForTest = 99
Min Number of coins needed: 10
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 3 needed
maxCurrencyLevelForTest: 54
Min Number of coins needed: 8
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 1 needed
maxCurrencyLevelForTest: 55
Min Number of coins needed: 9
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 2 needed
maxCurrencyLevelForTest: 79
Min Number of coins needed: 9
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 2 needed
maxCurrencyLevelForTest: 85
Min Number of coins needed: 10
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 3 needed
El código puede ser refactorizado aún más, supongo.
Como entendí si está utilizando valores estándar del sistema monetario, es muy fácil contar el número mínimo de monedas con un solo bucle. Simplemente consuma siempre el valor máximo de la moneda y, si no es posible, verifique la siguiente opción. Pero si tienes un sistema como el que tienes monedas como 1,2,3,4, entonces no funciona. Supongo que la idea de tener monedas como 1,2,5,10,25 es hacer que la computación sea fácil para los humanos.
Después de no encontrar una buena solución para este tipo de problema en PHP, desarrollé esta función.
Toma cualquier cantidad de dinero (hasta $ 999.99) y devuelve un conjunto de la cantidad mínima de cada factura / moneda requerida para llegar a ese valor.
Primero convierte el valor en int en centavos (por alguna razón, obtendría errores al final al usar valores de float estándar).
Las denominaciones devueltas también están en peniques (es decir, 5000 = $ 50, 100 = $ 1, etc.).
function makeChange($val)
{
$amountOfMoney = intval($val*100);
$cashInPennies = array(10000,5000,2000,1000,500,100,25,10,5,1);
$outputArray = array();
$currentSum = 0;
$currentDenom = 0;
while ($currentSum < $amountOfMoney) {
if( ( $currentSum + $cashInPennies[$currentDenom] ) <= $amountOfMoney ) {
$currentSum = $currentSum + $cashInPennies[$currentDenom];
$outputArray[$cashInPennies[$currentDenom]]++;
} else {
$currentDenom++;
}
}
return $outputArray;
}
$change = 56.93;
$output = makeChange($change);
print_r($output);
echo "<br>Total number of bills & coins: ".array_sum($output);
=== OUTPUT ===
Array ( [5000] => 1 [500] => 1 [100] => 1 [25] => 3 [10] => 1 [5] => 1 [1] => 3 )
Total number of bills & coins: 11
En general, si tiene sus monedas COIN [] y su "rango de cambio" 1..MAX, lo siguiente debería encontrar la cantidad máxima de monedas.
Initialise array CHANGEVAL[MAX] to -1
For each element coin in COIN:
set CHANGEVAL[coin] to 1
Until there are no more -1 in CHANGEVAL:
For each index I over CHANGEVAL:
if CHANGEVAL[I] != -1:
let coincount = CHANGEVAL[I]
For each element coin in COIN:
let sum = coin + I
if (COINS[sum]=-1) OR ((coincount+1)<COINS[sum]):
COINS[sum]=coincount+1
No sé si el control de la minimización de monedas en el condicional interno es, estrictamente hablando, necesario. Pensaría que la cadena mínima de adiciones de monedas terminaría siendo correcta, pero es mejor prevenir que lamentar.
Escribí este algoritmo para un tipo similar de problema con DP, puede ayudar
public class MinimumCoinProblem {
private static void calculateMinumCoins(int[] array_Coins, int sum) {
int[] array_best = new int[sum];
for (int i = 0; i < sum; i++) {
for (int j = 0; j < array_Coins.length; j++) {
if (array_Coins[j] <= i && (array_best[i] == 0 || (array_best[i - array_Coins[j]] + 1) <= array_best[i])) {
array_best[i] = array_best[i - array_Coins[j]] + 1;
}
}
}
System.err.println("The Value is" + array_best[14]);
}
public static void main(String[] args) {
int[] sequence1 = {11, 9,1, 3, 5,2 ,20};
int sum = 30;
calculateMinumCoins(sequence1, sum);
}
}
Esta podría ser una solución genérica en C #
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace CoinProblem
{
class Program
{
static void Main(string[] args)
{
var coins = new int[] { 1, 5, 10, 25 }; // sorted lowest to highest
int upperBound = 99;
int numCoinsRequired = upperBound / coins.Last();
for (int i = coins.Length - 1; i > 0; --i)
{
numCoinsRequired += coins[i] / coins[i - 1] - (coins[i] % coins[i - 1] == 0 ? 1 : 0);
}
Console.WriteLine(numCoinsRequired);
Console.ReadLine();
}
}
}
No lo he pensado del todo ... es demasiado tarde en la noche. Pensé que la respuesta debería ser 9 en este caso, pero Gabe dijo que debería ser 10 ... que es lo que cede. Supongo que depende de cómo interpretes la pregunta ... estamos buscando la menor cantidad de monedas que puedan producir cualquier valor <= X, o la menor cantidad de monedas que puedan producir cualquier valor <= X usando la menor cantidad de monedas ? Por ejemplo ... Estoy bastante seguro de que podemos hacer cualquier valor con solo 9 monedas, sin monedas, pero luego para producir 9 ... necesitas ... oh ... ya veo. Necesitarías 9 centavos, que no tienes, porque eso no es lo que elegimos ... en ese caso, creo que esta respuesta es correcta. Solo una implementación recursiva de la idea de Thomas, pero no sé por qué se detuvo allí ... no es necesario forzar la fuerza bruta.
Editar: Esto está mal.
He estado aprendiendo acerca de la programación dinámica hoy, y aquí está el resultado:
coins = [1,5,10,25]
d = {} # stores tuples of the form (# of coins, [coin list])
# finds the minimum # of coins needed to
# make change for some number of cents
def m(cents):
if cents in d.keys():
return d[cents]
elif cents > 0:
choices = [(m(cents - x)[0] + 1, m(cents - x)[1] + [x]) for x in coins if cents >= x]
# given a list of tuples, python''s min function
# uses the first element of each tuple for comparison
d[cents] = min(choices)
return d[cents]
else:
d[0] = (0, [])
return d[0]
for x in range(1, 100):
val = m(x)
print x, "cents requires", val[0], "coins:", val[1]
La programación dinámica realmente es mágica.
La tarea
Find the least number of coins required, that can make any change from 1 to 99 cent.
difiere de la tarea
For each single change from 1 to 99 cent, find the least number of coins required.
porque la solución podría ser un conjunto completo de monedas diferentes.
Supongamos que no tiene (1), (5), (10) y (25) monedas de centavo, pero (1), (3), (5) y (17) monedas de centavo: para hacer el cambio de 5, solo necesitas una (5) moneda; pero para todos los cambios de 1 a 5 se necesitan dos (1) monedas y una (3) moneda, no ninguna (5) moneda.
El algoritmo codicioso itera desde el valor más pequeño al más grande, con respecto a los valores de cambio y de moneda:
With 1x(1) you get all change values below 2.
To make a change of 2, you need an additional coin,
which could have any value up to 2;
choose greedy -> choose the largest -> (1).
With 2x(1) you get all change values below 3.
To make a change of 3, you need an additional coin,
which could have any value up to 3;
choose greedy -> choose the largest -> (3).
With 2x(1)+1x(3) you get all change values below 6.
To make a change of 6, you need an additional coin,
which could have any value up to 6;
choose greedy -> choose the largest -> (5).
and so on...
Eso está en Haskell:
coinsforchange [1,3,5,17] 99
where
coinsforchange coins change =
let f (coinssofar::[Int],sumsofar::Int) (largestcoin::Int,wanttogoto::Int) =
let coincount=(max 0 (wanttogoto-sumsofar+largestcoin-1))`div`largestcoin
in (replicate coincount largestcoin++coinssofar,sumsofar+coincount*largestcoin)
in foldl f ([],0) $ zip coins $ tail [c-1|c<-coins] ++ [change]
Y en C ++:
void f(std::map<unsigned,int> &coinssofar,int &sumsofar, unsigned largestcoin, int wanttogoto)
{
int x = wanttogoto - sumsofar + largestcoin - 1;
coinssofar[largestcoin] = (x>0) ? (x / largestcoin) : 0;
//returns coinssofar and sumsofar;
}
std::map<unsigned,int> coinsforchange(const std::list<unsigned> &coins, int change)
{
std::map<unsigned,int> coinssofar;
int sumsofar=0;
std::list<unsigned>::const_iterator coin = coins.begin();
unsigned largestcoin = *coin;
for( ++coin ; coin!=coins.end() ; largestcoin=*(coin++))
f(coinssofar,sumsofar,largestcoin,(*coin) - 1);
f(coinssofar,sumsofar,largestcoin,change);
return coinssofar;
}
Lo que estás buscando es Programación Dinámica .
En realidad, no tiene que enumerar todas las combinaciones posibles para cada valor posible, porque puede compilarlo sobre las respuestas anteriores.
Tu algoritmo necesita tomar 2 parámetros:
- La lista de posibles valores de monedas, aquí
[1, 5, 10, 25] - El rango para cubrir, aquí
[1, 99]
Y el objetivo es calcular el conjunto mínimo de monedas requeridas para este rango.
La forma más simple es proceder de una manera ascendente:
Range Number of coins (in the minimal set)
1 5 10 25
[1,1] 1
[1,2] 2
[1,3] 3
[1,4] 4
[1,5] 5
[1,5]* 4 1 * two solutions here
[1,6] 4 1
[1,9] 4 1
[1,10] 5 1 * experience tells us it''s not the most viable one :p
[1,10] 4 2 * not so viable either
[1,10] 4 1 1
[1,11] 4 1 1
[1,19] 4 1 1
[1,20] 5 1 1 * not viable (in the long run)
[1,20] 4 2 1 * not viable (in the long run)
[1,20] 4 1 2
Es algo fácil, en cada paso podemos proceder sumando como máximo una moneda, solo necesitamos saber dónde. Esto se reduce al hecho de que el rango [x,y] se incluye en [x,y+1] lo que el conjunto mínimo para [x,y+1] debe incluir el conjunto mínimo para [x,y] .
Como habrás notado, a veces hay indecisiones, es decir, varios conjuntos tienen el mismo número de monedas. En este caso, solo se puede decidir más adelante cuál debería descartarse.
Debería ser posible mejorar su tiempo de ejecución, cuando me doy cuenta de que agregar una moneda generalmente te permite cubrir un rango mucho mayor que el que agregaste, creo.
Por ejemplo, tenga en cuenta que:
[1,5] 4*1 1*5
[1,9] 4*1 1*5
agregamos un centavo para cubrir [1,5] pero esto nos da hasta [1,9] gratis!
Sin embargo, cuando se trata de conjuntos de entrada escandalosos [2,3,5,10,25] para cubrir [2,99] , no estoy seguro de cómo comprobar rápidamente el rango cubierto por el nuevo conjunto, o sería realmente más eficiente .
Me encontré con este hoy, mientras estudiaba https://www.coursera.org/course/bioinformatics
DPCHANGE(money, coins)
MinNumCoins(0) ← 0
for m ← 1 to money
MinNumCoins(m) ← ∞
for i ← 1 to |coins|
if m ≥ coini
if MinNumCoins(m - coini) + 1 < MinNumCoins(m)
MinNumCoins(m) ← MinNumCoins(m - coini) + 1
output MinNumCoins(money)
Toma una cadena de denominaciones separadas por comas disponibles, y la cantidad objetivo.
Implementación de C #:
public static void DPCHANGE(int val, string denoms)
{
int[] idenoms = Array.ConvertAll(denoms.Split('',''), int.Parse);
Array.Sort(idenoms);
int[] minNumCoins = new int[val + 1];
minNumCoins[0] = 0;
for (int m = 1; m <= val; m++)
{
minNumCoins[m] = Int32.MaxValue - 1;
for (int i = 1; i <= idenoms.Count() - 1; i++)
{
if (m >= idenoms[i])
{
if (minNumCoins[m - idenoms[i]] + 1 < minNumCoins[m])
{
minNumCoins[m] = minNumCoins[m - idenoms[i]] + 1;
}
}
}
}
}
Necesitas al menos 4 centavos, ya que quieres obtener 4 como cambio, y puedes hacerlo solo con centavos.
No es óptimo tener más de 4 centavos. En lugar de 4 + x centavos, puede tener 4 centavos y x 5 centavos, que abarcan al menos el mismo rango.
Entonces tienes exactamente 4 centavos.
Necesita al menos 1 centavo, ya que quiere obtener 5 como un cambio.
No es óptimo tener más de 1 níquel. En lugar de 1 + x nickels, puede tener 1 nickel y x dimes, que abarcan al menos el mismo rango.
Entonces tienes exactamente 1 centavo.
Necesitas al menos 2 dimes, ya que quieres obtener 20.
Esto significa que tiene 4 centavos, 1 centavo y al menos 2 centavos.
Si tuviera menos de 10 monedas, tendría menos de 3 cuartos. Pero entonces el cambio máximo posible que podría obtener con todas las monedas es 4 + 5 + 20 + 50 = 79, no lo suficiente.
Esto significa que tienes al menos 10 monedas. La respuesta de Thomas muestra que, de hecho, si tienes 4 centavos, 1 centavo, 2 centavos y 3 cuartas partes, todo está bien.
Para este problema, el enfoque codicioso ofrece una mejor solución que DP u otros. Enfoque codicioso: encuentre la denominación más grande que sea menor que el valor requerido y agréguela al conjunto de monedas que se entregarán. Baje los centavos requeridos por la denominación que acaba de agregar y repita hasta que los centavos requeridos lleguen a cero.
Mi solución (enfoque codicioso) en la solución java:
public class MinimumCoinDenomination {
private static final int[] coinsDenominations = {1, 5, 10, 25, 50, 100};
public static Map<Integer, Integer> giveCoins(int requiredCents) {
if(requiredCents <= 0) {
return null;
}
Map<Integer, Integer> denominations = new HashMap<Integer, Integer>();
int dollar = requiredCents/100;
if(dollar>0) {
denominations.put(100, dollar);
}
requiredCents = requiredCents - (dollar * 100);
//int sum = 0;
while(requiredCents > 0) {
for(int i = 1; i<coinsDenominations.length; i++) {
if(requiredCents < coinsDenominations[i]) {
//sum = sum +coinsDenominations[i-1];
if(denominations.containsKey(coinsDenominations[i-1])) {
int c = denominations.get(coinsDenominations[i-1]);
denominations.put(coinsDenominations[i-1], c+1);
} else {
denominations.put(coinsDenominations[i-1], 1);
}
requiredCents = requiredCents - coinsDenominations[i-1];
break;
}
}
}
return denominations;
}
public static void main(String[] args) {
System.out.println(giveCoins(199));
}
}
Por un lado, esto ha sido respondido. Por otro lado, la mayoría de las respuestas requieren muchas líneas de código. Esta respuesta de Python no requiere muchas líneas de código, simplemente muchas líneas de pensamiento ^ _ ^:
div_round_up = lambda a, b: a // b if a % b == 0 else a // b + 1
def optimum_change(*coins):
wallet = [0 for i in range(0, len(coins) - 1)]
for j in range(0, len(wallet)):
target = coins[j + 1] - 1
target -= sum(wallet[i] * coins[i] for i in range(0, j))
wallet[j] = max(0, div_round_up(target, coins[j]))
return wallet
optimum_change(1, 5, 10, 25, 100)
# [4, 1, 2, 3]
Este es un algoritmo de cambio de escala muy simple que tal vez se puede romper para entradas que aún no he considerado, pero creo que debería ser robusto. Básicamente dice: "para agregar un nuevo tipo de moneda a la billetera, eche un vistazo a la siguiente moneda tipo N, luego agregue la cantidad de monedas nuevas necesarias para que el target = N - 1 ". Calcula que necesita al menos ceil((target - wallet_value)/coin_value) para hacerlo, y no verifica si esto también hará que todos los números ceil((target - wallet_value)/coin_value) entre ellos. Observe que la sintaxis codifica el "de 0 a 99 centavos" al agregar el número final "100", ya que produce el target final apropiado.
La razón por la que no se verifica es algo así como "si puede, automáticamente lo hará". Dicho de manera más directa, una vez que hace este paso por un centavo (valor 1), el algoritmo puede "romper" un níquel (valor 5) en cualquier subintervalo 0 - 4. Una vez que lo hace por un centavo, el algoritmo ahora puede "romper" "un centavo (valor 10). Y así.
Por supuesto, no requiere esas entradas particulares; también puedes usar monedas extrañas:
>>> optimum_change(1, 4, 7, 8, 100)
[3, 1, 0, 12]
Observe cómo ignora automáticamente la moneda 7 porque sabe que ya puede "romper" los 8 con el cambio que tiene.
Puedes encontrar rápidamente un límite superior.
Diga, toma tres cuartos. Entonces solo tendrías que completar los ''huecos'' 1-24, 26-49, 51-74, 76-99 con otras monedas.
Trivialmente, eso funcionaría con 2 dimes, 1 nickel y 4 pennies.
Entonces, 3 + 4 + 2 + 1 debería ser un límite superior para su número de monedas. Siempre que su algoritmo de fuerza bruta supere thta, puede dejar de buscar inmediatamente más profundo.
El resto de la búsqueda debe funcionar lo suficientemente rápido para cualquier propósito con programación dinámica.
(editar: respuesta fija según la observación de Gabe)
Suponiendo que está hablando de la moneda de EE. UU., Querría un algoritmo codicioso: http://en.wikipedia.org/wiki/Greedy_algorithm
En esencia, prueba todas las denominaciones de mayor a menor, tomando la mayor cantidad posible de monedas de cada una hasta que no te quede nada.
Para el caso general, consulte http://en.wikipedia.org/wiki/Change-making_problem , porque desearía usar programación dinámica o programación lineal para encontrar la respuesta a las denominaciones arbitrarias donde un algoritmo codicioso no funcionaría.
Una versión vb
Public Class Form1
Private Sub Button1_Click(ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles Button1.Click
For saleAMT As Decimal = 0.01D To 0.99D Step 0.01D
Dim foo As New CashDrawer(0, 0, 0)
Dim chg As List(Of Money) = foo.MakeChange(saleAMT, 1D)
Dim t As Decimal = 1 - saleAMT
Debug.WriteLine(t.ToString("C2"))
For Each c As Money In chg
Debug.WriteLine(String.Format("{0} of {1}", c.Count.ToString("N0"), c.moneyValue.ToString("C2")))
Next
Next
End Sub
Class CashDrawer
Private _drawer As List(Of Money)
Public Sub New(Optional ByVal QTYtwoD As Integer = -1, _
Optional ByVal QTYoneD As Integer = -1, _
Optional ByVal QTYfifty As Integer = -1, _
Optional ByVal QTYquarters As Integer = -1, _
Optional ByVal QTYdimes As Integer = -1, _
Optional ByVal QTYnickels As Integer = -1, _
Optional ByVal QTYpennies As Integer = -1)
_drawer = New List(Of Money)
_drawer.Add(New Money(2D, QTYtwoD))
_drawer.Add(New Money(1D, QTYoneD))
_drawer.Add(New Money(0.5D, QTYfifty))
_drawer.Add(New Money(0.25D, QTYquarters))
_drawer.Add(New Money(0.1D, QTYdimes))
_drawer.Add(New Money(0.05D, QTYnickels))
_drawer.Add(New Money(0.01D, QTYpennies))
End Sub
Public Function MakeChange(ByVal SaleAmt As Decimal, _
ByVal amountTendered As Decimal) As List(Of Money)
Dim change As Decimal = amountTendered - SaleAmt
Dim rv As New List(Of Money)
For Each c As Money In Me._drawer
change -= (c.NumberOf(change) * c.moneyValue)
If c.Count > 0 Then
rv.Add(c)
End If
Next
If change <> 0D Then Throw New ArithmeticException
Return rv
End Function
End Class
Class Money
''-1 equals unlimited qty
Private _qty As Decimal ''quantity in drawer
Private _value As Decimal ''value money
Private _count As Decimal = 0D
Public Sub New(ByVal theValue As Decimal, _
ByVal theQTY As Decimal)
Me._value = theValue
Me._qty = theQTY
End Sub
ReadOnly Property moneyValue As Decimal
Get
Return Me._value
End Get
End Property
Public Function NumberOf(ByVal theAmount As Decimal) As Decimal
If (Me._qty > 0 OrElse Me._qty = -1) AndAlso Me._value <= theAmount Then
Dim ct As Decimal = Math.Floor(theAmount / Me._value)
If Me._qty <> -1D Then ''qty?
''limited qty
If ct > Me._qty Then ''enough
''no
Me._count = Me._qty
Me._qty = 0D
Else
''yes
Me._count = ct
Me._qty -= ct
End If
Else
''unlimited qty
Me._count = ct
End If
End If
Return Me._count
End Function
ReadOnly Property Count As Decimal
Get
Return Me._count
End Get
End Property
End Class
End Class
Editar: Como lo comentaron los comentaristas, he malinterpretado la pregunta. (La pregunta es muy similar a un problema básico de CS que veo que los estudiantes de la universidad tienen que resolver ...) waves hand Esta no es la respuesta que estás buscando. Dicho esto, si bien la respuesta original es incorrecta, podemos usarla como un trampolín hacia una solución O ( n ).
Por lo tanto, tome la respuesta incorrecta a continuación, que solo resuelve para un valor único (es decir, la acuñación mínima requerida para 68 centavos) y simplemente ejecútelo para cada valor.
changes = []
for amount in xrange(1, 100): # [1, 99]
changes.append( run_the_algo_below( amount ) )
# Take the maximum for each coin type.
# ie, if run_the_algo_below returns (q, d, n, p):
change = [0, 0, 0, 0]
for c in changes:
change = [max(c[i], change[i] for i in xrange(0, 4)]
Ahora, esto definitivamente le dará una respuesta válida, pero ¿es una respuesta mínima? (esta es la parte más difícil. Actualmente mi instinto me dice que sí, pero todavía estoy pensando en esto ...)
( La respuesta incorrecta )
Guau. Loops? ¿Programación dinámica? ¿De verdad amigos?
En Python:
amount = ( your_amount_in_cents )
quarters = amount // 25
dimes = amount % 25 // 10
nickels = amount % 25 % 10 // 5
pennies = amount % 25 % 10 % 5
Probablemente algunas de esas operaciones de módulo se puedan simplificar ...
Esto no es difícil, solo debes pensar en cómo realizas el cambio en la vida real. Cedes cuartos hasta que agregar otro trimestre te ponga por encima de la cantidad deseada, repartes monedas de diez centavos hasta que agregar otro centavo te ponga por encima de la cantidad deseada, y así sucesivamente. Luego, conviértase en operaciones matemáticas: módulo y división. La misma solución aplica para dólares, convirtiendo segundos en HH: MM: SS, etc.
Example Program:
#include<stdio.h>
#define LEN 9 // array length
int main(){
int coins[LEN]={0,0,0,0,0,0,0,0,0}; // coin count
int cointypes[LEN]={1000,500,100,50,20,10,5,2,1}; // declare your coins and note here {ASC order}
int sum =0; //temp variable for sum
int inc=0; // for loop
int amount=0; // for total amount
printf("Enter Amount :");
scanf("%d",&amount);
while(sum<amount){
if((sum+cointypes[inc])<=amount){
sum = sum+ cointypes[inc];
//printf("%d[1] - %d/n",cointypes[inc],sum);
//switch case to count number of notes and coin
switch(cointypes[inc]){
case 1000:
coins[0]++;
break;
case 500:
coins[1]++;
break;
case 100:
coins[2]++;
break;
case 50:
coins[3]++;
break;
case 20:
coins[4]++;
break;
case 10:
coins[5]++;
break;
case 5:
coins[6]++;
break;
case 2:
coins[7]++;
break;
case 1:
coins[8]++;
break;
}
}else{
inc++;
}
}
printf("note for %d in/n note 1000 * %d/n note 500 * %d/n note 100 * %d/n note 50 * %d/n note 20 * %d/n note 10 * %d/n coin 5 * %d/n coin 2 * %d/n coin 1 * %d/n",amount,coins[0],coins[1],coins[2],coins[3],coins[4],coins[5],coins[6],coins[7],coins[8]);
}
Here''s a simple c# solution using Linq.
internal class Program
{
public static IEnumerable<Coin> Coins = new List<Coin>
{
new Coin {Name = "Dime", Value = 10},
new Coin {Name = "Penny", Value = 1},
new Coin {Name = "Nickel", Value = 5},
new Coin {Name = "Quarter", Value = 25}
};
private static void Main(string[] args)
{
PrintChange(34);
Console.ReadKey();
}
public static void PrintChange(int amount)
{
decimal remaining = amount;
//Order coins by value in descending order
var coinsDescending = Coins.OrderByDescending(v => v.Value);
foreach (var coin in coinsDescending)
{
//Continue to smaller coin when current is larger than remainder
if (remaining < coin.Value) continue;
// Get # of coins that fit in remaining amount
var quotient = (int)(remaining / coin.Value);
Console.WriteLine(new string(''-'',28));
Console.WriteLine("{0,10}{1,15}", coin.Name, quotient);
//Subtract fitting coins from remaining amount
remaining -= quotient * coin.Value;
if (remaining <= 0) break; //Exit when no remainder left
}
Console.WriteLine(new string(''-'', 28));
}
public class Coin
{
public string Name { get; set; }
public int Value { get; set; }
}
}
Inspired from this https://www.youtube.com/watch?v=GafjS0FfAC0 following
1) optimal sub problem 2) Overlapping sub problem principles introduced in the video
using System;
using System.Collections.Generic;
using System.Linq;
namespace UnitTests.moneyChange
{
public class MoneyChangeCalc
{
private static int[] _coinTypes;
private Dictionary<int, int> _solutions;
public MoneyChangeCalc(int[] coinTypes)
{
_coinTypes = coinTypes;
Reset();
}
public int Minimun(int amount)
{
for (int i = 2; i <= amount; i++)
{
IList<int> candidates = FulfillCandidates(i);
try
{
_solutions.Add(i, candidates.Any() ? (candidates.Min() + 1) : 0);
}
catch (ArgumentException)
{
Console.WriteLine("key [{0}] = {1} already added", i, _solutions[i]);
}
}
int minimun2;
_solutions.TryGetValue(amount, out minimun2);
return minimun2;
}
internal IList<int> FulfillCandidates(int amount)
{
IList<int> candidates = new List<int>(3);
foreach (int coinType in _coinTypes)
{
int sub = amount - coinType;
if (sub < 0) continue;
int candidate;
if (_solutions.TryGetValue(sub, out candidate))
candidates.Add(candidate);
}
return candidates;
}
private void Reset()
{
_solutions = new Dictionary<int, int>
{
{0,0}, {_coinTypes[0] ,1}
};
}
}
}
Casos de prueba:
using NUnit.Framework;
using System.Collections;
namespace UnitTests.moneyChange
{
[TestFixture]
public class MoneyChangeTest
{
[TestCaseSource("TestCasesData")]
public int Test_minimun2(int amount, int[] coinTypes)
{
var moneyChangeCalc = new MoneyChangeCalc(coinTypes);
return moneyChangeCalc.Minimun(amount);
}
private static IEnumerable TestCasesData
{
get
{
yield return new TestCaseData(6, new[] { 1, 3, 4 }).Returns(2);
yield return new TestCaseData(3, new[] { 2, 4, 6 }).Returns(0);
yield return new TestCaseData(10, new[] { 1, 3, 4 }).Returns(3);
yield return new TestCaseData(100, new[] { 1, 5, 10, 20 }).Returns(5);
}
}
}
}
Solution with greedy approach in java is as below :
public class CoinChange {
public static void main(String args[]) {
int denominations[] = {1, 5, 10, 25};
System.out.println("Total required coins are " + greeadApproach(53, denominations));
}
public static int greeadApproach(int amount, int denominations[]) {
int cnt[] = new int[denominations.length];
for (int i = denominations.length-1; amount > 0 && i >= 0; i--) {
cnt[i] = (amount/denominations[i]);
amount -= cnt[i] * denominations[i];
}
int noOfCoins = 0;
for (int cntVal : cnt) {
noOfCoins+= cntVal;
}
return noOfCoins;
}
}
But this works for single amount. If you want to run it for range, than we have to call it for each amount of range.
There are a couple of similar answers up there but my solution with Java seems a little easier to understand. Check this out.
public static int findMinimumNumberOfCoins(int inputCents) {
// Error Check, If the input is 0 or lower, return 0.
if(inputCents <= 0) return 0;
// Create the List of Coins that We need to loop through. Start from highest to lowewst.
// 25-10-5-1
int[] mCoinsArray = getCoinsArray();
// Number of Total Coins.
int totalNumberOfCoins = 0;
for(int i=0; i < mCoinsArray.length; i++) {
// Get the Coin from Array.
int coin = mCoinsArray[i];
// If there is no inputCoin Left, simply break the for-loop
if(inputCents == 0) break;
// Check If we have a smaller input than our coin
// If it''s, we need to go the Next one in our Coins Array.
// e.g, if we have 8, but the current index of array is 10, we need to go to 5.
if(inputCents < coin) continue;
int quotient = inputCents/coin;
int remainder = inputCents%coin;
// Add qutient to number of total coins.
totalNumberOfCoins += quotient;
// Update the input with Remainder.
inputCents = remainder;
}
return totalNumberOfCoins;
}
// Create a Coins Array, from 25 to 1. Highest is first.
public static int[] getCoinsArray() {
int[] mCoinsArray = new int[4];
mCoinsArray[0] = 25;
mCoinsArray[1] = 10;
mCoinsArray[2] = 5;
mCoinsArray[3] = 1;
return mCoinsArray;
}
This the code in c# to find the solution.
public struct CoinCount
{
public int coinValue;
public int noOfCoins;
}
/// <summary>
/// Find and returns the no of coins in each coins in coinSet
/// </summary>
/// <param name="coinSet">sorted coins value in assending order</param>
/// <returns></returns>
public CoinCount[] FindCoinsCountFor1to99Collection(int[] coinSet)
{
// Add extra coin value 100 in the coin set. Since it need to find the collection upto 99.
CoinCount[] result = new CoinCount[coinSet.Length];
List<int> coinValues = new List<int>();
coinValues.AddRange(coinSet);
coinValues.Add(100);
// Selected coin total values
int totalCount = 0;
for (int i = 0; i < coinValues.Count - 1; i++)
{
int count = 0;
if (totalCount <= coinValues[i])
{
// Find the coins count
int remainValue = coinValues[i + 1] - totalCount;
count = (int)Math.Ceiling((remainValue * 1.0) / coinValues[i]);
}
else
{
if (totalCount <= coinValues[i + 1])
count = 1;
else
count = 0;
}
result[i] = new CoinCount() { coinValue = coinValues[i], noOfCoins = count };
totalCount += coinValues[i] * count;
}
return result;
}
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
public class LeastNumofCoins
{
public int getNumofCoins(int amount)
{
int denominations[]={50,25,10,5,2,1};
int numOfCoins=0;
int index=0;
while(amount>0)
{
int coin=denominations[index];
if(coin==amount)
{
numOfCoins++;
break;
}
if(coin<=amount)
{
amount=amount-coin;
numOfCoins++;
}
else
{
index++;
}
}
return numOfCoins;
}
public static void main(String[] args) throws IOException
{
Scanner scanner= new Scanner(new InputStreamReader(System.in));
System.out.println("Enter the Amount:");
int amoount=scanner.nextInt();
System.out.println("Number of minimum coins required to make "+ amoount +" is "+new LeastNumofCoins().getNumofCoins(amoount));
scanner.close();
}
}