Trovare la dimensione massima possibile di S, dove s è un insieme di sottoinsiemi di Disjoint a coppie dell'elenco e ogni elemento di S somme a K

Question

Supponiamo che avessi un elenco di numeri nell'intervallo 1-20 per esempio: [5, 16, 17, 3, 2, 14, 4, 9, 11, 19] e un numero intero K (diciamo k = 40)

Come troverei la dimensione massima possibile di s, dove s è un insieme di sottoinsiemi a coppie-wisjoint dell'elenco e ogni elemento di somme a k?

Credo che questo algoritmo sia completo NP.

Basta pensare al problema come un algoritmo di imballaggio del cestino, ma invece di dire che il valore totale degli elementi nel cestino non deve superare la capcacità del cestino, sto dicendo che il valore totale degli elementi nel cestino deve essere esattamente uguale alla capacità del cestino . Inoltre, stiamo cercando di massimizzare il numero di bidoni.

Scenario di esempio:

Supponiamo che io abbia un elenco: [1, 2, 2, 3, 5, 6, 5] e k = 7, quindi alcuni valori di esempio di S sarebbero:

(3+2+2), (6+1)] - 5 e 5 rimasti

(5+2), (5+2), (6+1)] - 3 rimasti

Come puoi vedere, la seconda soluzione è ottimale perché produce 3 partizioni anziché 2.