Эффективный алгоритм удаления плохих чисел из множеств

Question

Дано число конечных наборов целых чисел, например:

A = {1,2,3}
B = {2,3,4}
C = {3,4,5}

, а также число, например 6. Вопрос состоит в том, чтобы определить из наборов числа, которые нельзя использовать для суммирования 6, выбрав одно число из каждого набора. Например, 1 в A является действительным, потому что 1 + 2 + 3 = 6 (2 из B и 3 из C). 5 из C недопустимо, потому что вы не можете суммировать до 6, используя 5 (вы всегда получите по крайней мере 1 + 2 + 5 = 8).

Как вы можете сделать это эффективно?

Answer 1

Я предполагаю, что 3 набора - это просто пример, а фактическое количество наборов не фиксировано

Допустим, у нас есть m наборов с n числами всего и максимально возможнымсумма S.(В вашем примере m = 3, n = 9, S = 12).

Затем задайте вопрос, можно ли использовать число t из набора s для получения суммы x, эквивалентно следующему:могут ли другие наборы m - 1 (кроме набора s) составить число x - t?

Эта задача имеет псевдополиномиальное решение сложности O(n*S), очень похожее на решение для задача о сумме подмножеств .

Таким образом, вы можете решить эту проблему для каждой комбинации m - 1 наборов, и это даст вам O(n*S*m) сложность.