Algorithm to match items be value into sets base on total

Posted by Ben on Programmers See other posts from Programmers or by Ben
Published on 2014-08-18T17:05:17Z Indexed on 2014/08/18 22:31 UTC
Read the original article Hit count: 296

Filed under:

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?

© Programmers or respective owner

Related posts about algorithms