Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00% covered (success)
100.00%
12 / 12
100.00% covered (success)
100.00%
2 / 2
 CRAP
100.00% covered (success)
100.00%
1 / 1
Continuous
100.00% covered (success)
100.00%
12 / 12
100.00% covered (success)
100.00%
2 / 2
 5
100.00% covered (success)
100.00%
1 / 1
 __construct
n/a
0 / 0
n/a
0 / 0
 1
 continuousComparator
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
 1
 solve
100.00% covered (success)
100.00%
11 / 11
100.00% covered (success)
100.00%
1 / 1
 3
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 */
13declare(strict_types=1);
14
15namespace phpOMS\Algorithm\Knapsack;
16
17/**
18 * Continuous knapsack algorithm
19 *
20 * @package phpOMS\Algorithm\Knapsack
21 * @license OMS License 2.0
22 * @link    https://jingga.app
23 * @since   1.0.0
24 */
25final class Continuous
26{
27    /**
28     * Constructor
29     *
30     * @since 1.0.0
31     * @codeCoverageIgnore
32     */
33    private function __construct()
34    {
35    }
36
37    /**
38     * Comparing items
39     *
40     * @param Item[] $a Item
41     * @param Item[] $b Item
42     *
43     * @return int
44     *
45     * @since 1.0.0
46     */
47    private static function continuousComparator(array $a, array $b) : int
48    {
49        return $b['item']->getValue() / $b['item']->getCost() <=> $a['item']->getValue() / $a['item']->getCost();
50    }
51
52    /**
53     * Fill the backpack with items
54     *
55     * @param array             $items    Items to fill the backpack with ['item' => Item, 'quantity' => ?]
56     * @param BackpackInterface $backpack Backpack to fill
57     *
58     * @return BackpackInterface
59     *
60     * @since 1.0.0
61     */
62    public static function solve(array $items, BackpackInterface $backpack) : BackpackInterface
63    {
64        /* @phpstan-ignore-next-line */
65        \usort($items, ['self', 'continuousComparator']);
66
67        $availableSpace = $backpack->getMaxCost();
68
69        foreach ($items as $item) {
70            if ($availableSpace <= 0.0) {
71                break;
72            }
73
74            $backpack->addItem(
75                $item['item'],
76                $quantity = \min($item['quantity'], $availableSpace / $item['item']->getCost())
77            );
78
79            $availableSpace -= $quantity * $item['item']->getCost();
80        }
81
82        return $backpack;
83    }
84}