Comment pouvons-nous identifier les éléments spécifiques inclus dans un sac à dos à l'aide de l'algorithme du sac à dos ?

Détermination des éléments dans le sac à dos à l'aide de l'algorithme du sac à dos

L'algorithme du sac à dos, une technique d'optimisation, est couramment utilisé pour déterminer la valeur optimale des objets qui peut être logé dans un sac à dos de capacité limitée. Cependant, pour obtenir une solution complète, il est souvent souhaitable d'identifier non seulement la valeur optimale mais également les éléments spécifiques inclus dans le sac à dos.

Pour améliorer le code fourni, un tableau supplémentaire peut être utilisé pour enregistrer le éléments choisis. L'étape appropriée pour effectuer cette sélection se situe pendant le processus itératif de l'algorithme.

Après chaque itération, vérifiez si la différence entre le poids actuel dans le sac à dos (dpw) et le poids précédent sans l'article actuel (dp [w - items[j-1].getWeight()][j-1]) est égal au poids de l'élément actuel. Si cette condition est remplie, l'élément a été sélectionné et doit être ajouté au tableau.

Alternativement, une approche simple consiste à revenir en arrière dans la matrice après avoir déterminé la valeur optimale. Si la différence entre le poids actuel dans le sac à dos (dpline) et le poids précédent sans l'élément actuel (dpline - poids(i)) est exactement égale à la valeur de l'élément actuel (value(i)), cela indique que le L'article est dans le sac à dos et doit être marqué comme tel. Ce processus se poursuit jusqu'à ce que tous les éléments soient vérifiés.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!