From: Andreas Launila <ruby-talk@...>
Date: 2008-11-06T18:32:39+09:00
Subject: Re: Combination of numbers in an array that add up to x

Hae Lee wrote:
> Axel Etzold wrote:
>> There is Gecoder for combinatorial optimization problems in Ruby :
>>
>> http://gecoder.rubyforge.org/
>>
> 
> Thanks so much!  I downloaded and installed Gecoder with Gecode and 
> checked out the few examples, etc. available on the mentioned URL.  I 
> couldn't figure it out much yesterday when I first reviewed it, but I'll 
> practice using it to become efficient with it - it looks like it can 
> come in handy for different / other scenarios.

The simplest way to solve this problem in Gecode/R is probably to use
set variables:

  require 'rubygems'
  require 'gecoder'

  weights = [2429.63, 497.87, 51.96, 59.43, 138.4, 66.22, 28.74, 1.75,
    2075.13, 556.14, 112.56, 116.5, 84.41, 55.97, 139.07, 24.46]
  # Convert to integers.
  weights.map!{ |x| (x*100).floor }

  solution = Gecode.solve do
    selected_weights_is_a set_var([], weights)
    selected_weights.sum.must == 343578

    branch_on selected_weights
  end
  p solution.selected_weights.value.map{ |x| x.to_f / 100 }

Output:

  [1.75, 112.56, 116.5, 138.4, 139.07, 497.87, 2429.63]

The variable "selected_weights" is a set variable that may include any
of the elements in "weights". A constraint is then placed on the sum of
that set.

-- 
Andreas Launila