Memoized dynamic programming solution for the coin exchange problem (16-1) in CLRS Introduction to Algorithms, Chapter 16

coinswap.rb

Val = rand(2..1000)

Denoms = [1]
100.times{ Denoms << rand(2..1000) }
Denoms.sort!

def coinswap_aux(m, i)
  r = Array.new(m + 1) { Array.new(i) }
  sols = Array.new(m + 1) { Array.new(i) }

  swaps = coinswap_memo(m, i-1, r, sols)

  return [swaps, sols]
end

def coinswap_memo(m, i, r, sols)
  return r[m][i] if r[m][i]

  if m == Denoms[i] # leftover value is equal to the current coin
    r[m][i] = 1
    sols[m][i] = 1
  elsif i == 0 # bottomed out at the first coin, pick it
    r[m][i] = coinswap_memo(m - Denoms[i], i, r, sols) + 1
    sols[m][i] = 1
  elsif m < Denoms[i] # move down a coin
    r[m][i] = coinswap_memo(m, i - 1, r, sols)
  else # decide what's best
    skip = coinswap_memo(m, i - 1, r, sols)
    pick = coinswap_memo(m - Denoms[i], i, r, sols) + 1

    if pick < skip
      r[m][i] = pick
      sols[m][i] = 1
    else
      r[m][i] = skip
    end
  end
  r[m][i]
end

def printSol(sol, val)
  chosenCoins = []

  while val > 0 do
    # Start from the last column (largest coin)
    Denoms.size.downto(0) do |i|
      if sol[val][i] == 1
        coin = Denoms[i]
        val -= coin
        chosenCoins << coin
        break
      end
    end
  end
  chosenCoins
end

minCoins, sol = coinswap_aux(Val, Denoms.size)
puts "Coins: #{Denoms}"
puts "Value #{Val} swapped with the #{minCoins} coins: #{printSol(sol, Val).join(', ')}"