È il problema dello zaino 0-1 dove il valore è uguale a peso NP-completo?
-
16-10-2019 - |
Domanda
Ho un problema che ho il sospetto è NP-completo. E 'facile dimostrare che è NP. Il mio attuale treno della ruota di pensiero intorno usando una riduzione da bisaccia, ma sarebbe risultato in casi di 0-1-zaino con il valore di ogni elemento è uguale al suo peso.
È ancora NP-completo? O mi sto perdendo qualcosa?
Soluzione
Sì, questo è chiamato il problema sottoinsieme somma ed è NP difficile.
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange