Python Challenge

Question

I am doing the coin-change problem. I have finished the problem, that it prints out how many coins I need to make the least amount of change possible, but how do I change my program so that it also prints those coins??

Here is a sample I/O:

input: coin_change(48, [1, 5, 10, 25, 50])

output: [6, [25, 10, 10, 1, 1, 1]]

input: coin_change(48, [1, 7, 24, 42])

output: [2, [24, 24]]

Currently my code only returns the 6.

By the way, this must be done with recursion only. No loops are allowed.

Code:

def change(C, V):
    def min_coins(i, aC):
        if aC == 0:
            return 0
        elif i == -1 or aC < 0:
            return float('inf')
        else:
            return min(min_coins(i-1, aC), 1 + min_coins(i, aC-V[i]))
    return min_coins(len(V)-1, C)

The code below is what I tried, but it does NOT work for the second input

def giveChange(C, V, res = None):
    res=[] if res is None else res
    if len(V)==0:
        return len(res),res
    maxx=max(V)
    print maxx
    V.remove(maxx)
    ans=C//maxx
    if ans==0 and maxx<C :
        print maxx
        res +=[maxx]*ans
        return  len(res),res
    else:
        res += [maxx]*ans
        return  giveChange(C % maxx,V,res)

Since this is homework (and even if it wasn't), we'd like to see some effort on your part, first. What have you tried? What worked? What hasn't? Why? — Cat
– Cat, Commented Sep 22, 2012 at 1:08

xwb1989 · Accepted Answer · 2012-09-22 04:43:16Z

1

Might not use maxx=max(V)

An optimal solution may comprise of small coins, for example 48=24+24, which has two coins, lesser than 48=25+10+10+1+1+1. In that case, though 25>24, you have to use more tiny coins to make a 48.

Thus if your input is (48, [1, 7, 24, 42]), you will be trapped in the second situation and get a 48 = 42+1+1+1+1+1+1. You can combine your second posted codes with your first one, add a list as parameter for storing the changes and use the same recursion design.

answered Sep 22, 2012 at 4:43

xwb1989

3431 silver badge14 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

swang · Accepted Answer · 2012-09-22 05:13:28Z

0

Your first code will work with a few changes. Instead of returning just count, a function can return a list or even (count, [coins]) tuple. you may also want to sort V.

answered Sep 22, 2012 at 5:13

swang

2191 silver badge3 bronze badges

1 Comment

swang Over a year ago

that is not important. my point is your first code is logically correct. With a few tweaks it will also return list of coins. it can be done without passing a mutable list as parameter.

Collectives™ on Stack Overflow

Python Challenge

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related