Cette réduction de la couverture exacte en une somme sous-sol est-elle en raison d'un potentiel de faux positif?

Question

Après avoir retiré des multi-ensembles et des ensembles qui ont des éléments qui n'existent pas dans $ s $ .

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

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

Transformez les valeurs dans $ C $ des valeurs d'index partagées avec $ s $ . (Ceci doit être fait avant de toucher $ S $ )

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

et faites la même chose pour $ s $

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

carré chaque $ x $ entier dans $ s $ et $ C $ C $

$ f (x) $ = $ x ^ 2 $ , $ x ∈ S $ alors $ C $

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

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

Ensuite, supprimez tous les ensembles avec des sommes répétées pour éviter les faux positifs. Cela signifie no $ [1], [1] S ... $ qui pourrait être utilisé, pour résumer jusqu'à la somme totale de $ s $ , cela signifie aussi $ [1,4,9] $ ou $ [ 4,9,1] $ . (laissez-en un cependant!)

1. Une fois que la transformation est complète, utilisez Sous-Sum SUMVolver et définissez la somme totale en tant que 140 $ (somme totale de $ S $ )
2. Définir la liste des entiers en tant qu'ensemble résumé de $ C $ C $ = $ [[14], [41] , [85]] $
3. exécuter l'algorithme et obtenez la solution

Question

Cette réduction de la couverture exacte en une somme sous-ensembles est-elle un faux positif?

Answer 1

Si vous n'êtes pas vraiment sûr de savoir si une réduction fonctionnera, ce n'est probablement pas. Chaque fois que vous effectuez une réduction, vous devez toujours avoir un plan de la manière de la prouver correctement.

Dans ce cas, nous cherchons à voir si 1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + n ^ 2 $ peut être écrit comme une somme de carrés d'une autre manière (ce qui serait faux positif).

Nous avons que 4 $ ^ 2= 2 ^ 2 + 2 ^ 2 + 2 ^ 2 + 2 ^ 2 $ . Cela suffit à construire un contre-exemple.

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

Il n'y a pas de couverture exacte (le seul moyen d'obtenir 4 $ est de prendre $ \ {1,3, 4,5,6,7 \} $ Mais nous ne pouvons donc prendre aucun autre ensemble puisque tous chevauchent).

Cependant, nous avons cela:

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

Ainsi, nous pouvons conclure que la réduction ne fonctionne pas.