Le fameux problème complet NP. Le problème de mettre l'article dans le sac à dos pour que la valeur de l'article soit maximisée.
Si vous pensez simplement, ce sera $ O (2 ^ N) $ car vous devrez choisir de ne pas mettre l'article. Pensez à résoudre ce problème en temps polymorphe.
Je vais vous expliquer comment les résoudre en temps polymorphe en trois étapes.
En tant qu'image de la méthode de planification dynamique, envisagez d'augmenter à partir d'un petit état. En d'autres termes, pensez à une époque. À un moment donné, il est décidé de le mettre ou non en fonction de la capacité du sac à dos. Bien sûr, il est plus utile de le mettre, alors mettez-le. À la deuxième fois, décidez de le mettre dans le sac à dos. Ce à quoi vous devez faire attention ici, c'est la branche avec la première. La décision de le mettre dans le sac à dos est partagée. Et à la troisième fois, comparez-le avec le sac à dos à la fin du deuxième. En d'autres termes, c'est le miso de ce problème de réfléchir à l'opportunité d'ajouter un nouvel élément à l'état existant.
En production
Recommended Posts