Comment utiliser un algorithme de programmation dynamique pour résoudre le problème du sac à dos en PHP et obtenir la solution optimale ?
Le problème du sac à dos est l'un des problèmes d'optimisation combinatoire classiques en informatique. Étant donné un ensemble d'articles et la capacité d'un sac à dos, la manière de sélectionner les articles à mettre dans le sac à dos afin de maximiser la valeur totale des articles dans le sac à dos est au cœur du problème du sac à dos qui doit être résolu.
La programmation dynamique est l'une des méthodes courantes pour résoudre le problème du sac à dos. Il obtient finalement la solution optimale en divisant le problème en sous-problèmes et en enregistrant les solutions des sous-problèmes. Ci-dessous, nous expliquerons en détail comment utiliser un algorithme de programmation dynamique pour résoudre le problème du sac à dos en PHP.
Tout d'abord, nous devons définir l'entrée et la sortie du problème du sac à dos :
Entrée :
Sortie :
Ensuite, nous devons définir un tableau bidimensionnel $dp pour enregistrer la solution au sous-problème. $dp[$i][$j] représente la valeur totale maximale des premiers $i éléments lorsque la capacité du sac à dos est de $j.
Le déroulement de l'algorithme est le suivant :
La boucle extérieure parcourt l'index de l'article, de $i = 1 à $i = count($weights) - 1 :
La boucle intérieure parcourt la capacité du sac à dos, de $j = 0 à $j = $ capacité :
Ce qui suit est un algorithme de programmation dynamique qui utilise du code PHP pour implémenter le problème du sac à dos :
function knapsack($weights, $values, $capacity) { $dp = []; for ($i = 0; $i < count($weights); $i++) { $dp[$i] = []; for ($j = 0; $j <= $capacity; $j++) { $dp[$i][$j] = 0; } } for ($i = 1; $i < count($weights); $i++) { for ($j = 0; $j <= $capacity; $j++) { if ($weights[$i] > $j) { $dp[$i][$j] = $dp[$i - 1][$j]; } else { $dp[$i][$j] = max($dp[$i - 1][$j], $values[$i] + $dp[$i - 1][$j - $weights[$i]]); } } } return $dp[count($weights) - 1][$capacity]; }
En utilisant le code ci-dessus, nous pouvons résoudre le problème du sac à dos en appelant la fonction knapsack($weights, $values, $capacity)
et obtenir la solution optimale.
J'espère que cet article pourra vous aider à comprendre comment utiliser un algorithme de programmation dynamique pour résoudre le problème du sac à dos en PHP et obtenir la solution optimale.
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!