Transacciones mínimas para resolver deudas entre amigos

Question

Se le da $n$ enteros $x_1,x_2,\dots,x_n$ satisfacción $\sum_{i=1}^n x_i=0$. Un movimiento legal es elegir un número entero $a$ y dos índices de $i,j$, y para aumentar el $x_i$ por $a$ y disminuir el $x_j$ por $a$. El objetivo es $x_1=x_2=\dots=x_n=0$.

¿Qué es un algoritmo que logra este objetivo en el menor número de movimientos?

Existe un algoritmo que siempre tarda $n-1$ se mueve; en la $i^{th}$ paso, disminuir el $x_i$ por $x_i$ y aumentar el $x_{i+1}$ por $x_i$. Esto no es siempre óptimo, porque si la mitad de la $x_i$ igual $1$ y la otra mitad de la igualdad de $-1$, a continuación, $n/2$ mueve suficiente.

La motivación de este problema es la situación en la $n$ amigos se han ido a cenar, y han contribuido de cierta cantidad de dinero de la factura, y ahora quieren hacer lo que ellos tienen todo pagado una cantidad igual.

Answer 1

Por desgracia, en este mundo desequilibrado es duro para lograr la igualdad, incluso entre amigos. Es decir, para este problema existe ningún polinomio algoritmo a menos $\mathcal{ P=NP}$, ver más abajo.

Poner $[n]= \{1,\dots, n\}.$

La proposición. El objetivo se puede lograr en menos de $n-1$ mueve el fib no es un subconjunto $S$ de $[n]$ tal que $\sum_{i\in S} x_i=0$.

Prueba. ($\Leftarrow$) Si existe un conjunto $S$ entonces podemos annulate todos los $x_i$ con $i\in S$ por $|S|-1$ se mueve, y todos los $x_i$ con $i\in [n]\setminus S$ por $|[n]\setminus S |-1$ se mueve. Por lo tanto, podemos lograr el objetivo en la mayoría de los $|S|-1+|[n]\setminus S |-1=n-2$ se mueve en total.

($\Rightarrow$) Asumen que los amigos pueden annulate todos los $x_i$ uso de $k<n-1$ se mueve. Considere la posibilidad de un gráfico de $G$ , con el set de $[n]$ de vértices tal que los vértices $i$ e $j$ son adyacentes por una arista de peso $a$ fib hubo un pago de $a$ entre $i$-th y $j$-th amigo. Dado que el gráfico de $G$ tiene menos de $n-1$ bordes, tiene al menos dos componentes conectados. Claramente, $\sum_{i\in S} x_i=0$ para cada componente $S$. $\square$

Por último hacemos la observación de que es NP-difícil decidir si existe un subconjunto $S$ de $[n]$ tal que $\sum_{i\in S} x_i=0$, debido a que este problema es equivalente al Subconjunto suma problema, que es NP-duro. De hecho, dado enteros $x_1,\dots, x_{n-1}$ e $x_n=-\sum_{i\in [n-1]} x_i$, existe un subconjunto $S$ de $[n-1]$ tal que $\sum_{i\in S} x_i=0$ fib existe un subconjunto $S'$ de $[n]$ tal que $\sum_{i\in S'} x_i=0$.

Answer 2

Supongamos que tenemos un mínimo de tamaño de conjunto de los pagos, yo reclamo el resultado (grafo!) pago gráfica es siempre un árbol. En efecto, supongamos que el grafo tiene un ciclo, entonces podemos ajustar todos los pagos en este ciclo por $\pm 1$ hasta uno de los bordes se convierte en un pago de $0$ y desaparece. Podemos utilizar este procedimiento para encontrar una forma óptima de resolver cualquier $S \subseteq [n]$ con $\sum_{i\in S} x_i = 0$ uso de $|S|-1$ pagos.

Claramente entonces, la solución óptima se partición $[n]$ en subconjuntos $S_1,\dots,S_k$ tal que $\sum_{i\in S_j} x_i = 0$ para todos los $1\leq j \leq k$ y resolver cada subconjunto uso de $|S_j|-1$ pagos. En otras palabras, la solución óptima tiene valor $n - k$ donde $[n] = S_1 \cup \dots \cup S_k$ es el más grande de la descomposición en suma de subconjuntos de a $0$.

Sin embargo, tenga en cuenta que si $S_1$ e $S_2$ suma $0$, entonces también lo hace $S_1 \cup S_2$, por lo que, equivalentemente, podemos encontrar una longitud máxima de la cadena de $\emptyset \neq S_1 \subseteq \dots \subseteq S_k = [n]$ y resolver todos los conjuntos de $S_{i+1} \setminus S_i$ individuall el uso de $|S_{i+1} \setminus S_i|-1$ pagos. Podemos encontrar una máxima longitud de la cadena en $O(n2^n)$ tiempo por precomputing para cada subconjunto $S \subseteq [n]$ el valor de $s(S) = \sum_{i\in S} x_i$ y, a continuación, utilizando sólo la recurrencia:

$a$b(S) = \begin{cases} 0 & \text{if %#%#%} \\ 1 + \max_{u\in S} b(S\setminus\{u\}) & \text{if %#%#%} \\ 0 + \max_{u\in S} b(S\setminus\{u\}) & \text{if %#%#%} \\ \end{casos} $$

Esto es, nuevamente, $S = \emptyset$ del tiempo. Como se señaló en la otra respuesta que es raro encontrar un polinomio de tiempo del algoritmo.