Make change for a dollar amount

Question

Scott 2014-12-5

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/165630-make-change-for-a-dollar-amount

评论： Mohammad Abouali 2014-12-6

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:

0 0
0 1
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!

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Mohammad Abouali 2014-12-6

3
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/165630-make-change-for-a-dollar-amount#answer_161469

编辑：Mohammad Abouali 2014-12-6

在 MATLAB Online 中打开

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     0 % 1x 5 cents + 1x 2 cents
   0     2 % 1x 5 cents + 2x 1 cents
   3     1 % 3x 2 cents + 1x 1 cents
   2     3 % 2x 2 cents + 3x 1 cents
   1     5 % 1x 2 cents + 5x 1 cents
   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.

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

7 个评论
显示 5更早的评论隐藏 5更早的评论

Mohammad Abouali 2014-12-6

编辑：Mohammad Abouali 2014-12-6

在 MATLAB Online 中打开

So I changed the code in such a way that it does not require that third parameter at all any more. so only two parameters (those that you want)

Here is the new code:

function count=payBill(billList,Amount)
  billList=sort(billList,'descend');
  maxN=floor(Amount/billList(1));
  if (numel(billList)==1)
    reminder=mod(Amount,billList);
    if (reminder==0)
      count=[billList;maxN];
    else
      count=[];
    end
    return;
  elseif (numel(billList)>1)
    count=reshape(billList,1,[]);
    for i=maxN:-1:0
      reminder=Amount-i*billList(1);
      tmpCount=payBill(billList(2:end),reminder);
      count=[count; ...
             ones(size(tmpCount,1)-1,1)*i tmpCount(2:end,:)];
    end
  end
end

Note that the method to call the function has changed now. It actually returns all the combination and the first row is the ordered bill list (denominations). Here is an example:

count=payBill([1,2,5],5)
count =
       5     2     1 % Note the first row is the denominations 
                     % to guid each column coincide with which coin
       1     0     0
       0     2     1
       0     1     3
       0     0     5

If this is what you want, please accept the answer.

Mohammad Abouali 2014-12-6

编辑：Mohammad Abouali 2014-12-6

在 MATLAB Online 中打开

Nope. Doesn't need to change anything in the code. The code already takes care of that

If you look at note1 in my first reply as I said, doesn't matter how the denominations are inputed. It can be ascending, descending or even random order.

The output would be always in the descending order (highest denomination to the lowest)

If you want the output to be also in ascending order just flip the results using fliplr() , as follow:

count=fliplr( payBill([2:4],32) );

Mohammad Abouali 2014-12-6

If your question is answered, please accept the answer.

请先登录，再进行评论。

Make change for a dollar amount

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

7 个评论
显示 5更早的评论隐藏 5更早的评论

更多回答（0 个）

另请参阅

类别

标签

产品

Community Treasure Hunt

Make change for a dollar amount

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

7 个评论 显示 5更早的评论隐藏 5更早的评论

更多回答（0 个）

另请参阅

类别

标签

产品

Community Treasure Hunt

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

7 个评论
显示 5更早的评论隐藏 5更早的评论