All geek questions in one place

The most optimal coin is suitable for a given amount of money

How would you achieve a given amount in the most optimal way if you set a set of coins?

Let's say that in this case we have random numbers from coins 1, 5, 10, 20 and 50 cents, with the largest coins taking priority.

My first intuition would be to use all the largest coins that could be picked up, and then use the next smallest coin in value if the amount is exceeded.

Will it do this or is there a flaw in this approach? Are there more effective approaches?

+3
source share
3 answers

There are drawbacks to simply giving out the largest coins.

Suppose your vending machine is located outside each coin, with the exception of twenty of each of the coins 50c, 20c and 1c, and you need to deliver 60c per shift.

The “biggest priority” (or greedy) scheme will give you eleven coins, one 50 c coin and ten 1c coins.

The best solution is three 20c coins.

Greedy schemes give only local optimal solutions. For global optima, as a rule, you need to study all the possibilities (although there may be minimax-type algorithms to reduce the search space) to be sure that for delivery of changes it is usually within computability limits.

+8
source

Greedy algorithms (what you are doing right now) are usually chosen for this type of thing and implemented as Final State Machines for use in vending machines (for this particular case).

The greedy algorithm determines the minimum number of coins to give when making changes. These are the steps that a person will take to imitate a greedy algorithm.

+3
source

The assumption of exhaustion of the highest denomination will not be the best solution every time. Example:

Input: coins[] = {25, 10, 5}, V = 30 Output: Minimum 2 coins required We can use one coin of 25 cents and one of 5 cents Input: coins[] = {9, 6, 5, 1}, V = 11 Output: Minimum 2 coins required We can use one coin of 6 cents and 1 coin of 5 cents (min) As per logic of exhausting largest coins first, we would end up with one coin of 9 cents and 2 coins of 1 cent

See this answer for more details.

0
source

Source: https://habr.com/ru/post/1439959/

More articles:


All Articles