Будет ли это сокращение точного обложки в подведу-сумму сбой из-за потенциального ложного положительного?

Question

После удаления многоуровневых и наборов, которые имеют элементы, которые не существуют в $ S $ .

$ s $ = $ [9,6,7,4,5,1,8] $

$ C $ C $ = $ [[9,6,7], [4,5], [1, 8]] $

Преобразовать значения в $ C $ значения общего индекса с $ s $ . (Это должно быть сделано до прикосновения $ s $ )

$ C $ = $ [[1,2,3], [4,5], [6, 7]] $

и сделайте то же самое для $ s $

$ S $ = $ [1,2,3,4,5,6,7] $

квадрат каждый $ x $ Integer в обоих $ S $ и $ c $

$ f (x) $ = $ x ^ 2 $ , $ x ∈ S $ затем $ C $

$ s $ = $ [1, 4, 9, 16, 25, 36, 49] $

$ C $ = $ [[1,4,9], [16,25], [36, 49]] $

Затем удалите все наборы с повторяющимися суммами для предотвращения ложных срабатываний. Это означает, что нет $ [1], [1] s ... $ , который можно использовать, чтобы суммироваться до общей суммы $ s $ , это также означает $ [1,4,9] $ или $ [ 4,9,1] $ . (Оставьте один хоть!)

1. После завершения преобразования используйте Sumbest-Sum Sumver и определите общую сумму в качестве $ 140 $ (Total-Sum of $ s $ )
2. определяют список целых чисел как суммированные набор $ C $ = $ [[[14], [41] , [85]] $
3. пробежать алгоритм и получите решение

Вопрос

Это уменьшение точного прикрытия в подмножественную сумму каждую доходность ложного положительного?

Answer 1

Если вы не уверены, что будет работать уменьшение, это, вероятно, не будет. Всякий раз, когда вы делаете снижение, вы всегда должны иметь план того, как доказать это правильно.

В этом случае мы стремимся увидеть, $ 1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + n ^ 2 $ может быть написано как сумма квадратов каким-то другим способом (которая будет ложным положительным).

У нас есть что $ 4 ^ 2= 2 ^ 2 + 2 ^ 2 + 2 ^ 2 + 2 ^ 2 $ . Этого достаточно, чтобы построить контрпример.

Пусть $ s={1,2,3,4,5,6,7 \} $ и $ C={\ {1,2 \}, \ {2,3 \}, \ {2,5 \}, \ {2,6 \} \, \ {2,7 \}, \ {1, 3,4,5,6,7 \} \} $ .

Нет точного обложки (единственный способ получить $ 4 $ - это взять $ \ {1,3, 4,5,6,7 \} $ Но тогда мы не можем взять другой набор, поскольку все они перекрываются).

Однако у нас есть это:

$$ 1 ^ 2 + 2 ^ 2 + 3 ^ 2 + 4 ^ 2 + 5 ^ 2 + 6 ^ 2 + 7 ^ 2= (1 ^ 2 + 2 ^ 2 ) + (2 ^ 2 + 3 ^ 2) + (2 ^ 2 + 5 ^ 2) + (2 ^ 2 + 6 ^ 2) + (2 ^ 2 + 7 ^ 2) $$

Таким образом, мы можем заключить сокращение не работает.