Archived

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

Frankie68

Change returning algorithm

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