Questa riduzione della copertura esatta nella somma del sottoinsieme fallisce a causa di un potenziale falso positivo?

Question

Dopo aver rimozione di multi-set e set che hanno elementi che non esistono in $ s $ .

$ s $ = $ [9,6,74,4,1,8] $

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

Trasforma i valori in $ c $ dei valori dell'indice condiviso con $ s $ . (Questo deve essere fatto prima di toccare $ s $ )

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

e fai lo stesso per $ s $

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

quadrato ogni $ x $ intero in entrambi $ s $ e $ c $

$ f (x) $ = $ x ^ 2 $ , $ x ∈ s $ quindi $ c $

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

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

Quindi rimuovere tutti i set con le somme ripetute per prevenire falsi positivi. Questo significa no $ [1], [1] s ... $ che potrebbe essere utilizzato, per riassumere la somma totale di $ s $ , questo significa anche $ [1,4,9] $ o $ [container"> 4,9,1] $ . (lascia uno però!)

.
1. Dopo la trasformazione è completo Utilizzare sottoinsieme di sottoinsieme del subver e definisci somma totale come $ 140 $ (totale-somma di $ s $ )
2. Definisci l'elenco di numeri interi come set sommato di $ c $ = $ [[14], [41] , [85]] $
3. Esegui algoritmo e ottieni la soluzione

domanda

Questa riduzione del coperchio esatto nella somma del sottoinsieme ogni rendimento di un falso positivo?

Answer 1

Se non sei proprio sicuro se la riduzione funzionerà, probabilmente non lo farà. Ogni volta che stai facendo una riduzione, dovresti sempre avere un piano di come dimostrarlo corretto.

In questo caso, stiamo cercando di vedere se $ 1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + n ^ 2 $ può essere scritto come una somma di quadrati in qualche altro modo (che sarebbe un falso positivo).

Abbiamo quella $ 4 ^ 2= 2 ^ 2 + 2 ^ 2 + 2 ^ 2 + 2 ^ 2 $ . Questo è sufficiente per costruire un controesempio.

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

Non c'è una copertura esatta (l'unico modo per ottenere $ 4 $ è quello di prendere $ \ {1,3, 4,5,6,7 \} $ Ma quindi non possiamo prendere nessun altro set poiché tutti si sovrappongono).

Tuttavia, abbiamo questo:

$$ 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) $$ Quindi, possiamo concludere la riduzione non funziona.