Make change for a dollar amount

12 views (last 30 days)
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!

Accepted Answer

Mohammad Abouali
Mohammad Abouali on 6 Dec 2014
Edited: Mohammad Abouali on 6 Dec 2014
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
  7 Comments
Mohammad Abouali
Mohammad Abouali on 6 Dec 2014
If your question is answered, please accept the answer.

Sign in to comment.

More Answers (0)

Categories

Find more on Dates and Time 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!

Translated by