1

Given n sets of items. Each item has a value. The items in a set have similar values but vary by a small amount. The goal is to create new sets containing three items selected from the original sets such that the total of the values is within a given range. Only one item a source set can be selected.

For example: If we have the following starting sets:

  • Set A - { 4.0, 3.8, 4.2 }
  • Set B - { 7.0, 6.8, 7.2 }
  • Set C - { 1.0, 0.9, 1.1 }
  • Set D - { 6.5, 6.4, 6.6 }
  • Set E - { 2.5, 2.4, 2.6 }

Goal is to create sets containing three elements such that the total is between 11.9 and 12.1.

  • For example { 3.8, 7.2, 1.0 }

There can be unused elements.

Can someone suggest an algorithm for this problem?

2

This looks like a knapsack-type problem. No shortcuts.

Form a permutation of each of the possible selectsions, enumerate them, and pick any that fall with the range.

The problem definition could be improved by specifying exactly how selections are made eg one of out each set?

  • Looks like a knapsack to me. In this case the problem statement might actually provide an implicit optimization by constraining the inputs, however. – user22815 Aug 19 '14 at 5:16
1

If you must use exactly 3 items, then it's at worst O(n^2 log n) problem. Insert all elements into a sorted structure (O(n log n)). Then iterate through all possible pair sums (O(n^2)). For each pair sum search the tree to see if there is a suitable third element (O(log n)).

If you can use an arbitrary number of elements, but the values are positive and can be reduced to small integers (as above, just multiply all by 10), then you can use dynamic programming to get a solution in time O(n * s) where s is the desired sum.

See http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.