Comment implémenter l'algorithme du problème du sac à dos en utilisant PHP

Comment implémenter l'algorithme du problème du sac à dos en PHP

Le problème du sac à dos est un problème d'optimisation combinatoire classique. Son objectif est de sélectionner un ensemble d'éléments pour maximiser leur valeur totale dans le cadre d'une capacité de sac à dos limitée. Dans cet article, nous présenterons comment utiliser PHP pour implémenter l'algorithme du problème du sac à dos et fournirons des exemples de code correspondants.

1. Description du problème du sac à dos

Le problème du sac à dos peut être décrit de la manière suivante : étant donné un sac à dos d'une capacité C et N articles. Chaque élément i a un poids wi et une valeur vi. Il est nécessaire de sélectionner certains articles parmi ces N articles afin que leur poids total ne dépasse pas la capacité du sac à dos C et que leur valeur totale soit maximisée.

2. Algorithme de programmation dynamique

La programmation dynamique est une méthode courante pour résoudre le problème du sac à dos. Son idée de base est de diviser le problème en plusieurs sous-problèmes et de calculer la solution optimale pour chaque sous-problème. Ensuite, grâce à la récursion étape par étape, la solution optimale au problème initial est finalement obtenue.

Ce qui suit est un exemple de code qui utilise un algorithme de programmation dynamique pour résoudre le problème du sac à dos :

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

$C = 10; // 背包容量
$weights = array(2, 3, 4, 5); // 物品重量
$values = array(3, 4, 5, 6); // 物品价值
$N = count($weights); // 物品数量

$result = knapsack($C, $weights, $values, $N);

echo "背包问题的最优解为：" . $result;

Le code ci-dessus utilise un tableau bidimensionnel$dp pour enregistrer la solution optimale de chaque sous-problème. Où $dpi représente la valeur maximale de sélection de certains éléments parmi les i premiers éléments afin que leur poids total ne dépasse pas j. La formule de récursion est :

$dp[i][j] = max($values[i - 1] + $dp[i - 1][$j - $weights[i - 1]], $dp[i - 1][$j]);

Enfin, nous obtenons la solution optimale au problème du sac à dos en sortant $dpN.

3. Résumé

Cet article présente comment utiliser PHP pour implémenter l'algorithme du problème du sac à dos Grâce à la programmation dynamique, nous pouvons résoudre efficacement le problème du sac à dos. J'espère que cet article pourra fournir de l'aide aux lecteurs qui souhaitent apprendre l'algorithme du problème du sac à dos.

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!