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

ruler501 · « **Reply #15 on:** June 26, 2012, 02:18:36 am »

or you bring 3/4 that will reduce what you get back

nitacku · « **Reply #16 on:** June 26, 2012, 02:24:27 am »

For the sake of argument, lets suppose you carried with you the exact change you needed:

Carrying 4 coins means you will have 0.7 coins too little.
Carrying 5 coins means you will have 0.3 coins too much.

Since you're trying to minimize both sides, the smallest value is the one to select.

Builderboy · « **Reply #17 on:** June 26, 2012, 02:26:13 am »

How can you be carrying exact change and still not have enough or have to much?

And the simple math boils down to the fact that you cannot have an average less than 4.7 coins by carrying 5 coins.

Wretchedlout · « **Reply #18 on:** June 26, 2012, 02:29:03 am »

The answer is 9 coins, assuming the object being bought is 1-99 cents
That is because the thing requiring the most amount of coins is 94 cents which is done with the least ammount of coins which is 3Q 1D 1N 4P
Or 9 coins.

Builderboy · « **Reply #19 on:** June 26, 2012, 02:30:04 am »

Quote from: Wretchedlout on June 26, 2012, 02:29:03 am

The answer is 9 coins, assuming the object being bought is 1-99 cents
That is because the thing requiring the most amount of coins is 94 cents which is done with the least ammount of coins which is 3Q 1D 1N 4P
Or 9 coins.

Erm, you might want to re-read the original post, as you answered a different least-change question

nitacku · « **Reply #20 on:** June 26, 2012, 02:30:17 am »

Ah, you're correct. It isn't exact change, but an exact subset of the change needed. In some cases it will be exact, in others too much or too little.

EDIT:
The question is: How do you carry 4.7 coins?
You can't. But you can carry 5 coins. And carrying 4 coins means more often than not you wont have enough.
Knowing this, simply choosing the most probably occurring coins will yield the best result.

Builderboy · « **Reply #21 on:** June 26, 2012, 02:31:35 am »

So we do know that the answer is less than 5 coins, but whether that answer is not zero is yet to be determined. It gets a bit more complex since you can give the cashier any combination of coins to help minimize the change you get back.

Wretchedlout · « **Reply #22 on:** June 26, 2012, 02:35:33 am »

What are the 5 coins?

nitacku · « **Reply #23 on:** June 26, 2012, 02:38:07 am »

Well based on the probability of receiving a particular coin: 4 pennies and 1 quarter.

You wouldn't choose 5 pennies since that would be less efficient (aka nickel)
The quarter being the next most probable coin is then selected.

EDIT: I think I follow what you're saying now Builderboy.
You can't choose more than 4.7 coins since that is the average received.
Choosing more would be a less-than-optimal solution than just carrying none.

The solution may be more difficult than this, but right now I think 4 pennies is the optimal solution.

Wretchedlout · « **Reply #24 on:** June 26, 2012, 02:59:44 am »

So I brute forced some numbers:
For each amount of cents (1-99) I use the least amount of change for each
Like if the cent value was 21 I would have 2dimes and a penny...etc
So if you add up all the times each coin was used
Quarter 150 times
Dime 80 times
Nickel 40 times
Penny 2832 times
%
4.84
2.58
1.29
91.30

Yup I think 4 pennies

Builderboy · « **Reply #25 on:** June 26, 2012, 10:08:24 am »

Erm I think your value for pennies is off. There are only 100 different cases, and you will only be getting back at maximum 4 pennies per transaction. So that is a *maximum* of 400, much lower than 2832. The actual number of pennies is actually half of 400 though, since on average, you get back 2 pennies per transaction.

thepenguin77 · « **Reply #26 on:** June 26, 2012, 12:52:57 pm »

Well, I wrote a program to do it. This program stepped through all of the possible store-enter values and made the least amount of change for them to enter the store with (So 21 is penny, dime, dime) Then, it took each of those coin sets, and bought all the items from [0-99] cents and kept track of what was returned. Here are the results from this:

Spoiler For Spoiler:

enter value
   enter+leave
   enter
   leave
