phpalgorithmsortingcoin-change# Find the coin change (Greedy Algorithm) when coins are in decimals and returned amount in coins is larger then original return value

I need to find the number of coins that make a given value where coins are in decimals and there is a possibility that the algorithm will return more coins (money) because there is no way to return the exact value where the returned amount is close to the given value.

For example:

```
Coins: [23, 29.90, 34.50]
Value: 100
```

Possible solutions:

```
Solution 1: 34.60, 34.50, 29.90, 23 (122)
Solution 2: 29.90, 29.90, 29.90 ,29.90 (119.90)
Solution 3: 23, 23, 23, 23, 23 (115)
Solution 4: 23, 23, 23, 34.50 (103.5)
```

Based on the possible solutions, the clear winner is "Solution 4" and I am looking for an algorithm that will help me to solve this issue. I don't care how many coins are used I just need to be sure that returned values in coins are as close as passed/desired value.

Does someone know the solution or algorithm for this case?

Solution

Greedy algorithm assumes that you get the largest possible coin, then the next possible and so on until you reach the sum. But it does not provide the best solution in general case.

So consider using of table containing possible sums:

Multiply sum and all nominals by 100 to work in integers.

Make array `A[]`

of length `1 + sum + largest_coin`

, filled with zeros, set `A[0]`

into `-1`

.

For every coin nominal `C`

walk through array. If `A[i-C]`

is not zero, put value `C`

into `A[i]`

After all scan array range `A[sum]..A[max]`

to find the first non-zero item. It's index `K`

represents the best sum. This cell contains the last coin added - so you can unwind the whole combination, walking down until index 0: `A[k] => A[k - A[k]]`

an so on

Python code

```
def makesum(lst, summ):
mx = max(lst)
A = [-1] + [0]*(mx+summ)
for c in lst:
for i in range(c, summ + c + 1):
if A[i - c]:
A[i] = c
print(A)
#look for the smallest possible combination >= summ
for k in range(summ, summ + mx + 1):
if A[k]:
break
if (k == summ + mx + 1):
return
# unwind combination of used coins
while (k > 0):
print(A[k])
k = k - A[k]
makesum([7, 13, 21], 30)
```

Array for reference. Non-zero entries - for possible sums.

```
[-1, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 13, 7, 0, 0, 0, 0, 0, 13, 21, 0, 0,
0, 0, 13, 13, 21, 0, 0, 0, 0, 13, 21, 21, 0, 0, 0, 13, 13, 21, 21, 0, 0, 0,
0, 21, 21, 21, 0, 0]
```

Combination:

```
13
13
7
```

- What Path is acceptable?
- How to add variation stock status to Woocommerce product variation dropdown
- How can I change the Blade template file extention from *.blade.php to only *.blade
- Partial of PHP page does not refresh with AJAX call
- Change programmatically the email for new order, cancelled order and failed order WooCommerce notifications
- Nginx php 2 location forward to 2 different php app using docker
- How to remove all Woocommerce checkout billing fields without errors
- "Unresolvable dependency resolving" Laravel error
- Run cron job on cpanel with php7 version
- Upload files - array created in wrong way?
- Does php send a cookie to localhost with HTTP when session_start() with cookie_secure equal to true?
- When should I use static methods?
- Memcache alternatives, more control
- How to insert string before last line?
- php write hebrew / UTF-8 in csv
- Warning: mysqli_connect(): (HY000/2002): No such file or directory
- Get Invaild Argument Error with Google Wallet API when create a generic base class on PHP
- Allow only one downloadable product in WooCommerce cart
- Is it safe for the Stripe client_secret to be in the redirect URL?
- PHP Code Functioning as Intended but UNION Injection Payload Doesn't Work
- jQuery Color Changer - Ajax save not run
- How to create JSON API service from MySQL database in PHP
- "The zip extension and unzip/7z commands are both missing, skipping" in Windows during composer install laravel
- how to change email authentication by username using laravel?
- Is there a Wordpress php function that can return just the URL of the Custom Logo image(not the full image tag)?
- Filter the output of a select2_from_ajax field depending on another field in crud Backpack Laravel
- Removing email acc queries from MariaDB doesn't work
- PHP $row to array
- optional named argument after variadic argument
- Is it possible to send POST data with a PHP redirect?