matching a currency amount to available denominations

[bugzpodder]

Originally posted by bugzpodder
here is how u do it in psedocode:

in order to break m down:

declare boolean array arr[] and initialize each element to false

arr[0]<-true;

while (there is still change)
   change=get change;
   loop from 0 to n {i}
      if arr[i]=true
           set arr[i+change] <- true

now if arr[m] is true then you got your change. if not, check arr[m-1], arr[m+1], arr[m-2], arr[m+2] until you get something.

lol Destined this is the way to do it! guarentees 0.05 second run time (unless you want to make something crazy like 100000000000000 dollars). as long as your memory can hold that much boolean variables my method will work. i have already give you the code, Chris, the only thing i can do now is to answer any questions if you have any.