Для данного семейства наборов вычисляется сумма этих наборов, а затем указывается минимальное (по размеру) подсемейство этих наборов, которое все равно складывается в сумму ВСЕХ наборов. Ака удаляет все избыточные наборы так, чтобы оставалось как можно меньше наборов. Наборы хранятся в отсортированных массивах. Семейство представляет собой двумерный массив с различной длиной ряда.
Пример
F = {a,b,c,d,e,f}
a = {1,2,3};
b = {3,4};
c = {2,4,5};
d = {2,7,9};
e = {2,5,8};
f = {1,4,5,7};
sum (F) = {1,2,3,4,5,7,8,9} <- обратите внимание, что не все числа должны быть в сумме здесь 6 не встречается </p>
примерные решения решения:
проп. 1: {a, b, e, d} -> суммы до {1,2,3,4,5,7,8,9}, и ничего нельзя выбросить.
prop. 2: {a, b, f} -> aswell суммирует до {1,2,3,4,5,7,8,9}, и ничего нельзя выбросить.
НО: мы возвращаем предложение 2 как решение, потому что подсемейство содержит меньше наборов
Обеспечение алгоритма с наименьшей возможной временной сложностью