0
$\begingroup$

I want to solve the following problem. It is not a homework.

Assume that a company pays payroll to employees every period, the sum of the salaries for period is $T$. The accountant goes to the bank and withdraws the amount. She does not know what denominations she should ask the cashier to give here so that she can satisfy all salaries without asking any employee for change back. In the example below the denominations are 5,10,20,50 and 100. The total amount for all salaries for the period is 365. One employee gets 90 Dollars, the other gets 120 Dollars and the third gets 135 Dollars.

Questions:

Q1 - is to determine for each employee how many bills of each denomination to use so that the salary amount is paid in full and exactly without asking the employee to return change to the accountant. The answer presented suggests that first employee be paid 2-Twenty Dollars bill and 1-Fifty Dollars bill, and so on. Of course there may be 0, 1 or many solutions.

I am looking for the algorithm to use. You can help me by providing a reference instead of typing all the details.

Q2 - How can I tell if there is no solution?

Q3 - What area of mathematics study this kind of problem? Is it Dynamic Programming/Linear Programming?

Q4 - Do you know of any software that solves this kind of problems?

Thank you all.

Example data: enter image description here

$\endgroup$
8
  • $\begingroup$ Not sure this is sufficiently constrained. You could ask for all $5's$, say. or one $5$ and $36$ $10's$. Among other possibilities Are there other constraints? Fewest number of bills, say? $\endgroup$
    – lulu
    Apr 26, 2016 at 11:03
  • 1
    $\begingroup$ If, instead, you want to know "how many ways are there to do this?" then there are standard methods using generating functions. See, for example this or this $\endgroup$
    – lulu
    Apr 26, 2016 at 11:07
  • $\begingroup$ @lulu, thank you for your comments and for the links. Of course it would be fancier to add constraints, but I thought this would make it harder. As for the generating function approach, it is elegant. However, I guess it works for a single amount (employee in this case) only. I also think that trying to satisfy each individual separately, could lead to the situation where one runs out of 1 or more denominations suddenly, and would have to start over again. $\endgroup$
    – NoChance
    Apr 26, 2016 at 11:48
  • 1
    $\begingroup$ To clarify, I didn't mean to suggest that the individual solutions and the global solutions are in bijection. They aren't. If Alice gets two $5's$ and Bob gets a $10$, then I can switch those. So there is a combinatorial question involved in deciding which sets of individual solutions provide equivalent global solutions. Is that what you are asking about? $\endgroup$
    – lulu
    Apr 26, 2016 at 11:59
  • 1
    $\begingroup$ Well, unless I am confused (always possible) I see no problem with solving individually. Then just keep an Alice pile, and a Bob pile, and a Claire pile, and so on. Existence is a "small number" problem. That is, barring divisibility obstructions, there's always a solution if the total is big enough. If you have denominations of $2$ and $5$ then you can get any total larger than $3$, for example (but $1$ and $3$ are impossible). $\endgroup$
    – lulu
    Apr 26, 2016 at 12:27

0

Reset to default

You must log in to answer this question.