How to solve knapsack problem in PHP using dynamic programming algorithm and get optimal solution?

How to use dynamic programming algorithm to solve the knapsack problem in PHP and obtain the optimal solution?

The knapsack problem is one of the classic combinatorial optimization problems in computer science. Given a set of items and the capacity of a knapsack, how to select items to put into the knapsack so as to maximize the total value of the items in the knapsack is the core of the knapsack problem that needs to be solved.

Dynamic programming is one of the common methods to solve the knapsack problem. It finally obtains the optimal solution by splitting the problem into sub-problems and saving the solutions to the sub-problems. Below we will explain in detail how to use dynamic programming algorithm to solve the knapsack problem in PHP.

First, we need to define the input and output of the knapsack problem:

Input:

• The weight array $weights of the item, $weights[$i] represents the The weight of $i items
• The value array of items$values, $values[$i] represents the value of $i item
• The capacity of the backpack$capacity, indicating the maximum capacity of the backpack

Output:

• The maximum total value of the items in the backpack

Next, we need to define a two-dimensional array $dp, using to save the solution to the subproblem. $dp[$i][$j] represents the maximum total value of the first $i items when the backpack capacity is $j.

The algorithm flow is as follows:

1. Initialize the $dp array and set all elements to 0.

2. The outer loop traverses the index of the item, from $i = 1 to $i = count($weights) - 1:

   • The inner loop traverses The capacity of the backpack, from $j = 0 to $j = $capacity:

     • If the weight of the current item $weights[$i] is greater than the capacity of the backpack $j, then $dp[$i] [$j] = $dp[$i - 1][$j], that is, the current item cannot be put into the backpack, and the maximum total value is the same as the previous $i - 1 item.
     • Otherwise, the current item can be put into the backpack, and the value it generates $values[$i] plus the maximum total value before putting the item into it $dp[$i - 1][$j - $ weights[$i]], compared with the current value, take the larger value as $dp[$i][$j].
3. Returns $dp[count($weights) - 1][$capacity], that is, the first count($weights) items in the backpack have a capacity of $capacity maximum total value at the time.

The following is a dynamic programming algorithm for the knapsack problem using PHP code:

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

Using the above code, we can do this by calling knapsack($weights, $values, $capacity ) function to solve the knapsack problem and obtain the optimal solution.

I hope this article can help you understand how to use dynamic programming algorithm to solve the knapsack problem in PHP and obtain the optimal solution.

The above is the detailed content of How to solve knapsack problem in PHP using dynamic programming algorithm and get optimal solution?. For more information, please follow other related articles on the PHP Chinese website!