Comment réaliser l'algorithme de rencontre applicable pour 0-1 Knapsack?

Question

J'étudie maintenant un problème de KNAPACACK (KP) et trouvez l'algorithme de rencontre dans le milieu décrit dans Wikipedia Un peu incertaine qui, comment le réaliser dans la complexité théorique du temps de $ o ^ * (2 ^ {n / 2}) $ ? Je peux comprendre l'algorithme du problème des sous-ensembles (SSP) qui est une instance particulière de 0-1 KP, mais pour le problème généralisé, il pourrait y avoir quelque chose de mal à l'étape suivante:

  for each subset of A do
      find the subset of B of greatest value such that the combined weight is less than W

Si je comprends bien, c'est à rechercher (par exemple, une recherche binaire) sur des poids combinés de tous les sous-ensembles de B, qui prend le temps de logarithme pour chaque recherche. Mais après avoir connu quels sous-ensembles ont un poids combiné inférieur à W, comment trouver celui de la plus grande valeur? Si la recherche sur les valeurs des sous-ensembles avec Poids $ o ^ * (2 ^ {n / 2}) $ , mais quelque chose comme $ o ^ * (2 ^ n) $ .

même si cela commence à trouver le sous-ensemble de la plus grande valeur (facile pour une table) d'abord sans constriction sur le poids combiné, la vérification du poids deviendra probablement false et donc plus de tests sont nécessaires pour les autres sous-ensembles, dont le nombre semble être associé à la taille de la table à nouveau linéairement.

Maintenant, je ne peux que supposer que la valeur totale et le poids combiné est fortement positif corrélé, de sorte qu'après avoir trouvé le sous-ensemble avec un poids maximum autorisé, il ne prend que du temps constant pour rechercher ce sous-ensemble pour l'exacorme la plus grande valeur. Mais je ne suis pas satisfait de cette explication. Donc, tout le monde a de meilleures idées sur ce problème?

PS: J'ai lu le papier original de Horowitz, Ellis et Sahni, Sartaj, mais j'ai trouvé le problème défini qu'il existe un problème de décision plutôt que le problème d'optimisation commun. Peut-être que quelqu'un peut fournir des idées dans cette direction.

Answer 1

Premièrement, précalcompute les poids de chaque sous-ensemble de $ B $ .

Triez-les en poids et placez les poids et les sous-ensembles dans des matrices parallèles afin que $ w [i]= poids $ et $ S [i]= sous-ensemble $ .

Faites ensuite une autre matrice parallèle de sorte que meilleur [i] $ est l'index $ j $ de l'ensemble de la plus grande valeur telle que $ j <= i $ .Vous pouvez le faire avec une seule analyse de $ i= 0 $ vers le haut, en vous rappelant la plus grande valeur vue jusqu'à présent à chaque étape.

maintenant, pour rechercher $ B $ , vous faites une recherche binaire dans $ w $ pour trouverLe poids maximal admissible et obtenez le meilleur jeu de la même index dans meilleur $