matching a currency amount to available denominations

[ChrisSte]

Hi,

I have a problem, for which I'm looking for an algorithm. Given a limited set of currency denominations (bills only, so they are integer numbers) and a currency amount (this would be bills only as well, so it's an integer). I need to figure out whether the currency amount passed in can be broken down into the available denominations. If it can't be broken down into the available denominations I need to find the nearest amount which is greater than the given amount which can be broken down into the given denominations.

Here's an example:
Denominations (20,50,100,500,1000)
-------------------------
currency amount in question: 80
answer: yes it can be broken down into the available denominations (20x4)
-------------------------
currency amount in question: 70
answer: yes it can be broken down into the available denominations (20+50)
-------------------------
currency amount in question: 75
answer: no not it can not be broken down into the available denominations, the next greater value which can is 80 (20x4).

Thanks for any help.

[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.

[ChrisSte]

Either you didn't understand my question (possibly because I was unclear), or I didn't understand your answer. Anybody want to help me out with this?

[bugzpodder]

it helps if you tell me what you don't understand. and i am pretty sure i understand the question clearly (even though i haven't read the whole thing -- but seriously i do understand it clearly :D) btw i've edited my original code so it looks better.

[Destined Soul]

Interesting problem. Took me a little bit to get right, but I believe that this works. :DPrivate Bills(1 To 5) As Long

Private Sub Form_Load()
Bills(1) = 2
Bills(2) = 5
Bills(3) = 10
Bills(4) = 20
Bills(5) = 50
End Sub

Private Function CanYouSplit(amount As Long) As Boolean

CanYouSplit = False

If amount = 0 Then CanYouSplit = True: Exit Function

Dim i As Integer
Dim originalAmount As Long

i = UBound(Bills)
originalAmount = amount

For i = UBound(Bills) To LBound(Bills) Step -1
If amount >= Bills(i) Then
If CanYouSplit(amount - Bills(i)) Then
CanYouSplit = True
Exit Function
End If
End If
Next i

End Function

Private Sub Command1_Click()

If Not CanYouSplit(CLng(txtVal)) Then
MsgBox "Unable to split " & txtVal
Else
MsgBox "You CAN split " & txtVal
End If

