Prova para a dureza NP de minimização simultânea e maximização de um subconjunto ponderado

Question

Eu estou trabalhando em um problema definido como o seguinte

Dado um conjunto de elementos $ n $ chamado $ r \ subseteq \ mathbb {n} \ vezes \ mathbb { N} $ e números $ Z, g \ in \ mathbb {n} $ , onde $ Z $ é uma medida de nossos recursos e $ g $ é a nossa recompensa mínima necessária, há um conjunto $ r '\ subseteq R $ , de modo que $ \ sum _ {(z, g) \ em r'} z \ leq z $ e $ \ sum _ {(z, g) \ em r '} g \ geq g $ ?

Eu quero mostrar sua completude NP e mostrar que ele já está no NP. Eu estou lutando com a dureza NP. Meus problemas NP-Hard NP são os SAT, 3,00, partição, soma de subconjunto e embalagem de bin.

Minha luta parece ser principalmente com o fato de termos de equilibrar dois valores diferentes agora, o custo e a recompensa. Este não é o caso em qualquer um dos problemas relacionados que mencionei e não consigo pensar em como modelar isso em SAT ou 3SAT. O que estou perdendo aqui? Como posso mostrar a dureza NP e, como tal, a completude np desse problema usando apenas esses problemas dados?

Answer 1

Isso parece-me como o problema da mochila onde

• $ z $ é o peso de cada item,
• $ z $ é a capacidade da mochila,
• $ g $ o valor do item e
• $ g $ o valor a ser alcançado.

O problema é np-completo mas solucionável, usando programação dinâmica, em pseudo-polynomial tempo $ O (n \ cdot w) $ onde $ w=max _ {(z, g) \ em r} (g) $ .

Você pode provar que o problema da mochila é NP - completo reduzindo a partir do Problema de soma do subconjunto . De fato, a soma do subconjunto é um caso especial de mochila onde $ z= g $ ; O "peso" de cada problema é o mesmo que seu "valor".