A knapsack is a bag with straps, usually carried by soldiers to help them take their necessary items or valuables during their journey. Each item has a value and definite weight attached to it. So, the soldier has to pick the most valuable items within their maximum weight limit as they cannot put everything in their bag. The word 0/1 means that either we can take it or leave it. We cannot take an item partially. This is known as the famous 0-1 knapsack problem. We will take the bottom-up approach for solving the 0-1 knapsack problem. Here is the pseudocode for the solution:

Procedure knapsack(n, W, w1,...,wN, v1,...,vN) 
for w = 0 to W 
    M[0, w] = 0 

for i = 1 to n 
    for w = 0 to W 

    if wi > w : 
        M[i, w] = M[i-1, w] 
    else : 
        M[i, w] = max (M[i-1, w], vi + M[i-1, w-wi ]) 
return M[n, W] 

end procedure  

For example, if we have five items, [1,2,3,4,5], and they have the weight of 10,20,30,40,50, respectively, a maximum allowed weight of 10 will produce the following table using the bottom-up approach:

As we can see, we build the up the table bottom up where we start with one item and one weight and increase it to our desired weight and maximize the value count by choosing the best possible items. At the end, the last cell in the bottom-right corner is the one with the expected result for the 0-1 knapsack problem. Here is the implementation and code to run the function:

function knapSack(int $maxWeight, array $weights, array $values, int $n) { 
    $DP = []; 
    for ($i = 0; $i <= $n; $i++) { 
      for ($w = 0; $w <= $maxWeight; $w++) { 
          if ($i == 0 || $w == 0) 
          $DP[$i][$w] = 0; 
          else if ($weights[$i - 1] <= $w) 
          $DP[$i][$w] =  
            max($values[$i-1]+$DP[$i - 1][$w - $weights[$i-1]] 
            , $DP[$i - 1][$w]); 
          else 
          $DP[$i][$w] = $DP[$i - 1][$w]; 
        } 
    } 
    return $DP[$n][$maxWeight]; 
} 

$values = [10, 20, 30, 40, 50]; 
$weights = [1, 2, 3, 4, 5]; 
$maxWeight = 10; 
$n = count($values); 
echo knapSack($maxWeight, $weights, $values, $n); 

This will show 100 on the command line, which actually matches our expected result from the preceding table. The complexity of this algorithm is O (n*W), where n is the number of items and W is the target weight.