Forum: Ruby Combination of numbers in an array that add up to x

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Hae L. (Guest)
on 2008-11-04 17:50
Objective: Find list of values in an array that adds up to a specific
sum.
-
I have a list of values in an array:
[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]

I want to find a combination among these numbers that adds up to a total
sum of:
3435.78

I was hoping a one-liner in irb would do the trick but I haven't found a
method, etc. that will help me do this.  Thoughts regarding?
Brian C. (Guest)
on 2008-11-04 17:59
Hae L. wrote:
> Objective: Find list of values in an array that adds up to a specific
> sum.
> -
> I have a list of values in an array:
> [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]
>
> I want to find a combination among these numbers that adds up to a total
> sum of:
> 3435.78
>
> I was hoping a one-liner in irb would do the trick but I haven't found a
> method, etc. that will help me do this.  Thoughts regarding?

Google "Knapsack problem"

It may be easier if your multiply your numbers up by 100 so you get
integers.
Axel E. (Guest)
on 2008-11-04 18:23
(Received via mailing list)
-------- Original-Nachricht --------
> Datum: Wed, 5 Nov 2008 00:58:07 +0900
> Von: Brian C. <removed_email_address@domain.invalid>
> An: removed_email_address@domain.invalid
> Betreff: Re: Combination of numbers in an array that add up to x

> > 3435.78
> >
> > I was hoping a one-liner in irb would do the trick but I haven't found a
> > method, etc. that will help me do this.  Thoughts regarding?
>
> Google "Knapsack problem"
>
> It may be easier if your multiply your numbers up by 100 so you get
> integers.
> --
> Posted via http://www.ruby-forum.com/.

Dear Hae,


There is Gecoder for combinatorial optimization problems in Ruby :

http://gecoder.rubyforge.org/

The numbers must be integers.

Best regards,

Axel
Ara H. (Guest)
on 2008-11-04 18:28
(Received via mailing list)
On Nov 4, 2008, at 8:48 AM, Hae L. wrote:

> 3435.78
>
> I was hoping a one-liner in irb would do the trick but I haven't
> found a
> method, etc. that will help me do this.  Thoughts regarding?
> --


start by installing the permutations gem (for a brute force solution).


a @ http://codeforpeople.com/
Giampiero Z. (Guest)
on 2008-11-05 15:31
Hae L. wrote:
> Objective: Find list of values in an array that adds up to a specific
> sum.
> -
> I have a list of values in an array:
> [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]
>
> I want to find a combination among these numbers that adds up to a total
> sum of:
> 3435.78
>
> I was hoping a one-liner in irb would do the trick but I haven't found a
> method, etc. that will help me do this.  Thoughts regarding?

Hi from Italy, this is my first post on this forum; I am a ruby
beginner, so I took your question as an exercise; the following is the
one solution I found (integer values):
175, 11256, 11650, 13840, 13907, 49787, 242963

v = [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]
goal = 343578
v.map! {|x| (x*100).to_i}
v.sort!
def to_binary(i)
  bin_vett = []
  loop do
    bin_vett.push(i % 2)
    i = i / 2
    break if i == 0
  end
  bin_vett.reverse
end
n = 2 ** v.size
n.times do |i|
  b = to_binary(i)
  sum = 0
  b.each_index do |j|
    sum += v[j] if b[j] == 1
  end
  if sum == goal then
    b.each_index do |j|
      print "#{v[j]}  " if b[j] == 1
    end
  end
end
Hae L. (Guest)
on 2008-11-05 16:48
Brian C. wrote:
> Google "Knapsack problem"
>
> It may be easier if your multiply your numbers up by 100 so you get
> integers.

Thanks so much for the suggestion.  I learned a little about the
knapsack problem from the initial googling sessions, but unfortunately,
there weren't many suggestions regarding how to put something together
in the search hits I first checked. I will follow up on the topic as
time permits - it seems like an interesting concept to become familiar
with.  Thanks so much!
Hae L. (Guest)
on 2008-11-05 16:52
Axel E. wrote:
> Dear Hae,
>
>
> There is Gecoder for combinatorial optimization problems in Ruby :
>
> http://gecoder.rubyforge.org/
>
> The numbers must be integers.
>
> Best regards,
>
> Axel

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.  Thanks so much!
Hae L. (Guest)
on 2008-11-05 16:54
Ara Howard wrote:
> start by installing the permutations gem (for a brute force solution).
>
>
> a @ http://codeforpeople.com/

