Suivre les étapes de la programmation dynamique

Question

J'enseigne moi-même les principes de programmation de base, et je suis bloqué sur un problème de programmation dynamique. Prenons le tristement célèbre Knapsack Problème:

Étant donné un ensemble d'articles, chacun avec un poids et une valeur, déterminer le nombre de chaque article à inclure dans une collection de sorte que le poids total est inférieur ou égal à une limite donnée et la valeur totale est aussi grande que possible. Fixons la limite de poids à 10, et donnons deux listes: poids = [2,4,7] et valeurs = [8,4,9] (je viens juste de les faire monter). Je peux écrire le code pour donner la valeur maximale donnée la contrainte - ce n'est pas un problème. Mais qu'en est-il si je veux savoir quelles valeurs j'ai finalement utilisées? Pas la valeur totale - les valeurs individuelles. Donc, pour cet exemple, le maximum serait les objets avec les poids 2 et 7, pour une valeur totale de 8 + 9 = 17. Je ne veux pas que ma réponse lise "17" cependant - Je veux une sortie d'une liste comme: (8, 9). Cela peut être facile pour ce problème, mais le problème sur lequel je travaille utilise des listes qui sont beaucoup plus grandes et qui ont des numéros de répétition (par exemple, plusieurs objets ont une valeur de 8). Faites-moi savoir si quelqu'un peut penser à quoi que ce soit. Comme toujours, beaucoup d'amour et d'appréciation pour la communauté.

Answer 1

Considérez chaque solution partielle comme un nœud. Il suffit d'ajouter ce que vous utilisez dans chacun de ces nœuds et quel que soit le nœud devient la réponse à la fin contiendra l'ensemble des éléments que vous avez utilisés.

Ainsi, chaque fois que vous trouvez une nouvelle solution, il vous suffit de définir la liste des éléments dans la liste des éléments de la nouvelle solution optimale et de les répéter pour chacun.

Answer 2

Une implémentation de base de la matrice peut vous aider à garder une trace des éléments qui ont permis à un nouvel état DP d'obtenir sa valeur. Par exemple, si votre tableau DP est w[], vous pouvez avoir un autre tableau p[]. Chaque fois qu'un état est généré pour w[i], vous définissez p[i] sur l'élément que vous utilisiez pour obtenir 'w [i]'. Ensuite, pour afficher la liste des éléments utilisés pour w[n], tapez p[n], puis passez à l'index n-weightOf(p[n]) jusqu'à ce que vous atteigniez 0 pour sortir tous les éléments.