Code Coverage |
||||||||||
Lines |
Functions and Methods |
Classes and Traits |
||||||||
| Total | |
100.00% |
26 / 26 |
|
100.00% |
1 / 1 |
CRAP | |
100.00% |
1 / 1 |
| Bounded | |
100.00% |
26 / 26 |
|
100.00% |
1 / 1 |
10 | |
100.00% |
1 / 1 |
| __construct | n/a |
0 / 0 |
n/a |
0 / 0 |
1 | |||||
| solve | |
100.00% |
26 / 26 |
|
100.00% |
1 / 1 |
9 | |||
| 1 | <?php |
| 2 | /** |
| 3 | * Jingga |
| 4 | * |
| 5 | * PHP Version 8.1 |
| 6 | * |
| 7 | * @package phpOMS\Algorithm\Knapsack |
| 8 | * @copyright Dennis Eichhorn |
| 9 | * @license OMS License 2.0 |
| 10 | * @version 1.0.0 |
| 11 | * @link https://jingga.app |
| 12 | */ |
| 13 | declare(strict_types=1); |
| 14 | |
| 15 | namespace phpOMS\Algorithm\Knapsack; |
| 16 | |
| 17 | /** |
| 18 | * Bounded knapsack algorithm |
| 19 | * |
| 20 | * This algorithm only works for integer cost, values and quantities! |
| 21 | * |
| 22 | * @package phpOMS\Algorithm\Knapsack |
| 23 | * @license OMS License 2.0 |
| 24 | * @link https://jingga.app |
| 25 | * @since 1.0.0 |
| 26 | */ |
| 27 | final class Bounded |
| 28 | { |
| 29 | /** |
| 30 | * Constructor |
| 31 | * |
| 32 | * @since 1.0.0 |
| 33 | * @codeCoverageIgnore |
| 34 | */ |
| 35 | private function __construct() |
| 36 | { |
| 37 | } |
| 38 | |
| 39 | /** |
| 40 | * Fill the backpack with items |
| 41 | * |
| 42 | * This algorithm only works for integer cost, values and quantities! |
| 43 | * |
| 44 | * @param array $items Items to fill the backpack with ['item' => Item, 'quantity' => ?] |
| 45 | * @param BackpackInterface $backpack Backpack to fill |
| 46 | * |
| 47 | * @return BackpackInterface |
| 48 | * |
| 49 | * @since 1.0.0 |
| 50 | */ |
| 51 | public static function solve(array $items, BackpackInterface $backpack) : BackpackInterface |
| 52 | { |
| 53 | $n = \count($items); |
| 54 | |
| 55 | // @var int<0, max> $maxCost |
| 56 | $maxCost = (int) $backpack->getMaxCost(); |
| 57 | $mm = \array_fill(0, ($maxCost + 1), 0); |
| 58 | $m = []; |
| 59 | $m[0] = $mm; |
| 60 | |
| 61 | for ($i = 1; $i <= $n; ++$i) { |
| 62 | $m[$i] = $mm; |
| 63 | |
| 64 | for ($j = 0; $j <= $maxCost; ++$j) { |
| 65 | $m[$i][$j] = $m[$i - 1][$j]; |
| 66 | |
| 67 | for ($k = 1; $k <= $items[$i - 1]['quantity']; ++$k) { |
| 68 | if ($k * ((int) $items[$i - 1]['item']->getCost()) > $j) { |
| 69 | break; |
| 70 | } |
| 71 | |
| 72 | $v = $m[$i - 1][$j - $k * ((int) $items[$i - 1]['item']->getCost())] + $k * ((int) $items[$i - 1]['item']->getValue()); |
| 73 | |
| 74 | if ($v > $m[$i][$j]) { |
| 75 | $m[$i][$j] = $v; |
| 76 | } |
| 77 | } |
| 78 | } |
| 79 | } |
| 80 | |
| 81 | $s = 0; |
| 82 | for ($i = $n, $j = $maxCost; $i > 0; --$i) { |
| 83 | $s = 0; |
| 84 | $v = $m[$i][$j]; |
| 85 | |
| 86 | $value = (int) $items[$i - 1]['item']->getValue(); |
| 87 | |
| 88 | for ($k = 0; $v !== $m[$i - 1][$j] + $k * $value; ++$k) { |
| 89 | ++$s; |
| 90 | $j -= (int) $items[$i - 1]['item']->getCost(); |
| 91 | } |
| 92 | |
| 93 | if ($s > 0) { |
| 94 | $backpack->addItem($items[$i - 1]['item'], $s); |
| 95 | } |
| 96 | } |
| 97 | |
| 98 | return $backpack; |
| 99 | } |
| 100 | } |