Problem with making cash change

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)?

Answer 1

[DGM]

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]

ans = 1×4

2 0 1 1

conto % approximately five cents left

conto = 0.0500

fprintf('%.30f',conto) % but not exactly

0.050000000000000072164496600635

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.

https://www.mathworks.com/matlabcentral/answers/57444-faq-why-is-0-3-0-2-0-1-not-equal-to-zero

[Lorenz]

Thank you for the help! I solved the problem by implementig what you did at the end for the while loop, and also not using the variable conto, but conto*100, thus removing the floating point altoghether!

Answer 2

[John D'Errico]

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)

ans = 4×1

0 2 1 1

coinSolver(143)

ans = 4×1

1 1 0 14

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?

[John D'Errico]

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?