Wird diese Verringerung der exakten Abdeckung in die Subset-Summe aufgrund eines potenziellen FALSE-Positivs ausfallen?

Question

Nach dem Entfernen von Multi-Sets und Sets, die Elemente aufweisen, die in $ S $ nicht vorhanden sind.

$ S $ = $ [9,6,7,4,5,1,1,1] $

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

wandeln Sie die Werte in $ C $ von den freigegebenen Indexwerten mit $ s $ . (Dies muss vor dem Berühren von $ S $ )

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

und tun Sie dasselbe für $ s $

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

square jeweils $ x $ integer in beiden $ s $ und $ C $

$ F (x) $ = $ x ^ 2 $ , $ x ∈ S $ dann $ C $

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

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

Entfernen Sie dann alle Sätze mit wiederholenden Summen, um falsche Positive zu verhindern. Dies bedeutet, dass kein $ [1], [1] s ... $ , die verwendet werden könnten, um die Gesamtsumme der $ s $ , dies bedeutet auch $ [1,4,9] $ oder $ [ 4,9,1] $ . (hinterlasse sie aber!)

.
1. Nachdem die Transformation abgeschlossen ist, verwenden Sie den Subset-Sum-Solver und definieren Sie Gesamtsumme als $ 140 $ (Gesamtsumme von $ s $ )
2. Liste der Zahlen definieren als zusammengefasste Set von $ C $ = $ [[14], [41] , [85]] $
3. Laufen Sie Algorithmus und erhalten Sie die Lösung

Frage

wird diese Verringerung der exakten Abdeckung in die Subset-Summe jeder Ertrag ein falsch positiv?

Answer 1

Wenn Sie nicht wirklich sicher sind, ob eine Reduzierung funktioniert, wird dies wahrscheinlich nicht. Wann immer Sie eine Verringerung machen, sollten Sie immer einen Plan haben, wie er sich als richtig beweisen soll.

In diesem Fall möchten wir sehen, ob $ 1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + n ^ 2 $ kann sein als Summe von Quadraten auf andere Weise geschrieben (was ein falsches Positiv sein würde).

Wir haben diesen $ 4 ^ 2= 2 ^ 2 + 2 ^ 2 + 2 ^ 2 + 2 ^ 2 $ . Dies reicht aus, um ein Gegenbeispiel aufzubauen.

lass $ s={1,2,3,4,5,6,7 \} $ und $ C=\ \ \ \ 1,2 \ \ \ {2,3 \}, \ {2,5 \}, \ {2,6 \} \ \ {2,6 \}, \ {1, 3,4,5,6,7 \} \} $ .

Es gibt keine genaue Abdeckung (der einzige Weg, um $ 4 $ zu erhalten, ist, $ \ {1,3, 4,5,6,7 \} $ aber dann können wir kein anderes Set annehmen, da alle überlappt).

wir haben jedoch das:

$$ 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) $$ .

Wir können also abschließen, dass die Reduktion nicht funktioniert.