Find minimum number of coins that make a given value

From Rosetta Code
Find minimum number of coins that make a given value is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Task
Find minimum number of coins that make a given value


coins = [1,2,5,10,20,50,100,200]
value = 988

Coins are:
4*200
1*100
1*50
1*20
1*10
1*5
1*2
1*1

Factor

Works with: Factor version 0.99 2021-06-02

<lang factor>USING: assocs kernel math math.order prettyprint sorting ;

make-change ( value coins -- assoc )
   [ >=< ] sort [ /mod swap ] zip-with nip ;

988 { 1 2 5 10 20 50 100 200 } make-change .</lang>

Output:
{
    { 200 4 }
    { 100 1 }
    { 50 1 }
    { 20 1 }
    { 10 1 }
    { 5 1 }
    { 2 1 }
    { 1 1 }
}

Julia

Long version

Using a linear optimizer for this is serious overkill, but why not? <lang julia>using JuMP, GLPK

model = Model(GLPK.Optimizer) @variable(model, ones, Int) @variable(model, twos, Int) @variable(model, fives, Int) @variable(model, tens, Int) @variable(model, twenties, Int) @variable(model, fifties, Int) @variable(model, onehundreds, Int) @variable(model, twohundreds, Int) @constraint(model, ones >= 0) @constraint(model, twos >= 0) @constraint(model, fives >= 0) @constraint(model, tens >= 0) @constraint(model, twenties >= 0) @constraint(model, fifties >= 0) @constraint(model, onehundreds >= 0) @constraint(model, twohundreds >= 0) @constraint(model, 988 == 1ones +2twos + 5fives + 10tens + 20twenties + 50fifties + 100onehundreds + 200twohundreds)

@objective(model, Min, ones + twos + fives + tens + twenties + fifties + onehundreds + twohundreds)

optimize!(model) println("Optimized total coins: ", objective_value(model)) for val in [ones, twos, fives, tens, twenties, fifties, onehundreds, twohundreds] 

   println("Value of ", string(val), " is ", value(val))

end

</lang>

Output:
Optimized total coins: 11.0
Value of ones is 1.0
Value of twos is 1.0
Value of fives is 1.0
Value of tens is 1.0
Value of twenties is 1.0
Value of fifties is 1.0
Value of onehundreds is 1.0
Value of twohundreds is 4.0

Brief REPL command version

julia> accumulate((x, y) -> (x[1] % y, (y, x[1] ÷ y)), [200, 100, 50, 20, 10, 5, 2, 1], init=(988, 0))
8-element Vector{Tuple{Int64, Tuple{Int64, Int64}}}:
 (188, (200, 4))
 (88, (100, 1))
 (38, (50, 1))
 (18, (20, 1))
 (8, (10, 1))
 (3, (5, 1))
 (1, (2, 1))
 (0, (1, 1))

REXX

A check was made to check if an exact pay─out isn't possible.

The total number of coins paid─out is also shown. <lang rexx>/*REXX pgm finds & displays the minimum number of coins which total to a specified value*/ parse arg $ coins /*obtain optional arguments from the CL*/ if $= | $="," then $= 988 /*Not specified? Then use the default.*/ if coins= | coins="," then coins= 1 2 5 10 20 50 100 200 /* ... " " " " */

  1. = words(coins) /*#: is the number of allowable coins.*/

w= 0 /*width of largest coin (for alignment)*/ 

       do j=1  for #;   @.j= word(coins, j)     /*assign all coins to an array  (@.).  */
       w= max(w, length(@.j) )                  /*find the width of the largest coin.  */
       end   /*j*/

say 'available coin denominations: ' coins /*shown list of available denominations*/ say say center(' making change for ' $, 30 ) /*display title for the upcoming output*/ say center( , 30, "─") /* " sep " " " " */ koins= 0 /*the total number of coins dispensed. */ paid= 0 /*the total amount of money paid so far*/ 

       do k=#  by -1  for #;  z= $ % @.k        /*start with largest coin for payout.  */
       if z<1  then iterate                     /*if Z is not positive, then skip coin.*/
       koins= koins + z
       paid= z * @.k                            /*pay out a number of coins.           */
       $= $ - paid                              /*subtract the pay─out from the $ total*/
       say right(z,9) ' of coin ' right(@.k, w) /*display how many coins were paid out.*/
       end   /*k*/

say center( , 30, "─") /* " sep " " " " */ say say 'number of coins dispensed: ' koins if $>0 then say 'exact payout not possible.' /*There a residue? Payout not possible*/ exit 0 /*stick a fork in it, we're all done. */</lang>

output   when using the default inputs:
available coin denominations:  1 2 5 10 20 50 100 200

    making change for  988
──────────────────────────────
        4  of coin  200
        1  of coin  100
        1  of coin   50
        1  of coin   20
        1  of coin   10
        1  of coin    5
        1  of coin    2
        1  of coin    1
──────────────────────────────

number of coins dispensed:  11

Python

<lang python>def makechange(denominations = [1,2,5,10,20,50,100,200], total = 988): 

   print(f"Available denominations: {denominations}. Total is to be: {total}.")
   coins, remaining = sorted(denominations, reverse=True), total
   for n in range(len(coins)):
       coinsused = remaining // coins[n]
       if coinsused > 0:
           remaining -= coinsused * coins[n]
           print("   ", coinsused, "*", coins[n])

makechange()

</lang>

Output:
Available denominations: [1, 2, 5, 10, 20, 50, 100, 200]. Total is to be: 988.
    4 * 200
    1 * 100
    1 * 50
    1 * 20
    1 * 10
    1 * 5
    1 * 2
    1 * 1

Ring

<lang ring> load "stdlib.ring"

see "working..." + nl see "Coins are:" + nl sum = 988

sumCoins = 0 coins = [1,2,5,10,20,50,100,200] coins = reverse(coins)

for n = 1 to len(coins) 

   nr = floor(sum/coins[n])
   if nr > 0
      sumCoins= nr*coins[n]
      sum -= sumCoins    
      see "" + nr + "*" + coins[n] + nl
   ok

next

see "done..." + nl </lang>

Output:
working...
Coins are:
4*200
1*100
1*50
1*20
1*10
1*5
1*2
1*1
done...
Retrieved from "https://rosettacode.org/wiki/Find_minimum_number_of_coins_that_make_a_given_value?oldid=314861"