End SubUnless, of course, someone can find a logic flaw in this. (I haven't yet.)

[Edit]: Note that this code does NOT find the nearest match. I was too lazy to figure that out. :p

Destined

[bugzpodder]

it would work but i believe that the original question asks if you can't split it, you have to give the nearest amount. also, if the amount you are splitting is like: 1000000000 your program would be VERY slow, especially if you can't split it, you have to check that amount +/-1, 2, 3,... so on.

[Destined Soul]

Looking at it again, yes, it's probably a bit hard to determine the nearest (even if we only find smaller value that closest fits..)

Actually, I just noticed that this is only SLIGHTLY varying from bugz post about humble numbers (http://www.vbforums.com/showthread.php?s=&threadid=193463). In both problems, you have to find all combinations - in bugz post all of the time, in yours only when you know that it can't be split. Perhaps that might help you some more.

Note that after some testing, my algorithm is too SLOW for larger numbers if I was to use the currency: (20,50,100,500,1000) Oh well. :p

Destined

[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.

[ChrisSte]

Ok, here's what I don't understand in your pseudocode...

What does "change=get change;" mean?
How big an array of booleans are you creating?
What is n?
what is m?

I've figured out a brute force algorithm I can use which involves using the modulo operation. It goes something like this:

-Take the Modulo of the amount in question with each denomination (only for denominations that are less than the amount in question). If you find a 0 remainder the number in question can be broken down, otherwise take all your remainders and repeat the modulo operation on each denomination untill you find a 0 remainder or all your remainder are less than the lowest denomination.

I haven't quite figured out the 2nd part of my problem (figuring out the next best value).

[bugzpodder]

going to use ur example:

Here's an example:
Denominations (20,50,100,500,1000)
-------------------------
currency amount in question: 80
answer: yes it can be broken down into the available denominations (20x4)
-------------------------


m is the amount you want to break down (in your words currency amount in question, or in this case $80).

change are the denominations. so the first time through the loop, change=20, second time, change=50, 3rd time, change=100,4th time,change=500, 5th time, change=1000; next time, there is no more changes, so the loop quits.

the array size is tricky: it needs to be as large as the closest value. so the value you may want to make is 1, and all you have is $1000. so i suggest you make the array size the currency amount in question + largest change (denominations) in this case its 80+1000

sorry about the n, i didn't notice that. here is the new pseudocode:

arr[0]<-true;

loop from 0 to # of denominations {i}
change=denomination[i];
loop from 0 to Currency_Amount_in_Question-1 {j}
if arr[i]=true
set arr[i+change] <- true



remember that you can alter the program such that by declaring a bigger array and set the Currency_Amount_in_Question to really big, and now no matter how many time the user asks, you don't need to do the above code again. so if the user asks you to break down x dollars (currency amount in question)

you just check arr[x], if it is true, yes it can be broken down using denominations.

if its false, you simiply find a x' that is closest to the value of x such that arr[x'] is true and that number can be broken down.

now if you want to know exactly how to break it down, you can either keep track of it (pretty complex) or you can simiply use the brute-force algorithm you developed. any more questions?

[ChrisSte]

Ah, now I understand your solution. You're basically creating an array of all valid combinations (up to some point). Then checking the ammount in question against that array. That solution is going to be a bit memory hungry for my application. I guess the brute force method is going to be the easiest way to do this = (

Thanks

[bugzpodder]

its not that bad. a boolean array costs only 1 byte. so 100,000 of them takes around 1MB of memory. anyhow its much faster than your brute force, since especially if you can't make the amount in question using the available denominations, you have to check +1,-1 +2,-1, which would be very slow. my algorithm runs in less than 1 seconds in all cases, while your brute force search may take as long as 15-60 seconds when the the amount in question is really large. if it is small, my algorithm only takes a few kilobytes of memory at most but hey its your choice.

[jim mcnamara]

Here's a thought:

You do not have to try a brute force deal with all denominations.
Remove higher denominations that are factored by the lower ones.
You are not finding how to make exact change with the fewest number of bills,
only if it is possible. Or not.

{20,50,100,500,1000} becomes {20,50}

first test if the amount is an even multiple of either one
Let's Call {20,50} D()

function can_do(ByRef amt as integer) as Boolean
Dim d(2) as integer
d(1)=20
d(2)=50
For i=1 to ubound(d) ' modulo check
if amt mod d(i)=0 then
can_do=True
Exit Function
end if
next i
tmp = amt mod d(2)
if tmp < d(1) and d(1) mod tmp <> 0 then ' we cannot give change
can_do = False
end if

End Function

Use the brute force method [on 2 element D() array] to get the closest value you can get.
Set amt to that value, so you can print it on return.

[bugzpodder]

thats a great idea especially if you are only dealing with denominations that he mentioned!

[ChrisSte]

I'm trying to find the generic solution for any (limited size) set of denominations and any given amount (could be very large). The bugz method is memory intensive for large amounts (my application can deal with amounts in the millions and hundreds of millions) plus it still requires a fixed n*m execution time.

I've found a faster and non memory intensive solution by using modulo operations, starting with the lowest denomination and working your way up, recursively calling the modulo operation again on any remainders untill you find a 0 remainder or all remainders are less than the lowest denomination. I'll post the code when I figure out the 2nd half of my question.

Jim's idea may help me bail out earlier than I currently do for the case where the amount cannot be broken down. Thanks.

[bugzpodder]

you see, the problem with your method is, it is only good for checking one value. if the next greater value is like $5000 away, then you'd have being through 5000 of these. however, the next greater value is always less than n away from the asked value, where n is the smallest denomination. so i don't see a problem. simiply do a loop from the asked amount to asked amount + smallest denomination-1 and do your modulus method. if you hit the bulleye early then your method would be fast but if it doesn't then you are in trouble. u can also use my method provided that the asked amount is less than <10 million. thats about 10MB of memory.

[ChrisSte]

I still haven't found a generic algorithm for any set of denominations and any passed in amount.

I have an algorithm which does the following:
-Get the smallest set of denominations by factoring out any uneeded denominations. So (20,50,100,200) becomes (20,50) and (2,7,9,10,14) becomes (2,7,9).

-Take the modulus of the passed in amount with each denomination. Repeat this recursively on the remainders untill you find a 0 remainder. If the remainder is smaller than the smallest denomination, then it's considered a fail case.

This works for most cases, but not all:
Given the set (20,50) and the passed in amount 170 I do:

-170%20 - remainder = 10 - fail
--10%20 - fail amt smaller than smallest denomination
--10%50 - fail amt smaller than smallest denomination
-170%50 - remainder = 20 - fail
--20%20 - remainder = 0 - Success! exit

However take the same set for the amount 130:

-130%20 - remainder = 10 - fail
--10%20 - fail amt smaller than smallest denomination
--10%50 - fail amt smaller than smallest denomination
-130%50 - remainder = 30 - fail
--30%20 - remainder = 10 - fail
---10%20 - fail amt smaller than smallest denomination
---10%50 - fail amt smaller than smallest denomination
--10%50 - fail amt smaller than smallest denomination

However, I can build this amount with the given denominations (50+20+20+20+20), so I'm missing something here.

Anyone else able to figure this out? I can't just use a Greatest Common Denominator of the denominations because the GCD of (20,50) is 10 and 30 is not a valid amount... one thing I noticed is anything 40 and above and divisible by the GCD is a valid amount. I'm wondering if I can use this knowledge somehow?

Of course I still have the next part of my question, but I believe that can be easily gained once I have the knoledge of how to do the first part.

Thanks for any help.

[bugzpodder]

you take the reminder, assuming that you give it all you got for that currency.

so for example, 130%50=30, by doing this, you have determined
100, which is made by two not one 50 bills, and of course as your answer shows, only one 50 bill can produce a correct answer.

[ChrisSte]

huh?

I don't understand what you're trying to say.

[bugzpodder]

you can't use two 50s to make 130. only can use 50+20+20+20+20

130 mod 50 implies you use two 50s, because 130-2*50=30

[ChrisSte]

I having trouble figuring out what point are you trying to make.

I'm trying to find out if 130 can be made with the given denominations. You're saying use the anwer to disprove something? I don't have the answer yet! That's what I need to get.

[bugzpodder]

i am telling you whats wrong with your method. as for how to solve your problem, I have already provided a solution with cost of O(N) run time and a storage of N.

[ChrisSte]

Yeah, I know whats wrong with my method, that's why I'm posting asking for help.

As I've said, the method you've posted is unacceptable for my application. It's also the least elegant solution I can think of. You're basically creating a database of every possible input value and the result for those values. It's a silly solution given that input value can be arbitrarily large and the denominations could change or there might be multiple tables of denominations. I don't want a method who's min execution time and memory usage is 100% dependant on an input value, that's just bad programming.

I'm looking for an elegant algorithm to solve the problem. I know I'm close with the one one I've outlined. And the execution time and memory usage is a tiny fraction of the method you've outlined.

Lets look at a denomination set of (20,50) and an input value of 10,001

My max execution time:
6 x (small chunk of work)
My memory usage
6 x a few variables

Your min execution time:
10,001 x (small chunk of work)
Your memory usage
10,001 unit boolean array

If you want to help me with my problem, forget about your solution and start thinking about something more generic and more elegant. I know the method I've outlined just needs a few tweaks to be there. Forget that this is about money at all. Think of it as a generic problem for any set of numbers and any input value.

[bugzpodder]

no problem you don't have to use my method. btw i think your method is ridculously slow, given your requirements and such (find the nearest denomination). not to mention it is wrong! you realize that your "elegant" solution is useless because it produces the wrong answer? btw i don't need a lecture on how to program, since i am not the one whos asking for help. if you are asking for help don't ever give a lecture or no one (at least i wouldn't) help you. if you are full of urself then don't come here and ask for help.

for a solution thats like yours (but working), you could try a recursive solution which checks all possible combinations of a currency. as i said my original method is the only non-time consuming method. but if you are really keen on the memory usage, then u can use this.

here is the code to it.

say i want to know if i can make x dollars:

you are smart enough to translate my C++ code into VB or whatever language u may be using.

int excess=OriginalAmount;
int denom_count[n_denom];

void breakdown(){
//I'll leave this to yourself.
//If you can't even do this little method then you are
//unfit to do what you are doing.
}


bool BetterMethod (int x){
bool state=false;
if (x==0) return true;
else if (x<0) {
if (-1*x<excess)
excess=-1*x;
return false;
}
for (int i=0;i<n_denom;i++){
state=BetterMethod (x-denom[i]);
if (state==true)
denom_cnt[i]++;
break; //quit the for loop
}

if (state==true)
return true;
else teturn false;
}

if (BetterMethod(OriginalAmount)==true)
cout<<"It can be broken down into"<<breakdown()<<endl;
else
cout<<"No can't be broken down, the next biggest value that can be would be "<<OriginalAmount+excess<<" which can be broken down into "<<breakdown()<<endl;