Prova per la durezza NP di minimizzazione simultanea e massimizzazione di un sottoinsieme ponderato

Question

Sto lavorando su un problema definito come il seguente

Dato un set di $ N $ Elementi chiamati $ r \ subeteq \ mathbb {n} \ time \ mathbbs { N} $ e numeri $ z, g \ in \ mathbb {n} $ , dove $ Z $ è una misura delle nostre risorse e $ G $ è la nostra ricompensa minima necessaria, c'è un set $ r '\ SOCSETETQ $ , in modo che $ \ Sum _ {(z, g) \ in r'} z \ leq z $ e $ \ Sum _ {(z, g) \ in r '} g \ geq g $ ?

Voglio mostrare la sua completezza NP e hanno dimostrato che è già in NP. Sto lottando con la durezza NP. I miei noti problemi np-hard sono il sat, 3sat, partizione, somma sottoinsieme e imballaggio bin.

La mia lotta sembra essere principalmente con il fatto che dobbiamo bilanciare due valori diversi ora, il costo e la ricompensa. Questo non è il caso in nessuno dei problemi relativi impostati che ho menzionato e non riesco a pensare a come modellarlo in SAT o 3SAT. Cosa mi manca qui? Come posso mostrare la durezza NP e come tale la completezza NP di questo problema utilizzando solo questi problemi indicati?

Answer 1

Questo mi suona come il problema di zaino dove

.
• $ z $ è il peso di ciascun elemento,
• $ z $ è la capacità dell 'zaino,
• $ G $ il valore dell'articolo e
• $ G $ il valore da ottenere.

Il problema è np-completo ma risolvibile, utilizzando la programmazione dinamica, in tempo pseudo-polinomiale $ o (n \ O clot w) $ dove $ w=max _ {(z, g) \ in r} (g) $ .

È possibile dimostrare che il problema dello zaino è NP-Completo riducendo dal subset somma problema . Infatti, sottoinsieme è un caso speciale di zaino dove $ z= G $ ; Il "peso" di ogni problema è lo stesso del suo "valore".