0

I need to create a combination of sum of values closest to the target value. The combination needs to be of x numbers, where x is defined by the user. The algorithm will output the combination closest to a target value entered by the user. I also need to display the keys (values) that the algorithm returns.

Here is how I think the algorithm will work:

Target: 575

Values with corresponding keys:

150 [0] | 75 [1] | 123 [2] | 212 [3] | 23 [4] | 89 [5] | 20 [6] 77 [7] | 39 [8] | 16 [9] | 347 [10] | 512 [11] | 175 [12]

User wants Groups of: 5 values

The algorithm now runs combinations of sum of 5 values on the whole set and returns a sum of the values closest to the target value of 575.

Result

150 [0] + 212 [3] + 23 [4] + 77 [7] + 89 [5] = 551

Keys used were 0, 3, 4, 7, and 5.

I could use Arrays#combination(n), but I will not be able to keep track of the keys. I have been able to come up with a Hash which stores "key" => "int values", but I have no idea how to come up with an optimized algorithm to combine values stored in a Hash.

{0=>"150"} {1=>"212"} {2=>"23"} {3=>"77"} {4=>"89"}

P.S. This is not a homework. Its a personal project to put on the resume, talk about at interviews, and to learn to convert my ideas to code.

Improve this question
4
  • Are you sure you want to deal with a combination of sum of values? So you prepare a combination of combinations of numbers, and calculate the sum for each combination? And, combination [of numbers] closest to a target (number) value does not make sense. How can a combination (probably an array) be "closest" in any sense to a number? Commented Sep 20, 2013 at 6:50
  • Its a sum of combinations. Sum of say any X values from the set closest to the target. Commented Sep 20, 2013 at 7:04
  • Can you perdict how many elements there are in every array? If there are only few elements like shown above, a simple brute-force approach might be just the way to go. Commented Sep 20, 2013 at 7:07
  • That depends on the user input. If the user can request a sum of 10 or 100 values that make a value closes to the target. Commented Sep 20, 2013 at 7:27

2 Answers 2

Reset to default
1

Something like this would work:

hash = {0 => 150, 1 => 75, 2 => 123, 3 => 212, 4 => 23, 5 => 89, 6 => 20, 7 => 77, 8 => 39, 9 => 16, 10 => 347, 11 => 512, 12 => 175} # all key combinations of length 5 keys_of_5 = hash.keys.combination(5) #=> #<Enumerator: [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12]:combination(5)> # i.e. [[0, 1, 2, 3, 4], [0, 1, 2, 3, 5], [0, 1, 2, 3, 6], ...] # sum the values for each combination sums_of_5 = keys_of_5.map { |keys| [keys, hash.values_at(*keys).inject(:+)] } #=> [[[0, 1, 2, 3, 4], 583], [[0, 1, 2, 3, 5], 649], [[0, 1, 2, 3, 6], 580], ...] # sort by distance to target sorted = sums_of_5.sort_by { |keys, sum| (sum - 575).abs } #=> [[[4, 5, 7, 8, 10], 575], [[0, 4, 8, 9, 10], 575], [[3, 4, 5, 7, 12], 576], ...] # let's find the nearest ones nearest = sorted.select { |keys, sum| sum == sorted.first[1] } # and print 'em nearest.each do |keys, sum| puts keys.map { |key| "%3d [%d]" % [hash[key], key] }.join(" + ") << " = #{sum}" end

Output

 23 [4] + 89 [5] + 77 [7] + 39 [8] + 347 [10] = 575 150 [0] + 23 [4] + 39 [8] + 16 [9] + 347 [10] = 575
Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

min_by {} is equivalent to sort {}.first (and nicer to read IMO)
The former is more efficient.
@Stefan Watch out. The OP changed the question. But anyway, your sum is different from mine, and that should not depend on the way key/index are given. I wonder what is wrong.
Sorry about that guys. I did not think the indexes would matter to understand the logic, but it apparently does since you all are actually testing with the numbers,
I've updated my answer to reflect the OP's edit and fixed a bug along the way.
|
1

In order to keep track of the indice, you can apply combination on the indice of the array, not the array itself.

array = [150, 75, 212, 23, 89, 20, 77, 39, 16, 347, 512, 175] target = 575 x = 5 closest_indice = array .each_index.to_a .combination(x) .min_by{|is| (array.values_at(*is).inject(:+) - target).abs}

However, the answer is different from what you claim:

closest_indice # => [0, 3, 7, 8, 9] array.values_at(*closest_indice) # => [150, 23, 39, 16, 347] array.values_at(*closest_indice).inject(:+) # => 575

and I don't understand why you have a different answer.

Edit

As noticed my Stefan, there is no index 2. To deal with that:

hash = {0 => 150, 1 => 75, 3 => 212, 4 => 23, 5 => 89, 6 => 20, 7 => 77, 8 => 39, 9 => 16, 10 => 347, 11 => 512, 12 => 175} target = 575 x = 5 closest_keys = hash .keys .combination(x) .min_by{|is| (hash.values_at(*is).inject(:+) - target).abs} closest_keys # => [0, 4, 8, 9, 10] hash.values_at(*closest_indice) # => [150, 23, 39, 16, 347] hash.values_at(*closest_indice).inject(:+) # => 575

Notice This answer applies to the question as was at the beginning (i.e., before the OP changed the question to add an element 123 with index 2).

Improve this answer

4 Comments

212 has an index of 3, there's no index 2.
Thanks. I missed that point. I was actually wondering why my answer was different from yours.
My answer was based on randomly picked numbers for the example.
@Stefan: Thanks for pointing that out. I added a 2. Its 00:30 here and I need some coffee. Or sleep.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.