How to use backtracking to achieve an efficient solution to the 0-1 knapsack problem in PHP?

How to use backtracking to achieve an efficient solution to the 0-1 knapsack problem in PHP?

The knapsack problem is a classic combinatorial optimization problem that is often mentioned in many algorithm courses and interviews. One of the common knapsack problems is the 0-1 knapsack problem, which is also one of the most basic knapsack problems. The 0-1 knapsack problem is described as follows: given a set of items, each item has a weight and a value. Now there is a backpack with a capacity C. We need to select some items to put into the backpack so that the total weight of the items does not exceed the backpack capacity and the total value of the items is maximized.

The backtracking method is a classic algorithm for solving combinatorial optimization problems. It finally finds the optimal solution by constantly trying the possible solution space. The backtracking method can play a big role in achieving an efficient solution to the 0-1 knapsack problem. The following is a specific code example of using the backtracking method to implement the 0-1 knapsack problem in 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;

?>

The above code uses recursion to solve the 0-1 knapsack problem. Function knapsack receives a series of parameters, including the current maximum value, the total weight and total value of the currently selected items, the currently selected item index, the total weight of the backpack, and the weight and value array of the items. In the function body, first determine whether all items have been selected or the backpack has been filled. If so, the total value of the currently selected items is returned. Then try to select the current item or not select the current item, recursively solve for the maximum value in both cases, and return the larger value of the two. Finally, the maximum output value is the solution to the problem.

The time complexity of this algorithm is exponential, so there will be certain performance issues when dealing with large-scale problems. However, in practical applications, memorization technology can be added to save the calculated results to avoid repeated calculations and improve program efficiency.

The above is the detailed content of How to use backtracking to achieve an efficient solution to the 0-1 knapsack problem in PHP?. For more information, please follow other related articles on the PHP Chinese website!