MATLAB: Make change for a dollar amount

changeMATLABmodpermutations

I need to write a function that generates all of the ways that change for a an amount can be made. However, we are not using nickle, dimes, and quarters to make this change. We are using a set of inputted values.

For example, if my inputs are: X = [2 3 4] and Y = 32

My output should be:

16 0 0
14 0 1
10 0 3
etc...,

showing all of the ways that I can make a sum of 32 with the coin values 2,3, and 4.

I've tried to use some sort of permutation to do this, and I've also tried using mod(x,y) in different fashions, and cannot seem to get the correct result.

Any insights? Thanks a lot folks!

Best Answer

This question usually comes out a lot in job-interviews. The common method of implementation is using a recursive function. Save the following function in payBill.m

function payBill(billList,billCount,Amount)
  billList=sort(billList,'descend');
  maxN=floor(Amount/billList(1));
  if (numel(billList)==1)
    reminder=mod(Amount,billList);
    if (reminder==0)
      count=[billCount maxN];
      disp(count)
    end
  elseif (numel(billList)>1)
    for i=maxN:-1:0
      reminder=Amount-i*billList(1);
      payBill(billList(2:end),[billCount i],reminder);
    end
  end
end

Now let's say you want to see all the combination of paying 7 cents using 1cent, 2cent, and 5cent coins. You can type the following command

payBill([1 5 2],[],7)

It will generate all the combination possible as follow:

     1     1     0 % 1x 5 cents + 1x 2 cents
     1     0     2 % 1x 5 cents + 2x 1 cents
     0     3     1 % 3x 2 cents + 1x 1 cents
     0     2     3 % 2x 2 cents + 3x 1 cents
     0     1     5 % 1x 2 cents + 5x 1 cents
     0     0     7 % 7x 1 cents

Note 1: when calling the function the order of billList doesn't matter. We could have put in [1 2 5] or [2 5 1] or [1 5 2], doesn't matter.

Note 2: when the counts are printed, regardless of the order you put the billList it would be always from the highest value coin to the lowest. Note in our example we gave [1 5 2] but the first number in the output is the count of 5 cents coin.

Note 3: if there is no possible combination to pay the exact amount nothing is printed. try payBill([3 5],[],7). There is no combination of 3cents coin and 5 cents coin to pay 7 cents. so nothing would be printed.

to get your example type, i.e. paying 32 cents using 2cents, 3cents, and 4cents coin type:

payBill([2,3,4],[],32)

the following output is generated. Note that the first column is for the highest value coin, i.e. 4cents and then the next column is for 3 cents and the last column is for 2cents.

     8     0     0 % 8x 4 cents
     7     0     2 % 7x 4 cents + 2x 2 cents
     6     2     1 % and so on
     6     0     4
     5     4     0
     5     2     3
     5     0     6
     4     4     2
     4     2     5
     4     0     8
     3     6     1
     3     4     4
     3     2     7
     3     0    10
     2     8     0
     2     6     3
     2     4     6
     2     2     9
     2     0    12
     1     8     2
     1     6     5
     1     4     8
     1     2    11
     1     0    14
     0    10     1
     0     8     4
     0     6     7
     0     4    10
     0     2    13
     0     0    16

Related Solutions

MATLAB: Hello…….i have a matrix…….what i wonaa do is count the repeated entries in column 2 first then make arrangement =(number of repeated termes)! ..for example in given matrix i have two repeated terms so first arrangmnt..1 2 3 the second 2 1 3

Interesting problem. I used a slightly more complex example, with two values duplicated (4 twice, 9 thrice), for which we would expect twelve possible permutations:

>> a = [1,4;2,9;3,2;4,9;5,4;6,9]
a =
   1   4
   2   9
   3   2
   4   9
   5   4
   6   9

And the code:

[N,B] = histc(a(:,2),unique(a(:,2))); % count instances of values in 2nd column
X = find(N>1);                        % find duplicate values
foo = @(x)perms(find(B==x));          % row permutations for each duplicate value
C = arrayfun(foo,X,'uni',0);          % "


