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?

on 2008-11-04 16:50

on 2008-11-04 16:59

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.

on 2008-11-04 17:23

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

on 2008-11-04 17:28

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

on 2008-11-05 14:31

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

on 2008-11-05 15:48

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!

on 2008-11-05 15:52

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!

on 2008-11-05 15: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!!!

on 2008-11-05 15:59

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

on 2008-11-05 16: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.

on 2008-11-05 17: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"

on 2008-11-06 10:34

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

on 2008-11-06 15:53

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!

on 2008-11-06 15:56

2008/11/5 Hae Lee <hae.lee.subscription@gmail.com>: > > 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 Heesob

on 2008-11-06 16:53

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

on 2008-11-07 04:54

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

on 2008-11-07 10:10

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