• Advertisement

Archived

This topic is now archived and is closed to further replies.

Change returning algorithm

This topic is 5210 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

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]

Share this post


Link to post
Share on other sites
Advertisement
This is a dynamic programming problem, which is a way to construct algorithms, google for dynamic programing. I know that I got a algorithm for this somewhere, if you like i can look it up.

LizardCPP

Share this post


Link to post
Share on other sites

#include <limits.h>
#include <iostream.h>

#define ARRAY_SIZE 200
#define NUM_OF_COINS 3

int g_iCoinVal[] = {1, 4, 5};
int g_iDynMemory[ARRAY_SIZE];

bool CoinExists(int iValue) {
int iCounter;

for(iCounter = 0; iCounter < NUM_OF_COINS; iCounter++) {
if(g_iCoinVal[iCounter] == iValue) {
return true;
}
}

return false;
}

void DoAlg() {
int iCounter, iCounter2;

for(iCounter = 1; iCounter < ARRAY_SIZE; iCounter++) {
if(CoinExists(iCounter)) {
g_iDynMemory[iCounter] = 1;
} else {
// you only need to know the last coin, that is the coin for which the

// rest of the amount can be returned in a minimum amount of coins

int iMin = INT_MAX;

for(iCounter2 = 0; iCounter2 < NUM_OF_COINS; iCounter2++) {
if(iCounter - g_iCoinVal[iCounter2] > 0) {
if(g_iDynMemory[iCounter - g_iCoinVal[iCounter2]] < iMin) {
iMin = g_iDynMemory[iCounter - g_iCoinVal[iCounter2]] + 1;
}
} else {
break;
}
}
g_iDynMemory[iCounter] = iMin;

}
cout << iCounter << ": " << g_iDynMemory[iCounter] << endl;
}
}

int main(int argc, char* argv[])
{
DoAlg();
return 0;
}


You are right, this is the solution (don't you just love it when you have got a few minutes spare and a friend with the same problem )


[edited by - frankie68 on January 15, 2004 7:32:55 AM]

Share this post


Link to post
Share on other sites

  • Advertisement