Combination of numbers in an array that add up to x

Ruby
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?

2

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.

3

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/

4

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

Datum: Wed, 5 Nov 2008 00:58:07 +0900
Von: Brian C. [email protected]
An: [email protected]
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

5

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

6

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!

7

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

8

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!

9

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

10

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”

11

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.

12

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!

13

2008/11/5 Hae L. [email protected]:

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.

14

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.

15

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/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.

16

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

17

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