Original Post
Hi guys, nothing game realeted here, but still funny,
I am sitting here with a friend of mine discussing about a problem that is math-related: finding the best way of returning change to a customer.
(Can be game-related: monopoly: use as less bills as possible)
Problem:
coins of 1, 4 and 5 cents and you want to return 8 cents:
greedy algorithm: first 5 and then 1, 1, 1 (4), but best will do this: 4 and 4 (2).
I first though that a greedy algorithm would work when every coin is at least twice as big as it predecesor (5 < 4 * 2), but this doesn't work either:
coins: 1, 40, 100 (100 > 40 * 2, 40 > 1 * 2), returning 120:
greedy: 100, 20 * 1 (21)
best: 3 * 40 (3)
Even google couldn't help me on this, so maybe you can
EDIT: maybe is the same problem as order of storing textures in vid-mem?
[edited by - frankie68 on January 15, 2004 6:51:15 AM]