0 4.7 0 4.7
1 5.7 1 4.7
2 6.7 2 4.7
3 7.7 3 4.7
4 8.7 4 4.7
5 5.7 1 4.7
6 6.7 2 4.7
7 7.7 3 4.7
8 8.7 4 4.7
9 9.7 5 4.7
10 5.7 1 4.7
11 6.7 2 4.7
12 7.7 3 4.7
13 8.7 4 4.7
14 9.7 5 4.7
15 6.7 2 4.7
16 7.7 3 4.7
17 8.7 4 4.7
18 9.7 5 4.7
19 11 6 4.7
20 6.7 2 4.7
21 7.7 3 4.7
22 8.7 4 4.7
23 9.7 5 4.7
24 11 6 4.7
25 5.7 1 4.7
26 6.7 2 4.7
27 7.7 3 4.7
28 8.7 4 4.7
29 9.7 5 4.7
30 6.7 2 4.7
31 7.7 3 4.7
32 8.7 4 4.7
33 9.7 5 4.7
34 11 6 4.7
35 6.7 2 4.7
36 7.7 3 4.7
37 8.7 4 4.7
38 9.7 5 4.7
39 11 6 4.7
40 7.7 3 4.7
41 8.7 4 4.7
42 9.7 5 4.7
43 11 6 4.7
44 12 7 4.7
45 7.7 3 4.7
46 8.7 4 4.7
47 9.7 5 4.7
48 11 6 4.7
49 12 7 4.7
50 6.7 2 4.7
51 7.7 3 4.7
52 8.7 4 4.7
53 9.7 5 4.7
54 11 6 4.7
55 7.7 3 4.7
56 8.7 4 4.7
57 9.7 5 4.7
58 11 6 4.7
59 12 7 4.7
60 7.7 3 4.7
61 8.7 4 4.7
62 9.7 5 4.7
63 11 6 4.7
64 12 7 4.7
65 8.7 4 4.7
66 9.7 5 4.7
67 11 6 4.7
68 12 7 4.7
69 13 8 4.7
70 8.7 4 4.7
71 9.7 5 4.7
72 11 6 4.7
73 12 7 4.7
74 13 8 4.7
75 7.7 3 4.7
76 8.7 4 4.7
77 9.7 5 4.7
78 11 6 4.7
79 12 7 4.7
80 8.7 4 4.7
81 9.7 5 4.7
82 11 6 4.7
83 12 7 4.7
84 13 8 4.7
85 8.7 4 4.7
86 9.7 5 4.7
87 11 6 4.7
88 12 7 4.7
89 13 8 4.7
90 9.7 5 4.7
91 11 6 4.7
92 12 7 4.7
93 13 8 4.7
94 14 9 4.7
95 9.7 5 4.7
96 11 6 4.7
97 12 7 4.7
98 13 8 4.7
99 14 9 4.7

So, as you can see, you will always leave with on average 4.7 coins meaning that taking in anything is just a waste.

The method I used for purchases was to pay with the least valued coins first. This means use all the pennies, then all the nickels, dimes, quarters, and finally, break out a dollar if need be. This method should maximize the change you give away because the reverse operation (starting big and going to small) minimizes the change you pay. Apparently using this strategy, you'll always end up with the same net coins.

Finally, my program didn't check the non-standard coin sets (like 3 dimes) but, since these all return with 4.7, I assume they will not break the trend.

someone · « **Reply #27 on:** June 26, 2012, 03:42:59 pm »

Quote from: thepenguin77 on June 25, 2012, 11:49:00 pm

what coins should you enter a store with so that sum of the number of coins you enter a store and leave a store with is at a minimum?

The general idea here is that you basically want to carry the least amount of change. So, the way this works, is you pick E number of coins to enter with, after buying your items (which have random number of cents) you leave with L number of coins. You want to minimize L + E.

Rules:
We're using American coins, so the choices are: penny - .01, nickel - .05, dime - .10, quarter - .25 (no half dollars, too rare )
The number of cents your purchase costs is random (So, a purchase would cost some dollar amount + [0 - 99] cents)
You receive the minimum number of coins from the cashier ($.90 is not 9 dimes)

Have at it. You'll of course have to provide some sort of justification for your answer.

I'm not sure I get the question right or not (and all the rules).

Are you asking which coins you should bring for any situation? (in which the cost of the purchase varies from 0 to 99 cents, excluding round numbers which you can therefore use bills). If so, then you would you be able to use dollars. Because it would be useful to use them when the price is between 51¢ & 99¢, because then you would only need to calculate from 0¢ to 50¢, because the other part is just the complement (e.g. 66¢ = $1 - 34¢, so you calculate over 34¢ & not the 66¢).

