Le problème du sac à dos 0-1 où la valeur est égale au poids est-il NP-complet?

9

J'ai un problème que je soupçonne être NP-complet. Il est facile de prouver qu'il s'agit de NP. Mon courant de pensée tourne autour de l'utilisation d'une réduction par rapport au sac à dos, mais il en résulterait des instances de 0-1-sac à dos avec la valeur de chaque élément étant égale à son poids.

Est-ce toujours NP-complet? Ou est-ce que je manque quelque chose?

complexity-theory np-complete decision-problem packing Zeta Two
la source
C'est des années trop tard, mais de toute façon: votre formulation suggère que vous essayez peut-être de réduire dans la mauvaise direction. Vous devez passer du sac à dos à votre problème, ce qui signifie que vous devez autoriser les instances de sac à dos arbitraires (ce qui peut produire des instances de votre problème qui ont une structure spéciale) - aucune partie de cette procédure ne "résultera" en des instances de sac à dos avec quelques spéciales structure. (OTOH, il est logique de se demander si un cas spécial de Knapsack est toujours NP-complet, car il pourrait être plus facile de le réduire.)
j_random_hacker
Oui. Ce que je voulais dire, c'est que je réduis à partir du sac à dos, mais plus précisément du "0-1-sac à dos, la valeur de chaque article étant égale à son poids". Donc, c'était seulement ma formulation qui était un peu décalée.
Zeta Two

Réponses:

9

Oui, cela s'appelle le problème de la somme des sous-ensembles et est NP-difficile.

Aryabhata
la source
Merci! Je viens de réaliser que j'ai fait cette découverte plus tôt. Malheureusement, j'ai également réalisé que ma réduction ne fonctionnait pas du tout. Retour à la planche à dessin. :(
Zeta Two
@ZetaTwo: Vous êtes les bienvenus :-)
Aryabhata