Code Coverage for /var/www/html/dev/src/phpOMS/Algorithm/CoinMatching/MinimumCoinProblem.php

1	<?php
2	/**
3	* Jingga
4	*
5	* PHP Version 8.1
6	*
7	* @package phpOMS\Algorithm\CoinMatching
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\CoinMatching;
16
17	/**
18	* Matching a value with a set of coins
19	*
20	* @package phpOMS\Algorithm\CoinMatching
21	* @license OMS License 2.0
22	* @link https://jingga.app
23	* @since 1.0.0
24	*/
25	final class MinimumCoinProblem
26	{
27	/**
28	* Constructor
29	*
30	* @since 1.0.0
31	* @codeCoverageIgnore
32	*/
33	private function __construct()
34	{
35	}
36
37	/**
38	* Find the minimum amount of coins that are required to match a value
39	*
40	* @param array $coins Types of coins available (every coin has infinite availablity)
41	* @param int $value Value to match with the coins
42	*
43	* @return array
44	*
45	* @since 1.0.0
46	*/
47	public static function getMinimumCoinsForValueI(array $coins, int $value) : array
48	{
49	// amount of required coins for different values
50	$table = [0];
51	$usedCoins = [];
52
53	for ($i = 1; $i <= $value; ++$i) {
54	$table[$i] = \PHP_INT_MAX;
55	}
56
57	$m = \count($coins);
58
59	for ($i = 1; $i <= $value; ++$i) {
60	for ($j = 0; $j < $m; ++$j) {
61	if ($coins[$j] <= $i) {
62	$subRes = $table[$i - $coins[$j]];
63
64	if ($subRes !== \PHP_INT_MAX
65	&& $subRes + 1 < $table[$i]
66	) {
67	$table[$i] = $subRes + 1;
68	$usedCoins[$i] = $coins[$j] === null ? ($usedCoins[$i] ?? []) : \array_merge($usedCoins[$i - $coins[$j]] ?? [], [$coins[$j]]);
69	}
70	}
71	}
72	}
73
74	return $usedCoins[$value] ?? [];
75	}
76	}