Combination of numbers in an array that add up to x

ruby-talk
1

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?
--
Posted via http://www.ruby-forum.com/.

2

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

···

--
Posted via http://www.ruby-forum.com/\.

3

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

a @ http://codeforpeople.com/

···

On Nov 4, 2008, at 8:48 AM, Hae Lee 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?
--

--
we can deny everything, except that we have the possibility of being better. simply reflect on that.
h.h. the 14th dalai lama

4

Hae Lee 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

···

--
Posted via http://www.ruby-forum.com/\.

5

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 Heesob

···

2008/11/5 Hae Lee <hae.lee.subscription@gmail.com>:

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?

6

-------- Original-Nachricht --------

Datum: Wed, 5 Nov 2008 00:58:07 +0900
Von: Brian Candler <b.candler@pobox.com>
An: ruby-talk@ruby-lang.org
Betreff: Re: Combination of numbers in an array that add up to x

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

···

--
"Feel free" - 5 GB Mailbox, 50 FreeSMS/Monat ...
Jetzt GMX ProMail testen: GMX ProMail - Mehr als E-Mail mit dem Profi-Postfach

7

Brian Candler 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!

···

--
Posted via http://www.ruby-forum.com/\.

8

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

···

--
Posted via http://www.ruby-forum.com/\.

9

Giampiero Zanchi 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!!!

···

--
Posted via http://www.ruby-forum.com/\.

10

Axel Etzold 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!

···

--
Posted via http://www.ruby-forum.com/\.

11

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.

···

--
Posted via http://www.ruby-forum.com/\.

12

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"

···

--
Posted via http://www.ruby-forum.com/.

13

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

14

Andreas Launila 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!

···

--
Posted via http://www.ruby-forum.com/\.

15

Hae Lee wrote:

Andreas Launila 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/searching_for_solutions.html
. 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.

···

--
Andreas Launila

16

Andreas Launila 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!!!

···

--
Posted via http://www.ruby-forum.com/\.

17

Hae Lee wrote:

Andreas Launila 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/tut_methods.html
[2] http://www.whytheluckystiff.net/ruby/pickaxe/html/intro.html
[3] http://www.whytheluckystiff.net/ruby/pickaxe/html/tut_classes.html

···

--
Andreas Launila