What is the largest sum that can be constructed with the given recipes?


There are $ n$ sets of distinct positive integers, $ S_1,\ldots,S_n$ . There is a set of recipes that allows us to construct tuples of integers from these sets. For example, the recipe {1,2} allows us to construct tuples of two integers: one from $ S_1$ and one from $ S_2$ . Each integer can be used in at most one tuple. What is an algorithm that, given the sets and the recipes, constructs tuples such that the sum of integers in all tuples together is maximum? Here are some simple cases:

(a) There is a single recipe, e.g. {1,2}. Then the algorithm is simple: sort the integers in $ S_1$ and in $ S_2$ in descending order; pair the largest integers in each set; pair the second-largest integers in each set; keep pairing integers as long as the sum of the next pair is positive.

(b) There are two recipes {1,2} and {1,3}. Then, $ S_2$ and $ S_3$ are substitutes: combine them into a single set $ S_4 = S_2\cup S_3$ , and proceed as in (a) with the recipe {1, 4}.

(c) There are two recipes {1,2} and {1,3,4}. Then, $ S_3$ and $ S_4$ are complements: sort each one in descending order, and construct a new set $ S_5$ in which the largest element is the sum of the largest elements in $ S_3,S_4$ , the second-largest is the sum of the two second-largest elements, and so on. Proceed as in (b) with the recipes {1,2} and {1,5}.

(d) The above two operations can be generalized to the case in which the set of recipes has a tree structure: there is a tree in which each node is a set, and each recipe is a path from root to leaf in the tree. The tree can be "contracted" as follows: a leaf which is the unique child of its parent can be combined with its parent as in (c); two leafs of the same parent can be combined as in (b).

Is there an efficient algorithm that works for any set of recipes?