Sign in to follow this  

Your thought experiment for the day

This topic is 4781 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

The US currency system has 4 coins that are most commonly used, in denominations of 1 cent, 5 cents, 10 cents, and 25 cents. (Other denominations are also available but are much rarer in general circulation.) This set of denominations, {1, 5, 10, 25} has the interesting property that a particular amount of money can be expressed in a minimal total number of coins with this algorithm:
procedure make_change(amount)
    for each denomination d in decreasing order (25, 10, 5, 1)
        while(amount >= d)
            dispense coin of denomination d
            amount = amount - d
        end while
    end for
end


Consider other possible denomination sets. One such set is {1, 5, 7}. The algorithm above does _not_ produce the minimal number of coins for 10 cents: it favors 4 coins (1, 1, 1, 7) where only 2 (5, 5) are necessary. Your challenges, should you choose to accept them: 1. Is there an efficient algorithm (I.E. not NP-hard) to determine whether the above algorithm is suitable for a given set of denominations S? 2. Is there an efficient algorithm (I.E. not NP-hard) to determine correct change for any denomination and any amount?

Share this post


Link to post
Share on other sites
Being lazy and taking a stab at number 1 without thinking it through much, I'd say that as long as each coin amount is greater than or equal to twice the next largest one smaller than it, then the algorithm works. So, because 5 >= 1·2, 10 >= 5·2, and 25 >= 10·2, the set {1, 5, 10, 25} works this way.

That's probably wrong, but it's Friday. I don't wanna use my brain anymore, while still superficially looking like I am. [grin]

Share this post


Link to post
Share on other sites
If you're actually looking for the answers, I can point you to a paper that gives you your answers. If you're just trying to provoke discussion, then I'll probably have to sit this one out. :P

Share this post


Link to post
Share on other sites
Hmm... but consider the coin set {16, 5, 1}. Your rule holds, but the amount 20 is expressed by the algorithm as (1, 1, 1, 1, 16) instead of (5, 5, 5, 5).

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
If you're actually looking for the answers, I can point you to a paper that gives you your answers. If you're just trying to provoke discussion, then I'll probably have to sit this one out. :P
Just trying to provoke discussion. :-) I wasn't aware of the paper, though.... feel free to post it here when discussion dies down some.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
2. Is there an efficient algorithm (I.E. not NP-hard) to determine correct change for any denomination and any amount?

This can be done with dynamic programming.

Share this post


Link to post
Share on other sites
just blue-skying it here...

seems the original algorithm fails when there is a jump of less than 2x (5 to 7).

maybe define cost as "(n integer_div d) + (n modulo d)" and pick the lowest cost denomination for each step?

otherwise, if my 1st guess is right (the 2x thing), you may need some king of grouping. Start with the highest value, and group until you get a value of < 0.5*highest. Start over with the new value, etc.

Share this post


Link to post
Share on other sites
Dynamic programming solves the problem of finding the minimal number of coins in O(N*M) time and O(N+M) memory, where N is the number of different demoninations of coins and M is the number you wish to find change for. You can test this algorithm against the original algorithm for each M >= 0 until you find L consecutive numbers whose minimal coin set all have a coin of value L, where L is the largest coin denomination (though the proof that this will always happen is a little more complex). This will determine the correctness of the greedy algorithm in polynomial time.

Share this post


Link to post
Share on other sites
Quote:
Original post by hplus0603
The reason it works for US coins is that each coin evenly divides the coin above it, except for the topmost coin.
Does it? 10 does not divide 25 evenly.

Share this post


Link to post
Share on other sites
Quote:
Original post by lonesock
jseems the original algorithm fails when there is a jump of less than 2x (5 to 7).
Again, consider {16, 5, 1}.

Share this post


Link to post
Share on other sites
...Looks like an homework question, why a moderator can post such things and an user is strongly opposed ?
The door HAS to swing in both ways i think.

