2
$\begingroup$

I am new to Matlab (& also to stackexchange) and I need to learn it for a dynamic Macro class.

I have trouble using a while loop in a function. The function is supposed to calculate the amount of coins one needs to pay price p. My function, however, just provides a vector displaying which coins I need and not how much of which. I hope, someone jumps in and helps me out of my trouble. Here is my code:

function[c] = achange(p,coins)
s=size(coins);  
c=zeros(1,s(2)); 

while p>0
    for i=1:s(2) 
    if coins(i) <= p 
        p=p-coins(i); 
        c(i)=c(i)+1; 
    end
    end
end 
end
$\endgroup$
12
  • $\begingroup$ Okay, well you should know that the economics stackexchange is for economics questions, not Matlab questions. $\endgroup$
    – user253751
    Nov 18 '20 at 19:19
  • $\begingroup$ @user253751 no actually our help center explicitly states: "Software questions: Questions related to software used in economics and econometrics, are on-topic here." See here. So this question is totally on topic because it is application of matlab to some econ question. Matlab is used in economics quite a lot for numerical modeling - I dont recognize the type of the problem above since it is not connected to anything I specialize in but it looks like an Econ problem $\endgroup$
    – 1muflon1
    Nov 18 '20 at 19:25
  • 2
    $\begingroup$ Your function seems to be okay. Suppose that the good costs 60 cents, and you have the following vector of coins $(1,2,5,10,20)$, then the function returns $(4,3,2,2,1)$ telling you that you need 4 one cent coins, 3 two cents coins etc., adding up to 60 cents, which is the price of the good. $\endgroup$ Nov 18 '20 at 20:48
  • $\begingroup$ @BrianRomanchuk that is correct, it works only with integers. But this is a refinement that we should let to the author. $\endgroup$ Nov 18 '20 at 20:58
  • 1
    $\begingroup$ The algorithm doesn’t diagnose an inability to get the requested amount, and can miss the correct solution. Let’s say we have p=50 and c=[25, 10]. It will return c=[1,2] to add up to 45, and not [2,0] which gives 50. $\endgroup$ Nov 18 '20 at 21:01
2
$\begingroup$

I thought a little bit about the problem, and I came up with the following quick hack, that seems to work.

Here is the piece of code that should do the job in principle with integers:

function  [exch]=achange(p,coins)
s=size(coins);
c=zeros(1,s(2));
coins=sort(coins,'descend');
it=1:s(2);
isaninteger = @(x)isfinite(x) & x==floor(x);
if p<coins(end)
   return
end
if isaninteger(p)==0
   exch.coins=coins;
   exch.c=inf(1,s(2));
   exch.rest=inf;
   return
elseif any(isaninteger(coins)==0)
   exch.coins=coins;
   exch.c=inf(1,s(2));
   exch.rest=inf;
   return
end
rest=0;
while p>0
    trQ=mod(p,coins)==0;
    idx=it(trQ);
    li=length(idx);
    if isempty(idx)
       rst=1;
       rest=rest+rst;
       p=p-rst;
    elseif li>0 && li<s(2)
      ps=it(trQ)==0;
      idx2=idx;
      idx2(ps)=[];
      for k=1:li
          if p>0
             p=p-coins(idx2(k));
             c(idx2(k))=c(idx2(k))+1;
          end
      end
    elseif li==s(2)
     for k=1:li
         if p>0
            p=p-coins(idx(k));
            c(idx(k))=c(idx(k))+1;
         end
     end
    end
end
exch.coins=coins;
exch.c=c;
exch.rest=rest;
end

At least for the following example it works:

>> exch=achange(57,[10 25])
exch = 
struct with fields:
  coins: [25 10]
      c: [1 2]
   rest: 12
 
>> exch.coins*exch.c' + exch.rest
ans =
57

or for:

>> exch=achange(51,[10 25])
exch = 
struct with fields:
    coins: [25 10]
        c: [1 2]
     rest: 6

>> exch.coins*exch.c' + exch.rest
ans =
51

and finally my example from the comments:

>> exch=achange(60,[1 2 5 10 20])
exch = 
    struct with fields:
    coins: [20 10 5 2 1]
        c: [1 1 3 4 7]
     rest: 0

>> exch.coins*exch.c'  
ans =
60

If any input is not an integer, we obtain

>> exch=achange(57,[5 .10 25])
exch = 
    struct with fields:
    coins: [25 5 0.1000]
        c: [Inf Inf Inf]
    rest: Inf

or similar

>> exch=achange(57.8,[5 10 25])
exch = 
   struct with fields:
     coins: [25 10 5]
         c: [Inf Inf Inf]
      rest: Inf

UPDATE 21.11.2020

Due to the fact that the allocation of the species is not optimal by the above code, which can be seen, for instance, by first example, where the residual amount can still be allocated to some coins, I provide a small amendment that should produce better results.

The residual amount of the mentioned example is $12$ indicating that the structure of problem is unchanged, which allows us to solve the problem recursively. That is, we should replace the lines of code after the While-loop by the following If-construct to invoke a recursive call whenever it is necessary.

if any(rest>coins)
   exch2=achange(rest,coins);
   exch.coins=coins;
   exch.c=c+exch2.c;
   exch.rest=exch2.rest;
else
   exch.coins=coins;
   exch.c=c;
   exch.rest=rest;
end   

Then we can reduce the residual amount of the first example from $12$ to $2$, as we can see through

>> exch=achange(57,[10 25])
exch = 
   struct with fields:
     coins: [25 10]
         c: [1 3]
      rest: 2
$\endgroup$
2
  • $\begingroup$ Thank you very much! This code is very nice. As a newbie I guess I wouldn't have figured it out. Probably, it will take me some time to even understand the code completely. So again, thanks a lot for your help! $\endgroup$
    – Hokkaido21
    Nov 19 '20 at 15:37
  • $\begingroup$ @Hokkaido21 I provided a code amendment to optimize the allocation procedure of the coins. I hope this helps. $\endgroup$ Nov 21 '20 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.