Pague colectivamente el problema de la factura

Hay $n$ personas en una mesa. El $i$ ª persona tiene que pagar $p_i$ dólares.

Algunas personas no tienen las facturas correctas para pagar exactamente $p_i$ , por lo que se les ocurre el siguiente algoritmo.

Primero, todos ponen algo de su dinero sobre la mesa. Luego, cada individuo recupera el dinero que pagó en exceso.

Los billetes tienen un conjunto fijo de denominaciones (que no forman parte de la entrada).

Un ejemplo: supongamos que hay dos personas, Alice y Bob. Alice debe $ 5 y tiene cinco billetes de $ 1. Bob debe $ 2 y tiene un billete de $ 5. Después de que Alice y Bob ponen todo su dinero sobre la mesa, Bob recupera $ 3 y todos están felices.

Por supuesto, hay momentos en que uno no tiene que poner todo su dinero sobre la mesa. Por ejemplo, si Alice tenía mil billetes de $ 1, no es necesario que los ponga a todos en la mesa y luego retire la mayoría de ellos.

Quiero encontrar un algoritmo con las siguientes propiedades:

La entrada especifica el número de personas, cuánto debe cada persona y cuántos billetes de cada denominación tiene cada persona.
El algoritmo le dice a cada persona qué billetes poner sobre la mesa en la primera ronda.
El algoritmo le dice a cada persona qué facturas eliminar de la mesa en la segunda ronda.
Se minimiza la cantidad de facturas puestas sobre la mesa + la cantidad de facturas eliminadas de la mesa.

Si no hay una solución factible, el algoritmo simplemente devuelve un error.

algorithms optimization Chao Xu
fuente

¿Las denominaciones de los billetes se fijan por adelantado (digamos a las denominaciones estadounidenses $ 1, $ 2, $ 5, $ 10, $ 20, $ 50 y $ 100), o parte de la entrada? En otras palabras, ¿el algoritmo tiene que manejar la posibilidad de que Mefistófeles tenga tres billetes de $ 7, un billete de $ 13 y quince billetes de $ 4 ?

JeffE

Las facturas son fijas. Supongo que en ese caso no puedo reducir la suma del subconjunto y demostrar que es NP-Hard. Lo editaré.

Chao Xu

Necesita una forma de expresar 4/5 como una optimización única. No es posible optimizar para estas dos condiciones independientes. Sé lo que pretendes, tuve un problema similar antes, pero necesitas cuantificar exactamente lo que significa optimizar para ambas condiciones.

edA-qa mort-ora-y

Creo que sería mejor, como punto de partida, asumir que todos pagan la factura exactamente o que el algoritmo simplemente informa un fallo.

JeffE

¿Cuál es exactamente la pregunta aquí, hay requisitos de complejidad? Escribir un algoritmo ingenuo parece trivial, ¿o me falta algo?

Stéphane Gimenez

Respuestas:

Si reformula el problema de una manera ligeramente diferente (pero equivalente), un algoritmo se vuelve más obvio:

$n$ $n-1$ $p_i$ $i$ $p_0$

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

Es decir, cuando la comida termina, el restaurante debería tener $ 61, Alice debería tener $ 11, Bob debería tener $ 1 y Carl debería tener $ 5.

$b$ $m$

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

Las denominaciones de los billetes no importan, pero he elegido denominaciones de papel moneda estadounidense para este ejemplo porque son familiares.

$i$ $j$ $\{0,1\}$ $C$ $C_{0,j} = 0$ $j$

Continuando con nuestro ejemplo:

C = [\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}]

$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]$

indica que Alice comenzó con $ 1, $ 5, $ 10, $ 20, Bob comenzó con $ 1, $ 1, $ 5, $ 5, y Carl comenzó con $ 10 y $ 20.

Nuevamente, el objetivo es minimizar la cantidad de billetes que cambian de manos. En otras palabras:

\begin{aligned} Minimize: & \sum_{i = 0}^{n - 1} \sum_{j = 0}^{m - 1} C_{i, j} x_{i, j} \\ subject to: & \sum_{i = 0}^{n - 1} x_{i, j} = 1 for 0 \leq j < m, \\ \sum_{j = 0}^{m - 1} x_{i, j} b_{j} = p_{i} for 0 \leq i < n, \\ and & x_{i, j} \geq 0 \end{aligned}

$\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}$

La primera restricción dice que la solución solo puede asignar una factura particular a una de las partes, y la segunda asegura que todos paguen la cantidad apropiada.

Este es el problema de PROGRAMACIÓN INTEGRAL 0,1 y está completo para NP (ver [ Karp 1972 ]). La página de Wikipedia sobre programación lineal tiene información sobre diferentes algoritmos que pueden usarse para este tipo de problemas.

Hay potencialmente múltiples soluciones óptimas; A mano, la primera solución al ejemplo que se me ocurrió fue:

x = [\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}]

$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]$

lo que significa que Alice paga exactamente $ 5 y $ 20, Bob paga exactamente $ 1, $ 5 y $ 5, y Carl paga en exceso $ 10 y $ 20 y luego retira $ 5 de la mesa.

También utilicé el módulo de Programa lineal de enteros mixtos del sistema Sage Math que tiene la capacidad de usar diferentes backends de resolución ( GLPK , COIN , CPLEX o Gurobi ). La primera solución que dio fue

x = [\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}]

$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.

David
fuente

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?

Raphael

Existe una forma más condensada de esta IP, al tener una variable para el número de billetes de una denominación particular que una variable 0,1. Las denominaciones fijas cambian un poco la complejidad, si el número de personas también es fijo, el algoritmo de Lenstra puede resolverlo en tiempo polinómico.

Chao Xu

-2

Ciertamente, algunos inicios básicos podrían ser incluir las facturas más pequeñas disponibles para alcanzar el monto total de la factura general. Si no desea permitir facturas de $ 2, cada persona podría simplemente eliminar la factura más grande que pueda tomar del grupo y llegaría allí relativamente rápido. El billete de $ 2 arroja eso, ya que no se subdivide muy bien en las otras denominaciones y complica enormemente el problema. También hay una serie de otras optimizaciones que podrían hacerse para hacer observaciones sobre la necesidad de agregar más fondos durante la ronda 1 (por ejemplo, si el número total de billetes de $ 1 es suficiente para cubrir la factura, entonces todos puede dejar de ingresar a menos que aún no hayan ingresado lo suficiente para su factura).

AJ Henderson
fuente