Least amount of change

[nitacku]

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]

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 All | Copy To Clipboard

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

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

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

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.