[brramiz]

so i basically have what i believe to be working code once i fix one problem.. and i'm not exactly sure how to fix the problem i'm having i'll post the code i have then the error i get below it. i know where the error is but i'm not sure what to do about it. any help would be appreciated thank you!

def min_number_of_coins (array, request):
  OutputArray = [None]*(request+1)
  x = 0
  OutputArray[0] = 0
  for value in array:
    if value > request: break
    OutputArray[value] = 1
  for i in range(request+1):
    a=i-x
    if OutputArray[i]: x = i
    else:
      OutputArray[i] = OutputArray[x] + OutputArray[a]
    print "i: ", i," OutputArray[i]: ", OutputArray[i]
  return OutputArray[request]

>>> min_number_of_coins([2,5,9],89)
i: 0 OutputArray[i]: 0

Traceback (most recent call last):
File "<pyshell#0>", line 1, in <module>
min_number_of_coins([2,5,9],89)
File "C:\Python26\coins3.py", line 12, in min_number_of_coins
OutputArray[i] = OutputArray[x] + OutputArray[a]
TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

[Martyr2]

Well the error is because on your second iteration of the for loop, you have values of i = 1, a = 1, x = 0 so when you use "a" in your array reference on line 12, it is pointing to index 1 which is set to None. Thus you are trying to add zero + [None] which of course doesn't work. Now that is the heart of the problem. As for a fix, I can't begin to even tell you because I have absolutely no clue what you are attempting to do here. If you want to know the number of coins for each denomination, you could be using integer division and modulus. Your code is also not very descriptive nor do you provide exactly what you are trying to do here.

But in short, you are referencing a spot in your array which is set to None. I probably would try not have have an array with None values in it to begin with.

[brramiz]

I got it! i just rethought my entire way about going and redid my code pretty much completely.. but i will explain.. the whole problem was about being able to take in an amount of units or cents and finding the least amount of coins of any given denomination so for example if i was told to make 89 cents of change with coins of denominations (1cent,4cents,7cents) then the least amount of coins i would need to make this amount of change would be 14 coins 12(7 cent coins), 1(4 cent coin) and 1(1 cent coin) and that is the whole point of the program. not having set denominations was where i was getting tripped up.

 CoinChange(M,c,d):
    MinCoins=[]
    MinCoins.append(0)
    n=0
    m=1
    while m<=M: #creates loop to test every amount
        Mins=200000 #sets high amount for minimum coins
        while n <= c-1: #creates loop to test every denomination
            if m>=d[n]: #only test coin amount if amount is higher than denomination
                if MinCoins[m-d[n]]+1 < Mins:
                    Mins=MinCoins[m-d[n]]+1 #sets mins to new value if value is lower
                    
            n=n+1 #increments n(denomination)
        m=m+1 #increments m up to amount
        n=0 #resets n(denomination)
        MinCoins.append(Mins) #adds Mins to array for all values
    return MinCoins[M]

[Martyr2]

Glad you got this working. However I think you would be doing yourself a great thing by looking at other change algorithms out there. The integer division/modulus setup would still work better than your current solution I believe. The idea is that you take the amount and divide it by given denominations. This could be all types of currency denominations or only the set ones you provide. Either way, it yields the least number of coins.

Good luck and I am happy you found a solution.

[mostyfriedman]

if coins follow the US coin system then you can use the greedy approach, otherwise dynamic programming is the way to go

[Steven Smith]

I was actually going to reply back with a similar response and more elaboration, but if the OPs requirement to work with ANY GIVEN denomination is valid, modulus division would not always yield and optimum or valid solution.

For example, if you needed to make change for 23c with denominations of 13c, 11c, and 1c, modulus division would yield an answer of one 13c coin and ten 1c coins. The correct answer is of course two 11c coins and one 1c coin.

Furthermore, if your problem was to make change for 23c with denominations of 13c, 11c, and 3c, modulus division would not even give a valid solution. If you use one 13c coin, no combination of the remaining coins can equal the remaining 10c. The correct solution would again be one 11c coin and four 3c coins.

The OP's algorithm looks like a brute force on the surface, but it has a subtle elegancy. Using my previous case of making change for 23c with 13/11/3c denoms... here is how hthe OP's program figures it out.

Sorry for the "Stream of Conciousness"

Basically, you start at 1 cent and work your way up trying to see what each coin does to your total.

1c - No solution because it is smaller than my smallest coin.
2c - "
3c - I can make this with a 3c coin. This leaves me with 3-3 = 0c. Look back at 0c (defined as 0) Store 1 + 0 = 1 here.
4c - I can make this with a 3c coin. However, I look back at 4c-3c = 1c, and realize at that point I have no solution. Therefore, no solution.
5c - "
6c - A 3c coin is valid here. I look at 6c-3c and see at 3c I used 1 coin. I store 1 + that value, or 2.
7c - No solution.
8c - No solution.
9c - Stores 3.
10c - No Solution
11c - The 11c coin works now. Look back at 11-11=0 and see a zero. Store 0+1 = 1.
12c - Now the 11c coin leads me back to 1c, so no solution. However, 3c leads me to 9c which required 3 coins. 3+1 = 4.
13c - The 13c coin works now for 1 coin. The 11c coin takes me to 2c, no solution. The 3c coin takes me to 10c, no solution.

... so on and so forth.


Whether intended or not, this is almost a form of dynamic programming. You are breaking each step into a increment of your denomination and previous solutions that you are forced into with that denomination. Your code could use some cleaning to help explain it better, or perhaps use something like a function stack to minimize the loop within a loop look, but in general... KUDOS

Steve

[Steven Smith]

One other thought from the drive home.

One limiting factor of your program is the need for at least as many iterations as the change. For 20c this isn't an issue, but if you were looking at 5263c... your speed starts to show.

One nice piece of logic you could add (or expand on) is that any time your total change exceeds the Least Common Multiple of your denominations, the best solution to reach the LCM (or any integer multiple of it) will be your largest denomination.

For example, if I have denominations of 2, 4, and 11 my LCM is 44. If I was trying to solve this problem for 250c, I could do integer division to get 250 / 44 = 5 and 5 * (44 / 11) = 20 coins to get to 220 optimally. Then you run your program for 30 (250 mod 44) and add that number of coins to 20. This could be a significant time saver in certain problems, or impractical depending on your likely values.

Steve