The problem of optimization.

Knapsack algorithm is frequent used piece of code appearing in variety different applications in various forms. Given a container with limited capacity and a set of items represented in two dimensions (weight/value), the goal is to find most valuable combination of items. To achieve this we must sort items by weight/value ratio in ascending order first.

// [weight,value,name]
<?php
$items = [
    [1, 2, 'pens'], // ratio: 2
    [3, 6, 'game'], // ratio: 2
    [3, 5, 'book'], // ratio: 5/3
    [5, 6, 'shoes'], // ratio: 6/5
];

// Sort items by value/weight ratio callback.
function valueWeight($a, $b)
{
    $a0 = $a[1] / $a[0];
    $b0 = $b[1] / $b[0];
    if ($a0 == $b0) {
        return 0;
    }
    return ($a0 < $b0) ? -1 : 1;
}

usort($items, "valueWeight");

var_dump($items);

Building values matrix.

Now we are ready to build an array containing all item values for each weight.

For better understanding how algorithm is going to work, table below shows every value for our loop. Numbers in red, are values of finally selected items.

<?php
// Total knapsack weight. 
$totalWeight = 8;
// Values matrix
$values = [];
$item_count = count($items);

for ($j = 0; $j < $item_count; $j++) { // each item
    for ($i = 0; $i <= $totalWeight; $i++) { // each weight of item up to totalWeight
        if ($items[$j][0] <= $i) {
            if (isset($values[$j - 1][$i])) {
                $values[$j][$i] = max(
                    $items[$j][1] + $values[$j - 1][$i - $items[$j][0]],
                    $values[$j - 1][$i]
                );
            } else {
                $values[$j][$i] = $items[$j][1];
            }
        } else {
            if (isset($values[$j - 1][$i])) {
                $values[$j][$i] = $values[$j - 1][$i];
            } else {
                $values[$j][$i] = 0;
            }
        }
    }
}

var_dump($values);

Viewing selected items.

Unfortunately viewing results is not trivial. In order to display selected items we must walk backwards selected values and find corresponding items.

// Return knapsack most valued items.
$current_weight = $totalWeight; // current weight to find previous item
for ($i = $item_count - 1; $i >= 0; $i--) {
    if (isset($values[$i - 1])) {
        if ($values[$i][$current_weight] - $values[$i - 1][$current_weight] > 0) {
            var_dump($items[$i]);
            $current_weight = $current_weight - $items[$i][0];
        }
    } elseif ($values[$i][$current_weight] != 0) {
        var_dump($items[$i]);
    }
}