Fund package maintenance!

1.0.0 2022-09-06 12:49 UTC

This package is auto-updated.

Last update: 2024-04-07 12:48:29 UTC


Latest Stable Version Total Downloads Build status Scrutinizer Code Quality Code Coverage Mutation testing badge static analysis type-coverage

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.


The package could be installed with composer:

composer require samdark/sack --prefer-dist

General usage


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


Unit testing

The package is tested with PHPUnit. To run tests:


Mutation testing

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


Static analysis

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