CODEWITHSUNDEEP
python
Vaibhav Yadav
Vaibhav Yadav

Reputation: 9

Minimum coins needed to sum up an amount

This is the minimum coins, problem.

I am not able to handle the case when the return type of function is None. I tried something like if min_count != None && min_count <= counter: but this is not so proper.

Please tell me the correct way of doing this.

# min coin problem using a recursive approach
# this program is giving me all the solutions available in all combination

counter = 10000
def min_coin(Amount,coins_available,count):
    global counter
    if (Amount == 0):
        return count
    for i in coins_available:
        if Amount >= i:
            min_count =  min_coin(Amount - i,coins_available,count+1)
        if  min_count <= counter:
            counter = min_count

Amount = 2
coins_available = [1,2]

count = 0
min_coin(Amount,coins_available,count)
print(counter)

Upvotes: 0

Views: 384

Answers (2)

Antares
Antares

Reputation: 92

This is the Change-making problem. It can be solved using the greedy approach which works really well when the problem has the greedy choice.

This algorithm works for "canonical coin systems", systems where each value (coin value in our example) is at least double the value of the item before it.

You can see that if you give as input lets say Amount: 40 and Coins_available: [20, 10, 5, 2, 1] - Then it works perfectly,

but for Amount: 40 and Coins_available: [25, 20, 10, 5, 2, 1] - Check to see what we get.

def min_coin(amount, coins_available):

# Making sure your coin array is sorted in descending order
# This way we make sure to include the largest possible coin each time
coins_available.sort(reverse=True)

# Initializing our array that will hold the coins we choose
selected_coins = []

for i in range(len(coins_available)):
    while (amount >= coins_available[i]):
        
        # Evey time we pick a coin, we reduce the amount left by that coin's amount
        amount -= coins_available[i]
        selected_coins.append(coins_available[i])

    if(amount == 0):
        break;

for coin in selected_coins:
    print(coin)

In this solution I simplified some statements and removed unnecessary variables.

Try to avoid using global variables and also you can do the printing from within the function, otherwise you can just return the list and use it as you wish.

The way it works is it looks for the largest (in terms of value) coin we have, then checks if we can give it as change, if yes, we give it as change, reduce the amount left and check again. Once the amount left is less that the largest coin we move to the second largest.

This way we know our program is correct because the underlying algorithm is correct. Try to answer yourself why.

Hint:

See if you can assume that the solution is wrong and come up with a "correct" one, if you cant then its correct)

I hope this helped in understanding.

Upvotes: 1

DarrylG
DarrylG

Reputation: 17156

Corrected code to return min_count and rewritten without globals

def min_coin(amount, coins_available):
     if amount == 0:
        return 0
     
     # Find minimum count by recursive trying each coin
     min_count = 100000     # Initialze to large number
     for i in coins_available:
        if amount >= i:
            count =  1 + min_coin(amount - i, coins_available)
            
            if  count < min_count:
                min_count = count    # Lower min
                
     return min_count         # need return otherwise in parent conditional 
                              # won't work since will have 1 + None
            

print(min_coin(2, [1, 3]))  # Output: 2
print(min_coin(3, [1, 3]))  # Output: 1
print(min_coin(6, [1, 3]))  # Output: 2

Upvotes: 0

Related Questions