Algorithm to match items be value into sets base on total

Question

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?

Answer 1

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?

Answer 2

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