samdark / sack
Fund package maintenance!
Patreon
Requires
- php: ^8.0
Requires (Dev)
- phpunit/phpunit: ^9.5
- roave/infection-static-analysis-plugin: ^1.18
- vimeo/psalm: ^4.22
This package is auto-updated.
Last update: 2024-10-09 19:52:46 UTC
README
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