Hi there; thanks for your response.  I didn't notice the gem when I
checked the site you mentioned yesterday, but I will revisit to look
more closely.  It looks like an informative site - thanks for sharing!!!
Hae L. (Guest)
on 2008-11-05 16:59
Giampiero Z. wrote:
> Hi from Italy, this is my first post on this forum; I am a ruby
> beginner, so I took your question as an exercise; the following is the
> one solution I found (integer values):
> 175, 11256, 11650, 13840, 13907, 49787, 242963
>
> v = [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]
> goal = 343578
> v.map! {|x| (x*100).to_i}
> v.sort!
> def to_binary(i)
>   bin_vett = []
>   loop do
>     bin_vett.push(i % 2)
>     i = i / 2
>     break if i == 0
>   end
>   bin_vett.reverse
> end
> n = 2 ** v.size
> n.times do |i|
>   b = to_binary(i)
>   sum = 0
>   b.each_index do |j|
>     sum += v[j] if b[j] == 1
>   end
>   if sum == goal then
>     b.each_index do |j|
>       print "#{v[j]}  " if b[j] == 1
>     end
>   end
> end

Hi there!  Question: Are you sure you're a beginner?  =)  From a true
beginner's perspective, your code looks advanced!  Thanks so much!!!

When I first started trying this on my own yesterday, I'd gotten as far
as the first line in your code where I'd assigned the values in an
array.

