PHP algorithm analysis: How to use dynamic programming algorithm to solve the 0-1 knapsack problem?

PHP algorithm analysis: How to use dynamic programming algorithm to solve the 0-1 knapsack problem?

Introduction:
Dynamic programming is an algorithmic idea commonly used to solve optimization problems. In program development, the 0-1 knapsack problem is a classic dynamic programming application scenario. This article will introduce how to use PHP to write a dynamic programming algorithm to solve the 0-1 knapsack problem, and provide specific code examples.

What is the 0-1 knapsack problem?
0-1 knapsack problem is a classic combinatorial optimization problem. The problem is set as follows: There is a backpack with a capacity of C. There are n items, each item has a weight w[i] and a value v[i]. It is required to choose a combination of items to maximize the total value without exceeding the capacity of the backpack.

Dynamic programming solution
The dynamic programming algorithm divides the given problem into a series of sub-problems and stores the optimal solutions of the sub-problems, and finally solves the optimal solution of the entire problem. For the 0-1 knapsack problem, we can use dynamic programming algorithm to solve it.

Algorithm idea:

1. Create a two-dimensional array dp, dpi represents the maximum value when only the first i items are considered and the backpack capacity is j.
2. Initialize the dp array and set all elements to 0.

3. Traverse items:

   • For each item, if its weight is less than or equal to the backpack capacity j, you need to compare the weight when the item is put in and when the item is not put in. Value size, choose a larger solution to update the dp array.
   • If the weight of the item is greater than the backpack capacity j, you can only choose not to put the item in, that is, dpi = dpi-1.
4. After the cycle ends, dpn is the maximum value when the backpack capacity is C.

Specific code example:

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);

Code analysis:

• Function knapsackAccepts four parameters: backpack capacity C, items Weight array weight, item value array value and item quantity n.
• Create a two-dimensional array $dp to store the optimal solution to the sub-problem.
• Initialize the dp array and set all elements to 0.
• Loop through items and judge and update based on the state transition equation of dynamic programming.
• After the loop ends, the returned dpn is the maximum value when the backpack capacity is C.

Conclusion:
By using dynamic programming algorithm to solve the 0-1 knapsack problem, the maximum value that the knapsack can hold can be efficiently solved. In PHP, this algorithm can be implemented by writing appropriate code. This algorithmic idea is not only applicable to the 0-1 knapsack problem, but also can be applied to other similar combinatorial optimization problems.

The above is the detailed content of PHP algorithm analysis: How to use dynamic programming algorithm to solve the 0-1 knapsack problem?. For more information, please follow other related articles on the PHP Chinese website!