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
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";
}">
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
3 Aug 9, 2022
12.6k Dec 30, 2022
9 Aug 15, 2022
477 Jan 7, 2023
107 Dec 8, 2022
7 Oct 19, 2022
2 Jan 16, 2022
2 Sep 29, 2022
2 Sep 18, 2021
1 May 11, 2022
3 Jan 4, 2022
3 Jan 13, 2022
5 Nov 14, 2021
10 Nov 2, 2022
5 Jul 19, 2022
6 Aug 3, 2022
236 Dec 21, 2022
8 Nov 6, 2022
4 Oct 13, 2022