¿Esta reducción de la cobertura exacta a la suma del subconjunto fallará debido a un posible falso positivo?

Question

Después de eliminar conjuntos múltiples y conjuntos que tienen elementos que no existen en $S$.

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

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

Transformar los valores en $C$ de los valores del índice compartido con $S$.(Esto debe hacerse antes de tocar $S$)

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

Y haz lo mismo para $S$

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

Cuadrar cada uno $x$ entero en ambos $S$ y $C$

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

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

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

Luego elimine todos los conjuntos con sumas repetidas para evitar falsos positivos.Esto significa que no $[1],[1]s...$ que podrían utilizarse, para sumar la suma total de $S$, Esto también significa $[1,4,9]$ o $[4,9,1]$.(¡pero deja uno!)

1. Una vez completada la transformación, utilice el solucionador de suma de subconjuntos y defina la suma total como $140$ (suma total de $s$)
2. Definir lista de números enteros como un conjunto resumido de $C$ = $[[14],[41],[85]]$
3. Ejecute el algoritmo y obtenga la solución.

Pregunta

¿Esta reducción de la cobertura exacta a la suma del subconjunto producirá un falso positivo?

Answer 1

Si no está realmente seguro de si una reducción funcionará, probablemente no lo hará. Siempre que esté haciendo una reducción, siempre debe tener un plan de cómo demostrarlo.

En este caso, estamos buscando ver si $ 1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + n ^ 2 $ puede ser escrito como una suma de cuadrados de alguna otra manera (lo que sería un falso positivo).

Tenemos que $ 4 ^ 2= 2 ^ 2 + 2 ^ 2 + 2 ^ 2 + 2 ^ 2 $ . Esto es suficiente para construir un contraejemplo.

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

No hay una cubierta exacta (la única forma de obtener $ 4 $ es tomar $ \ {1,3, 4,5,6,7 \} $ pero luego no podemos tomar ningún otro conjunto ya que todos ellos se superponen).

Sin embargo, tenemos eso:

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

Por lo tanto, podemos concluir la reducción no funciona.