Analyse de l'algorithme PHP : Comment utiliser un algorithme de programmation dynamique pour résoudre le problème du sac à dos 0-1 ?

Analyse de l'algorithme PHP : Comment utiliser un algorithme de programmation dynamique pour résoudre le problème du sac à dos 0-1 ?

Introduction : 
La programmation dynamique est une idée algorithmique couramment utilisée pour résoudre des problèmes d'optimisation. Dans le développement de programmes, le problème du sac à dos 0-1 est un scénario classique d’application de programmation dynamique. Cet article explique comment utiliser PHP pour écrire un algorithme de programmation dynamique afin de résoudre le problème du sac à dos 0-1 et fournit des exemples de code spécifiques.

Quel est le problème du sac à dos 0-1 ?
Le problème du sac à dos 0-1 est un problème d'optimisation combinatoire classique. Le problème se pose comme suit : Il existe un sac à dos d’une capacité de C. Il y a n éléments, chaque élément a un poids w[i] et une valeur v[i]. Il est nécessaire de choisir une combinaison d’articles pour maximiser la valeur totale sans dépasser la capacité du sac à dos.

Solution de programmation dynamique
L'algorithme de programmation dynamique consiste à diviser le problème donné en une série de sous-problèmes et à stocker les solutions optimales des sous-problèmes, et enfin à résoudre la solution optimale de l'ensemble du problème. Pour le problème du sac à dos 0-1, nous pouvons utiliser un algorithme de programmation dynamique pour le résoudre.

Idée d'algorithme :

1. Créez un tableau bidimensionnel dp, dpi représente la valeur maximale lorsque seuls les i premiers éléments sont pris en compte et que la capacité du sac à dos est j.
2. Initialisez le tableau dp en définissant tous les éléments sur 0.

3. Articles de traversée :

   • Pour chaque article, si son poids est inférieur ou égal à la capacité du sac à dos j, vous devez comparer la valeur lorsque l'article est mis et lorsque l'article n'est pas mis, et choisir la solution la plus large pour mettre à jour le tableau dp.
   • Si le poids de l'article est supérieur à la capacité du sac à dos j, vous pouvez seulement choisir de ne pas mettre l'article dedans, c'est-à-dire dpi = dpi-1.
4. Une fois le cycle terminé, dpn est la valeur maximale lorsque la capacité du sac à dos est C.

Exemple de code spécifique :

function knapsack($C, $weight, $value, $n) {
    $dp = array();
    for ($i = 0; $i <= $n; $i++) {
        for ($j = 0; $j <= $C; $j++) {
            $dp[$i][$j] = 0;
        }
    }
  
    for ($i = 1; $i <= $n; $i++) {
        for ($j = 1; $j <= $C; $j++) {
            if ($weight[$i-1] <= $j) {
                $dp[$i][$j] = max($value[$i-1] + $dp[$i-1][$j-$weight[$i-1]], $dp[$i-1][$j]);
            } else {
                $dp[$i][$j] = $dp[$i-1][$j];
            }
        }
    }
  
    return $dp[$n][$C];
}

// 示例输入
$C = 10; // 背包容量
$weight = array(2, 3, 4, 5); // 物品重量
$value = array(3, 4, 5, 6); // 物品价值
$n = count($weight); // 物品数量

// 输出最大价值
echo "背包容量为 " . $C . " 时的最大价值为：" . knapsack($C, $weight, $value, $n);

Analyse du code :

• fonctionknapsackaccepte quatre paramètres : capacité du sac à dos C, poids du tableau de poids de l'article, valeur du tableau de valeurs de l'article et quantité d'article n.
• Créez un tableau bidimensionnel $dp pour stocker la solution optimale au sous-problème.
• Initialisez le tableau dp en définissant tous les éléments sur 0.
• Parcourez les éléments et effectuez des jugements et des mises à jour basés sur l'équation de transition d'état de la programmation dynamique.
• Une fois la boucle terminée, le dpn renvoyé est la valeur maximale lorsque la capacité du sac à dos est C.

Conclusion : 
En utilisant un algorithme de programmation dynamique pour résoudre le problème du sac à dos 0-1, la valeur maximale que le sac à dos peut contenir peut être résolue efficacement. En PHP, cet algorithme peut être implémenté en écrivant du code approprié. Cette idée algorithmique n’est pas seulement applicable au problème du sac à dos 0-1, mais peut également être appliquée à d’autres problèmes d’optimisation combinatoire similaires.

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!