Asp Forum - Combination of numbers in an array that add up to x

Hae Lee

11/4/2008 3:49:00 PM

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

16 Answers

Brian Candler

11/4/2008 3:58:00 PM

Axel Etzold

11/4/2008 4:21:00 PM

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

Dear Hae,

There is Gecoder for combinatorial optimization problems in Ruby :

http://gecoder.ruby...

The numbers must be integers.

Best regards,

Axel

--
"Feel free" - 5 GB Mailbox, 50 FreeSMS/Monat ...
Jetzt GMX ProMail testen: http://www.gmx.net/de/...

ara.t.howard

11/4/2008 4:26:00 PM

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

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

a @ http://codeforp...
--
we can deny everything, except that we have the possibility of being
better. simply reflect on that.
h.h. the 14th dalai lama

Giampiero Zanchi

11/5/2008 1:29:00 PM

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

Hae Lee

11/5/2008 2:47:00 PM

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

Hae Lee

11/5/2008 2:51:00 PM

Axel Etzold wrote:
> Dear Hae,
>
>
> There is Gecoder for combinatorial optimization problems in Ruby :
>
> http://gecoder.ruby...
>
> 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-....

Hae Lee

11/5/2008 2:53:00 PM

Ara Howard wrote:
> start by installing the permutations gem (for a brute force solution).
>
>
> a @ http://codeforp...

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

Hae Lee

11/5/2008 2:57:00 PM

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

Giampiero Zanchi

11/5/2008 3:28:00 PM

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

Brian Candler

11/5/2008 4:05:00 PM

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

comp.lang.ruby

Combination of numbers in an array that add up to x

Hae Lee

Brian Candler

Axel Etzold

ara.t.howard

Giampiero Zanchi

Hae Lee

Hae Lee

Hae Lee

Hae Lee

Giampiero Zanchi

Brian Candler

x Login to ForumsZone