If you get a chance, can you advise regarding the sources that you
learned from to be able to put together something like the code you
provided?  The materials I'm using aren't as helpful apparently!  =(

Thanks again!!!
Giampiero Z. (Guest)
on 2008-11-05 17:29
> If you get a chance, can you advise regarding the sources that you
> learned from to be able to put together something like the code you
> provided?  The materials I'm using aren't as helpful apparently!  =(
>
> Thanks again!!!

Ciao (Italian for Hi)
Yes, I am a ruby beginner. The script I posted here is NOT very
"Rubish". I began less than a month ago, but few hours for few days. I
am NOT a beginner as a programmer, and I feel that Ruby is quite
intuitive. What you need is to look at official documentation and write
your own lines of code. Use you preferite search engine to find a good
"ruby tutorial". It is enough, I think.
Brian C. (Guest)
on 2008-11-05 18:06
This isn't a very good solution - it probably doesn't handle cases where
they are multiple ways to reach the same subtotal - but it is good
enough to solve your particular problem.

BAG = [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]
TGT = 3435.78

seen = {0 => true}
work = {0 => BAG}    # total => [remaining items]

until work.empty?
  new_work = {}
  work.each do |tot, bag|
    bag.each_with_index do |item,i|
      nt = tot + item
      next if nt > TGT || seen[nt]
      nb = bag.dup
      nb.delete_at(i)
      if nt == TGT
        puts "Items NOT in the result set:"
        p nb
        puts "If there are no duplicates, the result set is:"
        p BAG - nb
        exit
      end
      seen[nt] = true
      new_work[nt] = nb
    end
  end
  work = new_work
end
puts "Sorry, go home"
Andreas L. (Guest)
on 2008-11-06 11:34
(Received via mailing list)
Hae L. wrote:
> 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.
Hae L. (Guest)
on 2008-11-06 16:53
Andreas L. wrote:
> 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.

Hi there; thanks so much!  Qq (quick question): How would I modify this
so that it lists each possible combination surrounded within their own
bracket sets?  I modified the weight and sum values to something I know
that'd have more than one combination, but it only spat back out just
one result set.

As you can tell, I'm less than a newb to coding and Ruby!  Sorry for the
inconvenience!  And again, thanks!
Heesob P. (Guest)
on 2008-11-06 16:56
(Received via mailing list)
2008/11/5 Hae L. <removed_email_address@domain.invalid>:
>
> I was hoping a one-liner in irb would do the trick but I haven't found a
> method, etc. that will help me do this.  Thoughts regarding?
If you really want one-liner and the solution exists, try this:

a = [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]
t = 3435.78

((s||={})[(a=a.sort_by{rand} while s[a])||a]=1
while(r=(1..a.size).map{|x|a[0,x]}.find{|y|y.inject{|z,n|z+n}==t}).nil?)||r

Regards,

Park H.
Andreas L. (Guest)
on 2008-11-06 17:53
(Received via mailing list)
Hae L. wrote:
> Andreas L. wrote:
>> The simplest way to solve this problem in Gecode/R is probably to use
>> set variables:
>>
>> [...]
>
> Hi there; thanks so much!  Qq (quick question): How would I modify this
> so that it lists each possible combination surrounded within their own
> bracket sets?
>

That is covered in
http://gecoder.rubyforge.org/documentation/searchi...
. There doesn't exist a convenience method for it, so one has to
formulate the problem as a class:

  require 'rubygems'
  require 'gecoder'

  class ArraySumProblem
    include Gecode::Mixin

    def initialize
      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 }

      selected_weights_is_a set_var([], weights)
      selected_weights.sum.must == 343578

      branch_on selected_weights
    end
  end

  ArraySumProblem.new.each_solution do |solution|
    p solution.selected_weights.value.map{ |x| x.to_f / 100 }
  end

Output:

  [1.75, 112.56, 116.5, 138.4, 139.07, 497.87, 2429.63]
  [24.46, 28.74, 51.96, 59.43, 66.22, 138.4, 139.07, 497.87, 2429.63]

If you are planning to solve several instances of the problem then you
probably want to modify the above so that the weights and target are
sent in through the constructor.
Hae L. (Guest)
on 2008-11-07 05:54
Andreas L. wrote:
> If you are planning to solve several instances of the problem then you
> probably want to modify the above so that the weights and target are
> sent in through the constructor.

Hi there!  The code excerpt worked wonderfully as I tried out different
total values with additional values in the array.  Thank you so much!!!

Regarding what you typed - I understood parts of it but the majority of
it went way over my head.  Do you mean there's a way to instruct Ruby
and Gecode/R to calculate for multiple targets using multiple weights
sets within a single .rb file??  That sounds pretty wicked cool!

Again, thanks so much!!!
Andreas L. (Guest)
on 2008-11-07 11:10
(Received via mailing list)
Hae L. wrote:
> Andreas L. wrote:
>> If you are planning to solve several instances of the problem then you
>> probably want to modify the above so that the weights and target are
>> sent in through the constructor.
>
> Regarding what you typed - I understood parts of it but the majority of
> it went way over my head.  Do you mean there's a way to instruct Ruby
> and Gecode/R to calculate for multiple targets using multiple weights
> sets within a single .rb file??  That sounds pretty wicked cool!
>

I meant that you would modify the code so that the weights and target
are sent to the constructor (initialize method) as parameters. See e.g.
[1], [2] and [3] for more information about that.

The point would be that the weights and target wouldn't be hard-coded in
the constructor. That way you would be able to reuse the class in the
following way to solve two different problem instances (or a general
problem instance constructed during runtime).

  weights1 = [1, 2, 3]
  target1 = 3
  ArraySumProblem.new(weights1, target1).each_solution do |solution|
    p solution.selected_weights.value.map{ |x| x.to_f / 100 }
  end

  weights2 = [2, 3, 4]
  target2 = 7
  ArraySumProblem.new(weights2, target2).each_solution do |solution|
    p solution.selected_weights.value.map{ |x| x.to_f / 100 }
  end

Where <[1,2,3], 3> and <[2,3,4], 7> are two different pairs of weights
and target.

It would probably also be a good idea to create a method in the
ArraySumProblem class that does the whole "selected_weights.value.map{
|x| x.to_f / 100 }"-thing for better maintainability.

[1] http://www.whytheluckystiff.net/ruby/pickaxe/html/...
[2] http://www.whytheluckystiff.net/ruby/pickaxe/html/intro.html
[3] http://www.whytheluckystiff.net/ruby/pickaxe/html/...
This topic is locked and can not be replied to.