Find minimum number of coins that make a given value

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

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

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...