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

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

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

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? ;)

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.

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

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: