Archived

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

Change returning algorithm

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

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 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 on other sites
#include <limits.h>#include <iostream.h>#define ARRAY_SIZE  200#define NUM_OF_COINS   3int 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]

1. 1
Rutin
29
2. 2
3. 3
4. 4
5. 5

• 13
• 13
• 11
• 10
• 14
• Forum Statistics

• Total Topics
632961
• Total Posts
3009485
• Who's Online (See full list)

There are no registered users currently online

×