Author Topic: Least amount of change (Read 14837 times)

nitacku · « **Reply #30 on:** June 26, 2012, 09:13:20 pm »

Quote from: ruler501 on June 26, 2012, 09:06:10 pm

nitacku you need to reduce the amount entered and left with put together

I think the solution in that case is to bring nothing.

The reason: There is never 100% probability that you eliminate what you brought. Even if it was 100% probable that you would use what you brought, it would simply cancel itself. For example: If you bring one penny, 80% of the time it is used. This means that your average number of coins is 1 + (4.7 - 0.8). You see? 1 - 0.8 > 0, which means bringing anything defeats the purpose.

ruler501 · « **Reply #31 on:** June 26, 2012, 10:12:01 pm »

I brute forced it too to see if that might show something other then the bring nothing

heres the code it runs with the standard C lib

Code: [Select]

#include <stdio.h>

typedef struct ChangeStruct
{
	int pennies;
	int nickels;
	int dimes;
	int quarters;
	int amount;
} Change;

Change calculateChange(int amount)
{
	int tempamount = amount;
	Change result = {0,0,0,0,amount};
	if (tempamount >= 25) 
	{
		result.quarters = amount / 25;
		tempamount -= result.quarters * 25;
	}
	if (tempamount >= 10)
	{
		result.dimes = tempamount / 10;
		tempamount -= result.dimes * 10;
	}
	if (tempamount >= 5)
	{
		result.nickels = 1;
		tempamount -= 5;
	}
	if (tempamount > 0)
	{
		result.pennies = tempamount;
	}
	return result;
}

int countCoins(Change counted)
{
	int total;
	total = counted.pennies + counted.nickels + counted.dimes + counted.quarters;
	return total;
}

Change subtractChange(Change first, int second)
{
	if (first.amount > second) return calculateChange(first.amount - second);
	else return calculateChange(second - first.amount);
}

void printCoins(Change printNeeded)
{
	printf("%d pennies\n%d nickels\n%d dimes\n%d quarters\n", printNeeded.pennies, printNeeded.nickels, printNeeded.dimes, printNeeded.quarters);
}

int main()
{
	int smallestTotal, smallestE, currentE, smallestL, currentL, total;
	Change smallestCoins, currentCoins, subtractCoins, returnCoins;
	double smallestAverage=100.0, currentAverage;
	for ( int i=0; i<100; i++)
	{
		total = 0;
		currentCoins = calculateChange(i);
		currentE = countCoins(currentCoins);
		for ( int j=0; j<100; j++)
		{
			currentL = countCoins(subtractChange(currentCoins, j));
			total += currentL + currentE;
		}
		currentAverage = total / 100.0;
		if (currentAverage < smallestAverage)
		{
			smallestAverage = currentAverage;
			smallestTotal = currentL + currentE;
			smallestE = currentE;
			smallestCoins = currentCoins;
		}
	}
	printCoins(smallestCoins);
	printf("With average %f\n", smallestAverage);
	printf("Entered with %d coins\n", smallestE);
}

and the result was
0 pennies
0 nickels
0 dimes
0 quarters
With average 4.700000
Entered with 0 coins

This seems wrong to me so please help me find if there is an error in my code

EDIT: I fixed it so that 0 coins was an option

thepenguin77 · « **Reply #32 on:** June 27, 2012, 07:30:22 pm »

Well, it looks like runer had it right from the start. Carrying 0 coins really is the best option.

Quote from: Runer112 on June 26, 2012, 12:38:10 am

I believe the solution is to carry no change.

Whatever the cost of your purchase is and whatever coins you have, you can ensure you leave with the minimum amount of change possible by giving the vendor all of your change. Whatever coins properly contribute to the payment, the vendor will keep; the coins that do not will be returned to you. Since the cents amount of the purchase is an equally-distributed random number, subtracting your constant amount of change from this will result in another equally-distributed random number (mod 100). Whatever amount of change you contribute, the vendor will always have to return to you coins that sum to an equally-distributed random amount of cents from 0-99.

You cannot limit the amount of coins you end with, so the optimal solution is simply to limit the amount of coins you begin with.

And with 2 brute force checks to back this, I'm happy. It looks like I've been doing it right all along. (Nitaku said his results were wrong and I think "someone" solved the wrong problem.

Author Topic: Least amount of change (Read 14837 times)

nitacku

Re: Least amount of change

ruler501

Re: Least amount of change

thepenguin77

Re: Least amount of change