samdark/sack

This package implements "0-1 Knapsack Problem" algorithm i.e. allows to find the best way to fill a knapsack of a specified volume with items of a certain volume and value.

It could be applied to:

• Filling a box with most valued items.
• Selecting best tasks for a week knowing each task value and effort in days.
• Selecting attractions to visit in a limited time knowing how much one wants to visit an attraction and time required for a visit.
• etc.

Installation

The package could be installed with composer:

composer require samdark/sack --prefer-dist

General usage

declare(strict_types=1);

use Samdark\Sack\Item;
use Samdark\Sack\SackFiller;

require __DIR__ . '/vendor/autoload.php';

// Items to select from
$items = [
    new Item('Guitar', 1, 1500),
    new Item('Player', 4, 3000),
    new Item('Laptop', 3, 2000),
];

$sackVolume = 7;
$filler = new SackFiller($sackVolume);
$result = $filler->fill($items);

echo "Possible items:\n\n";
echo "Name\tVolume\tValue\n";
foreach ($items as $item) {
    echo "{$item->getName()}\t{$item->getVolume()}\t{$item->getValue()}\n";
}

echo "\n\nMaximum value for sack of $sackVolume is {$result->getValue()}:\n\n";
echo "Name\tVolume\tValue\n";
foreach ($result->getItems() as $item) {
    echo "{$item->getName()}\t{$item->getVolume()}\t{$item->getValue()}\n";
}

Testing

Unit testing

The package is tested with PHPUnit. To run tests:

./vendor/bin/phpunit

Mutation testing

The package tests are checked with Infection mutation framework with Infection Static Analysis Plugin. To run it:

./vendor/bin/roave-infection-static-analysis-plugin

Static analysis

The code is statically analyzed with Psalm. To run static analysis:

./vendor/bin/psalm