I was bored, so I was playing around with an Excel sheet & count that at most you would need for all & any case the following coins:
3 pennies
1 nickel
2 dimes
2 quarters

However, if the question is just which is the worst of the cases, then you'll need to bring 5 coins at most, but it varies depending on the case...

Spoiler For Spoiler:

nitacku · « **Reply #28 on:** June 26, 2012, 08:50:53 pm »

I wrote a C program to brute force the result since I'm lazy

Code: [Select]

#include <stdio.h> 
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include "SFMT.c"

typedef struct ChangeStruct
{
	int penny;
	int nickel;
	int dime;
	int quarter;
} Change;

Change min_change(int value);

int main()
{
	Change carry;
	Change purchase;
	Change exchange;
	Change best_change;
	int transactions = 10000000;
	double best_result = 5;
	double average;

	int penny = 4;
		
	for (; penny >= 0; penny--)
	{
		int nickel = 1;
		
		for (; nickel >= 0; nickel--)
		{
			int dime = 2;
			
			for (; dime >= 0; dime--)
			{
				int quarter = 3;
				
				for (; quarter >= 0; quarter --)
				{
					int total_coins = 0;
					int x = 0;
				
					carry.penny = penny;
					carry.nickel = nickel;
					carry.dime = dime;
					carry.quarter = quarter;
					
					init_gen_rand(time(NULL));
				
					for (; x<transactions; x++)
					{
					
						purchase = min_change(gen_rand32()%100);
					
						exchange.penny = abs(purchase.penny - carry.penny);
						exchange.nickel = abs(purchase.nickel - carry.nickel);
						exchange.dime = abs(purchase.dime - carry.dime);
						exchange.quarter = abs(purchase.quarter - carry.quarter);
						
						total_coins += exchange.penny + exchange.nickel + exchange.dime + exchange.quarter;
					}
					
					average = (double)total_coins/transactions;
					
					printf("Pennies: %d Nickels: %d Dimes: %d Quarters: %d\n", penny, nickel, dime, quarter);
					printf("Average coins per transaction: %f\n\n", average);
					
					if (average < best_result)
					{
						best_result = average;
						best_change = carry;
					}
				}
			}
		}
	}
	
	printf("Best Result: %f\n", best_result);
	printf("Pennies: %d Nickels: %d Dimes: %d Quarters: %d\n", best_change.penny, best_change.nickel, best_change.dime, best_change.quarter);
	
	return 0;
}

Change min_change(int value)
{
	Change min_change;
	
	min_change.penny = 0;
	min_change.nickel = 0;
	min_change.dime = 0;
	min_change.quarter = 0;
	
	while (value)
	{
		if (value >= 25)
		{
			value -= 25;
			min_change.quarter++;
		}
		else
		{
			if (value >= 10)
			{
				value -= 10;
				min_change.dime++;
			}
			else
			{
				if (value >=5)
				{
					value -= 5;
					min_change.nickel++;
				}
				else
				{
					value -= 1;
					min_change.penny++;
				}
			}
		}
	}
	
	return min_change;
}

If you want to compile it you will also need the SIMD-oriented Fast Mersenne Twister library: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/

So the results the program generated:
Best Result: 3.198689
Pennies: 2 Nickels: 0 Dimes: 1 Quarters: 1

It's averaged over 10,000,000 transactions per combination.
Should be enough for statistical evidence.

EDIT: Best Result is the average number of coins leftover.
EDIT2: I should probably clarify, this isn't quite the answer the problem is looking for, but it is the answer to "What change should I carry to minimize my change received". But now that I think about it, even this isn't quite an answer, simply because 37 cents isn't enough to cover 38 cents, which means you'd have to pull out a $1 for that 1 cent which then makes your dollar 99 cents. This answer is merely the best combination of coins that matches average transactions the most.

ruler501 · « **Reply #29 on:** June 26, 2012, 09:06:10 pm »

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

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

ruler501

Re: Least amount of change

nitacku

Re: Least amount of change

Builderboy

Re: Least amount of change

Wretchedlout

Re: Least amount of change

Builderboy

Re: Least amount of change

nitacku

Re: Least amount of change

Builderboy

Re: Least amount of change

Wretchedlout

Re: Least amount of change

nitacku

Re: Least amount of change

Wretchedlout

Re: Least amount of change

Builderboy

Re: Least amount of change

thepenguin77

Re: Least amount of change

someone

Re: Least amount of change

nitacku

Re: Least amount of change

ruler501

Re: Least amount of change