Comment résoudre le problème du sac à dos en PHP en utilisant un algorithme de programmation dynamique et obtenir une solution optimale ?

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 :

• Le tableau de poids des éléments $weights, $weights[$i] représente le poids du $i-ième article
• Le tableau de valeurs des éléments $values ​​, $values[$i] représente la valeur du $i-ème article
• La capacité du sac à dos $capacity, représente la capacité maximale du sac à dos

Sortie :

• Le valeur totale maximale des éléments dans le sac à dos

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 :

1. Initialisez le tableau $dp et définissez tous les éléments à 0.

2. 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é :

     • Si le poids de l'article actuel $weights[$i] est supérieur à la capacité du sac à dos $j, alors $dp[$i][$j] = $dp[$i - 1][$j], c'est-à-dire que les objets actuels ne peuvent pas être placés dans le sac à dos et que la valeur totale maximale est la même que celle des premiers objets $i - 1.
     • Sinon, l'article actuel peut être mis dans le sac à dos, et la valeur qu'il génère $values[$i] plus la valeur totale maximale avant de mettre l'article $dp[$i - 1][$j - $weights[$ i ]], par rapport à la valeur actuelle, prenez la valeur la plus grande comme $dp[$i][$j].
3. Renvoie $dp[count($weights) - 1][$capacity], qui est la valeur totale maximale du premier compte($weights) articles lorsque la capacité du sac à dos est de $capacity.

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!