ChangeMakingProblem solver

change_making_problem.rb

class ChangeMakingProblem

  attr_reader :values, :target

  def initialize(values)
    # sorting is not nesesary, but has good impact on speed
    @values = values.sort.reverse
  end

  def solve(target)
    @current_best = (1e9).to_i # just a big number
    @target = target # target value we want to add up to
    solution = solver # solve it
    if solution.nil? # nil if problem doesn't have solution
      nil
    else # return solution otherwise
      #convert solution to [[value0, amount0], [value1, amount1], ...]
      @values.zip(solution.state)
    end
  end

  private

  def solver(index=0, state=State.new(self))
    # backtrack if state can't become solution by adding more coins
    if (state.coins_count >= @current_best) || (state.value > target)
      return nil
    # return state if it's solution and update current_best amount of coins
    elsif (state.solution?)
      @current_best = [state.coins_count, @current_best].min
      return state
    end

    # expand every state by adding idx-th coin (from values)
    # states = [state.with_extra_coin_at_position 0, state.with_extra_coin_at_position 1, ...]
    states = (index...@values.length).map do |idx|
      # allow adding coins only to positions >= position at which we're adding now
      # (if adding coin to n-th position the only allowed next positions are >=n)
      # it should prevent expanding duplicite states like ([1,0] -> [1,1] and [0,1] -> [1,1])
      solver(idx, state.clone.add_coin!(idx))
    end

    # select only solution (remove nil states)
    # reduce states by selecting best found solution (lowest coins count)
    states.select {|s| !s.nil? } .reduce do |solution, s|
      s.coins_count < solution.coins_count ? s : solution
    end
  end
end


class State

  attr_reader :value, :coins_count, :state

  def initialize(problem, state = nil, value = 0, coins_count = 0)
    if state.nil?
      @state = Array.new(problem.values.length, 0) 
    else
      @state = Array.new(state)
    end
    @problem, @value, @coins_count = problem, value, coins_count
  end

  def add_coin!(i)
    @value += @problem.values[i]
    @state[i] += 1
    @coins_count += 1
    self
  end

  def clone
    State.new(@problem, @state, @value, @coins_count)
  end

  def solution?
    value == @problem.target
  end

end

change_making_problem_spec.rb

require_relative 'change_making_problem.rb'


describe ChangeMakingProblem do

  it 'should find solution for standart currency' do
    problem = ChangeMakingProblem.new([1,2,5,10,20])
    expect(problem.solve(27)).to eql [[20, 1], [10, 0], [5, 1], [2, 1], [1, 0]]
    expect(problem.solve(29)).to eql [[20, 1], [10, 0], [5, 1], [2, 2], [1, 0]]
  end

  it 'should find solution for nonstandart currency' do
    problem = ChangeMakingProblem.new([1,2,3,11,33])
    expect(problem.solve(69)).to eql [[33, 2], [11, 0], [3, 1], [2, 0], [1, 0]]
  end

  it 'should not find solution' do
    problem = ChangeMakingProblem.new([2,4,8,16,32])
    expect(problem.solve(127)).to eql nil
  end

end