Preuve de la dureté NP de minimisation simultanée et maximisation d'un sous-ensemble pondéré

Question

Je travaille sur un problème défini comme le suivant

donné un ensemble de $ N $ éléments appelés $ r \ sous -éréq \ mathbb {n} \ fois \ mathbb { N} $ et numéros $ z, g \ in \ mathbb {n} $ $ , où $ z $ est une mesure de nos ressources et $ g $ est notre récompense minimale nécessaire, existe-t-il un ensemble $ r '\ Subretteq r $ , de sorte que $ \ somme _ {(z, g) \ in r'} z \ Leq z $ et $ \ somme _ {(z, g) \ in r '} g \ geq g $ ?

Je veux montrer sa NP-Complêtement et montré qu'il est déjà dans NP. Je me débats avec le NP-Dureté. Mes problèmes nf-hards connus sont la SAT, la 3SAT, la partition, la somme sous-ensemble et l'emballage des bacs.

Ma lutte semble être surtout avec le fait que nous devons équilibrer deux valeurs différentes maintenant, le coût et la récompense. Ce n'est pas le cas dans aucun des problèmes liés liés auxquels j'ai mentionné et je suis incapable de penser à la façon de modéliser cela en samedi ou 3SAT. Qu'est-ce que j'oublie ici? Comment puis-je montrer la dureté NP et, en tant que telle, la NP-Complétude de ce problème en utilisant uniquement ces problèmes donnés?

Answer 1

Cela me semble comme le Problème de Knapsack où

• $ z $ est le poids de chaque élément,
• $ z $ est la capacité du sac à dos,
• $ g $ la valeur de l'élément et
• $ g $ la valeur à atteindre.

Le problème est np-complet mais solvable, à l'aide de la programmation dynamique, dans temps pseudo-polynomial $ o (n \ CDOT W) $ où $ w=max _ {(z, g) \ in r} (g) $

.

.

Vous pouvez prouver que le problème du knapack est NP-complet en réduisant à partir du Sous-SOMM Problème . En effet, la somme sous-ensembles est un cas particulier de sacs à dos où $ z= g $ ; Le "poids" de chaque problème est le même que sa "valeur".