S = cellfun('size',C,1);              % count row permutations
L = arrayfun(@(r)1:r,S,'uni',0);      % row indices for each permutation matrix
[L{:}] = ndgrid(L{:});                % combine row indices
R = cellfun(@(v)v(:),L,'uni',0);      % "
baz = @(m,r)m(r,:);                   % use row indices to select all permutations
M = cellfun(baz,C,R,'uni',0);         % "
V = 1:size(a,1);                      % original row indices of input matrix
Z = cell(1,prod(S));                  % preallocate output cell array
for ii = 1:prod(S)                    % for each possible permutation...
    for jj = 1:numel(X)               % for each duplicate value...
        V(B==X(jj)) = M{jj}(ii,:);    % get row permutation indices
    end                               %
    Z{ii} = a(V,:);                   % use indices to select from input matrix
end

And checking the output:

>> numel(Z) % should be 3!*2!
ans = 12
>> Z{:}
ans =
   1   4
   2   9
   3   2
   4   9
   5   4
   6   9
ans =
   5   4
   2   9
   3   2
   4   9
   1   4
   6   9
ans =
   1   4
   4   9
   3   2
   2   9
   5   4
   6   9
ans =
   5   4
   4   9
   3   2
   2   9
   1   4
   6   9
ans =
   1   4
   2   9
   3   2
   6   9
   5   4
   4   9
ans =
   5   4
   2   9
   3   2
   6   9
   1   4
   4   9
ans =
   1   4
   4   9
   3   2
   6   9
   5   4
   2   9
ans =
   5   4
   4   9
   3   2
   6   9
   1   4
   2   9
ans =
   1   4
   6   9
   3   2
   2   9
   5   4
   4   9
ans =
   5   4
   6   9
   3   2
   2   9
   1   4
   4   9
ans =
   1   4
   6   9
   3   2
   4   9
   5   4
   2   9
ans =
   5   4
   6   9
   3   2
   4   9
   1   4
   2   9

Note that the number of permutations is (# of 1st duplicate value)! * (# of 2nd duplicate value)! * (# of 3rd duplicate value)! * ... , which will clearly explode very quickly into something totally intractable....

MATLAB: Min- imum number of coins required to pay

You have some issues in your if-else structure, but also you have a numerical problem - use uint datatype to avoid this:

[NumCoins1, UniqueCoinNumber1, CoinsCollection1] = numberOfCoins(99.12, 100)
[NumCoins2, UniqueCoinNumber2, CoinsCollection2] = numberOfCoins(17.95, 20)
[NumCoins3, UniqueCoinNumber3, CoinsCollection3] = numberOfCoins(10, 10)
[NumCoins4, UniqueCoinNumber4, CoinsCollection4] = numberOfCoins(3.99, 3.5)
function [NumCoins, UniqueCoinNumber, CoinsCollection] = numberOfCoins(totalAmount, paidAmount)
% totalAmount=input('totalAmount: ');
%     paidAmount=input('paidAmount: ');
coins = [];
if paidAmount<totalAmount
    disp('The paid amount is less then the total amount')
    NumCoins = NaN;
    UniqueCoinNumber = NaN;
    CoinsCollection = NaN;
else
    transaction = paidAmount - totalAmount;
    transaction = uint16(transaction * 100);
    while transaction > 0
        if transaction >= 100
            transaction = transaction - 100;
            coins = [coins 1];
        elseif transaction >= 50
            transaction = transaction - 50;
            coins = [coins 0.5];
        elseif transaction >= 25
            transaction = transaction - 25;
            coins = [coins 0.25];
        elseif transaction >= 10
            transaction = transaction - 10;
            coins = [coins 0.1];
        elseif transaction >= 5
            transaction = transaction - 5;
            coins = [coins 0.05];
        elseif transaction  >= 1
            transaction = transaction - 1;
            coins = [coins 0.01];
        end
    end
    NumCoins = numel(coins);
    UniqueCoinNumber = numel(unique(coins));
    CoinsCollection = coins;
    
end
end

Best Answer

Related Solutions

MATLAB: Hello…….i have a matrix…….what i wonaa do is count the repeated entries in column 2 first then make arrangement =(number of repeated termes)! ..for example in given matrix i have two repeated terms so first arrangmnt..1 2 3 the second 2 1 3

MATLAB: Min- imum number of coins required to pay

Related Question