22
$\begingroup$

There are $n$ people at a table. The $i$th person has to pay $p_i$ dollars.

Some people don't have the right bills to pay exactly $p_i$, so they come up with the following algorithm.

First, everyone puts some of their money on the table. Then each individual takes back the money they overpaid.

The bills have a fixed set of denominations (not part of the input).

An example: Suppose there are two people, Alice and Bob. Alice owes \$5 and has five \$1 bills. Bob owes \$2 and has one \$5 bill. After Alice and Bob put all their money on the table, Bob takes back \$3, and everyone is happy.

Of course, there are times where one doesn't have to put all his money on the table. For example, if Alice had a thousand \$1 bills, it's not necessary for her to put them all on the table and then take most of them back.

I want to find an algorithm with the following properties:

  1. The input specifies the number of people, how much each person owes and how many bills of each denomination each person has.

  2. The algorithm tells each person which bills to put on the table in the first round.

  3. The algorithm tells each person which bills to remove from the table in the second round.

  4. The number of bills put on the table + the number of bills removed from the table is minimized.

If there is no feasible solution, the algorithm just return an error.

$\endgroup$
  • 9
    $\begingroup$ Are the denominations of the bills fixed in advance (say to the American denominations \$1, \$2, \$5, \$10, \$20, \$50, and \$100), or part of the input? In other words, does the algorithm have to handle the possibility that Mephistopheles has three \$7 bills, a \$13 bill, and fifteen \$4 bills? $\endgroup$ – JeffE Jul 8 '12 at 22:24
  • 1
    $\begingroup$ The bills are fixed. I guess in that case I can't reduce subset sum and prove it's NP-Hard. I shall edit it. $\endgroup$ – Chao Xu Jul 8 '12 at 22:52
  • 1
    $\begingroup$ You need a way to express 4/5 as a single optimization. It isn't possible to optimize for these two independent conditions. I know about what you intend, I had a similar problem before, but you need to exactly quantify what it means to optimize for both conditions. $\endgroup$ – edA-qa mort-ora-y Jul 9 '12 at 15:59
  • 3
    $\begingroup$ I think it would be better, as a starting point, to assume that either everyone pays the bill exactly or the algorithm simply reports failure. $\endgroup$ – JeffE Jul 9 '12 at 17:44
  • 2
    $\begingroup$ What exactly is the question here, are there complexity requirements? Writing a naive algorithm seems trivial, or am I missing something? $\endgroup$ – Stéphane Gimenez Aug 31 '12 at 14:54
6
$\begingroup$

If you restate the problem in a slightly different (but equivalent) way, an algorithm becomes more obvious:

There are $n$ parties involved: $n-1$ persons, and one restauarant. Let $p_i$ be the amount of money party $i$ should have after the meal is finished and paid for. For example, if Alice has \$36 and owes \$25, Bob has \$12 and owes \$11, and Carl has \$30 and owes \$25, we say that $p_0$ is the restaurant and have:

$p = (61, 11, 1, 5)$

That is, when the meal is over the restaurant should have \$61, Alice should have \$11, Bob should have \$1 and Carl should have \$5.

Now let $b$ enumerate all of the $m$ bills involved. For example:

$b = (1, 5, 10, 20, 1, 1, 5, 5, 10, 20)$

The denominations of the bills do not matter, but I have chosen denominations of paper US currency for this example because they are familiar.

We are seeking to minimize the number of bills that change hands, so we associate a "cost" with person $i$ leaving with bill $j$ by using a $\{0,1\}$ matrix $C$. Entries of 0 in this matrix indicate which bills each party starts with ($C_{0,j} = 0$ for all $j$ because the restaurant starts with no bills).

Continuing our example:

$$ C = \left[ \begin{array}{cccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ \end{array} \right] $$

indicates that Alice started with \$1, \$5, \$10, \$20, Bob started with \$1, \$1, \$5, \$5, and Carl started with \$10 and \$20.

Again, the goal is to minimize the number of bills that change hands. In other words:

$$ \begin{align} \text{Minimize:} & \sum_{i=0}^{n-1}{\sum_{j=0}^{m-1}{C_{i,j} x_{i,j}}} \\ \text{subject to:} & \sum_{i=0}^{n-1}{x_{i,j}} = 1 \text{ for } 0 \le j \lt m, \\ & \sum_{j=0}^{m-1}{x_{i,j}b_j = p_i} \text{ for } 0 \le i \lt n, \\ \text{and} & x_{i,j} \ge 0 \end{align} $$

The first constraint says that the solution can only assign a particular bill to one party, and the second ensures that everyone pays the appropriate amount.

This is the 0,1 INTEGER PROGRAMMING problem and is NP-complete (see [Karp 1972]). The Wikipedia page about linear programming has information on different algorithms that can be used for these types of problems.

There are potentially multiple optimal solutions; by hand the first solution to the example I came up with was:

$$ x = \left[ \begin{array}{cccccccccc} 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \end{array} \right] $$

which means Alice pays exactly \$5 and \$20, Bob pays exactly \$1, \$5 and \$5, and Carl overpays \$10 and \$20 and then removes a \$5 from the table.

I also used the Mixed Integer Linear Program module of the Sage Math system which has the ability to use different solver backends (GLPK, COIN, CPLEX, or Gurobi). The first solution it gave was

$$ x = \left[ \begin{array}{cccccccccc} 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \end{array} \right] $$

which is almost the same except that Carl took the "other" $5 that Bob put on the table.

Formulating the problem in this way satisfies all the properties you list (you can extrapolate which bills end up where from $C$ and the solution matrix $x$). The exception is perhaps #4 which was discussed in the comments of the question. It is not clear to me what you would like to do in the situation that there is no feasible solution to the set of linear equations:

Identify a subset of people that can pay the reduced total? Or perhaps a subset of people which could still pay the entire bill, i.e. they pay for their friend.

Your final statement makes it seem like you are interested in the case that the denominations of the bills are fixed, this doesn't change the problem however.

In any case, there is also an $O(1)$ solution in which every person pays with a credit card.

$\endgroup$
  • $\begingroup$ That this problem can be expressed as IP was (almost?) clear; but how good is this solution? Can IPs of the created form be solved efficiently? If not, is there a faster algorithm? $\endgroup$ – Raphael Sep 30 '12 at 16:36
  • $\begingroup$ There exist a more condensed form of this IP, by having a variable for number of bills of a particular denomination than a 0,1 variable. Fixed denominations do change the complexity by a little, if the number of people are fixed as well, Lenstra's algorithm can solve it in polynomial time. $\endgroup$ – Chao Xu Jul 11 '13 at 19:29
-2
$\begingroup$

Certainly some basic starts could be to include the smallest bills available to reach the total amount of the overall bill. If you don't care to allow \$2 bills, each person could simply remove the largest bill they can take from the pool then and would get there relatively quickly. The \$2 bill throws that off as it doesn't sub-divide nicely in to the other denominations and greatly complicates the problem. There are also certainly a number of other optimizations that could be done to make observations about the need for further funds to be added during round 1 (for example, if the total number of \$1 bills is ever sufficient to cover the bill, then everyone can stop putting in unless they have not yet put in enough for their bill).

$\endgroup$

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.