Share this post


Link to post
Share on other sites
Question 1:
We assume that each Member of the Set must be in the same progression. For instance {25, 10, 5, 1} all belong to the fiver progression.

Question 2:
We tried splitting the given set into several diffrent sets, eacht containing only elements from the same progression. That leads to better results, but is not the final solution.

Keep on thinking...

Share this post


Link to post
Share on other sites
Given only three denominations, A, B, C, with A > B > C, it is possible to beat the original algorithm if
ceil(A/B) * A - B > ((A % B) / C) + 1


That is very hard to phrase in plain english :/

Once there is more than 3 denominations, I think it is still correct if the above rule holds for each consecutive set of 3 denominations in the sequence.
edit: thinking about it, I am now sure that the struck out bit is wrong :)

My only worry in the above is if the lowest of the three is not exactly divisible into the left hand side of the equation, but then you can't even be sure that a given value can be exactly represented anyway. If there is a 1 present, you're OK.

All that is off the top of my head and could easily be wrong :).

In response to the other popular answer, though, not only does a jump of less than 2x sometimes fail and sometimes succeed, but a jump of more than 2x can do both aswell, I think :)

> 2x
{16, 5, 1} fails
{50, 20, 5} passes

< 2x
{3, 2, 1} passes
{7, 5, 1} fails

Incedently, the algorithm works for UK currency, for which the coins go:

1, 2, 5, 10, 20, 50, 100, 200

It would be nice if they went 1 2 4 8 16 32 64 wouldn't it? ;)

Share this post


Link to post
Share on other sites
Quote:

...Looks like an homework question, why a moderator can post such things and an user is strongly opposed ?
The door HAS to swing in both ways i think.
Hehe... it's been awhile since I had to take any math classes.

EDIT: not to mention, I already turned down SiCrane's generous offer of The Answer.

Share this post


Link to post
Share on other sites
Well looks, like discussion has died down, so ... *fanfare*

The Answer

(Mostly. Like all academic papers, it assumes you have access to all the sources it cites, so makes a few jumps in between that might be disorienting.)

Share this post


Link to post
Share on other sites
I'd just like to point out then, where the author of that paper says the problem is non-polynomial, he means that it is non-polynomial in the number of bits used to represent the input, NOT the value of the input itself. I.e., a problem that is linear in the size of the input is exponential in the number of bits in the input, and likewise a problem that is logarithmic in the input is linear in the number of bits in the input. In most practical cases, we will be solving this problem with numbers that can be represented in 32 bits, so mathematical operations (i.e. addition, copying, etc.) can be performed in constant time (and not in linear or worse time in the number of bits). For those who care, the dynamic programming solution I mentioned earlier works as follows:

vector<int> coins;
vector<int> fewestCoins(MAX+1, INF); // MAX is the largest number you want to solve for; each value of the array is initialized to infinity, i.e. some very large constant

fewest[0] = 0; // Base case

int i, j;

for(i = 0; i <= MAX; i++)
{
for(j = 0; j < coins.size(); j++)
{
if((i + coins[j] <= MAX) && (fewest[i] + 1 < fewest[i + coins[j]]))
fewest[i + coins[j]] = fewest[i] + 1;
}
}

// fewest[x] now contains the fewest number of coins needed to construct a value of x.
// Note that if the smallest coin value is not 1, then if x is not makeable, fewest[x] will still be INF.
// To actually determine the set of coins you need (not just the number of coins), you can create
// another array that stores the last coin you added, and you can solve it in O(fewest[x]) time and O(x) memory

Share this post


Link to post
Share on other sites
"To discuss solutions and algorithms for math and physics AS RELATED TO game development."

It is not enough to simply claim it is not a homework problem. I don't follow the rules very well but still I have to believe the answer is going to help someone, in some way, in their quest to be a game developer.

Share this post


Link to post
Share on other sites

This topic is 4781 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this