Comment utiliser le backtracking pour trouver une solution efficace au problème du sac à dos 0-1 en PHP ?

Comment utiliser le backtracking pour obtenir une solution efficace au problème du sac à dos 0-1 en PHP ?

Le problème du sac à dos est un problème d'optimisation combinatoire classique qui est souvent mentionné dans de nombreux cours et entretiens sur l'algorithme. L’un des problèmes courants liés au sac à dos est le problème du sac à dos 0-1, qui est également l’un des problèmes les plus fondamentaux du sac à dos. Le problème du sac à dos 0-1 est décrit comme suit : étant donné un ensemble d’éléments, chaque élément a un poids et une valeur. Il existe maintenant un sac à dos d'une capacité C. Nous devons sélectionner certains articles à mettre dans le sac à dos afin que le poids total des articles ne dépasse pas la capacité du sac à dos et que la valeur totale des articles soit maximisée.

La méthode de backtracking est un algorithme classique de résolution de problèmes d'optimisation combinatoire. Elle trouve finalement la solution optimale en essayant constamment l'espace de solutions possibles. La méthode de retour en arrière peut jouer un rôle important dans la recherche d’une solution efficace au problème du sac à dos 0-1. Ce qui suit est un exemple de code spécifique d'utilisation de la méthode de backtracking pour implémenter le problème du sac à dos 0-1 en PHP :

<?php

// 通过回溯法解决0-1背包问题

/**
 * @param int $maxValue 当前最大价值
 * @param int $curWeight 当前已选择物品的总重量
 * @param int $curValue 当前已选择物品的总价值
 * @param int $curIndex 当前已选择的物品索引
 * @param int $totalWeight 背包的总重量
 * @param int[] $weights 物品的重量数组
 * @param int[] $values 物品的价值数组
 * @return int 当前已选择物品的最大价值
 */
function knapsack($maxValue, $curWeight, $curValue, $curIndex, $totalWeight, $weights, $values)
{
    if ($curIndex == count($weights) || $curWeight == $totalWeight) {
        return $curValue;
    }
  
    $value1 = 0;
    if ($curWeight + $weights[$curIndex] <= $totalWeight) {
        // 选择当前物品
        $value1 = knapsack($maxValue, $curWeight + $weights[$curIndex], $curValue + $values[$curIndex], $curIndex + 1, $totalWeight, $weights, $values);
    }
  
    // 不选择当前物品
    $value2 = knapsack($maxValue, $curWeight, $curValue, $curIndex + 1, $totalWeight, $weights, $values);

    return max($value1, $value2);
}
  
$weights = [2, 3, 4, 5]; // 物品的重量数组
$values = [3, 4, 8, 9]; // 物品的价值数组
$totalWeight = 9;  // 背包的总重量

$maxValue = knapsack(0, 0, 0, 0, $totalWeight, $weights, $values);

echo "最大价值为：" . $maxValue;

?>

Le code ci-dessus utilise la récursivité pour résoudre le problème du sac à dos 0-1. La fonction knapsack reçoit une série de paramètres, notamment la valeur maximale actuelle, le poids total et la valeur totale des articles actuellement sélectionnés, l'index de l'article actuellement sélectionné, le poids total du sac à dos et le tableau de poids et de valeur des articles. Dans le corps de la fonction, déterminez d'abord si tous les éléments ont été sélectionnés ou si le sac à dos a été rempli. Si tel est le cas, la valeur totale des éléments actuellement sélectionnés est renvoyée. Essayez ensuite de sélectionner l'élément actuel ou de ne pas sélectionner l'élément actuel, résolvez de manière récursive la valeur maximale dans les deux cas et renvoyez la plus grande valeur des deux. Enfin, la valeur de sortie maximale est la solution au problème.

La complexité temporelle de cet algorithme est exponentielle, il y aura donc certains problèmes de performances lors du traitement de problèmes à grande échelle. Cependant, dans les applications pratiques, une technologie de mémorisation peut être ajoutée pour sauvegarder les résultats calculés afin d'éviter des calculs répétés et d'améliorer l'efficacité du programme.

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!