Problem with making cash change
3 views (last 30 days)
Show older comments
I'm trying to write a matlab script, and in part of it, after being given a certain amount of euros, it would give me the output of the minimum number of coins it takes to make that amount of change. The possible coins are 0.1€, 0.2€,0.5€,1€. I created a while loop that, up until the last 0.1 euros, looks like it works, but after that, the pllot just gets stuck and neither gives me an output, neither an error.
while conto>0
if conto >= 1
conto = conto - 1;
euro = euro + 1;
elseif conto >= 0.5
conto = conto - 0.5;
half = half + 1;
elseif conto >= 0.2
conto = conto - 0.2;
tw = tw + 1;
elseif conto > 0.1
conto = conto - 0.1;
sm = sm +1;
end
end
What do I have to change for it to not "stop" anymore, and actually give me a result (or an error)?
0 Comments
Accepted Answer
DGM
on 26 May 2023
Edited: DGM
on 26 May 2023
I see two problems:
First, there's no provision for amounts which are not integer-divisible by 0.1. I don't know if that's customarily a thing, but let's assume it is. You can just add a catch-all else case at the end to make sure the loop exits.
conto = 2.35;
euro = 0;
half = 0;
tw = 0;
sm = 0;
while conto>0
if conto > (1 - eps)
conto = conto - 1;
euro = euro + 1;
elseif conto > (0.5 - eps)
conto = conto - 0.5;
half = half + 1;
elseif conto > (0.2 - eps)
conto = conto - 0.2;
tw = tw + 1;
elseif conto > (0.1 - eps)
conto = conto - 0.1;
sm = sm + 1;
else
% might remainder be nominally nonzero?
break;
end
end
[euro half tw sm]
conto % approximately five cents left
fprintf('%.30f',conto) % but not exactly
The bigger problem is that these successive subtractions are going to run into problems of the limited precision of floating-point numbers. So you're going to have to have a little extra wiggle room on those thresholds.
More Answers (1)
John D'Errico
on 26 May 2023
Edited: John D'Errico
on 26 May 2023
Now that you have an answer, I'll add one that is not solved the way you would do so, but using an ILP solver, so an Integer Linear Programming solver. I would just call intlinprog. So given a total amount, using INTEGER amounts. Multiply EVERYTHING by 10. That makes this an entirely integer problem, and you no longer need to worry about floating point arithmetic. So now we will have coins in the amounts {1,2,5,10}.
Next, I would write a function to return the solution. I show that below.
coinSolver(19)
coinSolver(143)
In each case, it returns the fewest number of coins needed to make up the desired total. There may be multiple solutions for some totals. One of them will be selected if that is the case.
function coinAmounts = coinSolver(total)
% Returns the minimum set of coins needed to make change for any total
% Assumes the coins have denominations of {1,2,5,10}
f = [1 1 1 1]; % we want to minimize the total number of coins needed to make change
Aeq = [1 2 5 10]; % the sum of all coins, mutiplied by their multiplicity must be total
beq = total;
intcon = [1 2 3 4]; % cannot have a fractional number of coins
lb = [0 0 0 0]; % cannot have a negative number of coins
ub = [];
A = []; % No linear inequality constraints
b = [];
opts = optimoptions('intlinprog');
opts.Display = 'none';
coinAmounts = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,opts);
end
So that is how I would solve the problem. I would use an existing tool that is designed to solve that class of problem.
Finally, an interesting question is how to solve the problem if you wanted to know ALL possible ways to break a total amount down to give change. For this, I would use my partitions function (it resides on the File Exchange, for free download), because really this becomes a problem of finding all integer partitions of the total amount, but restricted to the given set of coin amounts.
P143 = partitions(143,[1 2 5 10])
partitions(143,[1 2 5 10])
ans =
143 0 0 0
141 1 0 0
139 2 0 0
137 3 0 0
135 4 0 0
133 5 0 0
...
0 4 1 13
3 0 2 13
1 1 2 13
3 0 0 14
1 1 0 14
The first solution is to just return 143 of the smallest coin.
I've cut out the ones listed in the middle, because there are MANY ways to solve the problem for this number. 5840 of them in fact.
size(P143)
ans =
5840 4
Or how to know if there are multiple solutions, each of which is minimal. This latter question is an interesting one, because. For example, could one prove the minimal solution is unique? Under which circumstances would that be true?
1 Comment
John D'Errico
on 26 May 2023
An interesting variation on this problem...
Consider some set of "coin" denominations, all of which are presumed to be integer. As well, choose some integer amount for which to make change. For example, given a total amount of 71. we want to write 71 as a sum of members of the set: {3, 4, 6, 10, 14, 16, 20}. We can have replicates in that sum. It turns out that we can decompose
71 = 3 + 3*16 + 20 = 3 + 2*10 + 2*20
In both decompositions, there are exactly 5 coins that will be required, and there are no other decompositions of 71 in only 4 or fewer coins of those denominations. Define that as the minimal partition.
You should see however, that the minimal partition was not unique.
Can you find a sufficient condition on the coin denominations such that the minimal partition will always be unique?
See Also
Categories
Find more on Particle Swarm in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!