Un usuario preguntó 👇

[ad_1]

Estoy esperando un algoritmo para el problema a continuación.

Problema: Habrá un conjunto de personas que se deben algo de dinero o nada en absoluto. Ahora, necesito un algoritmo (el mejor y más organizado) para liquidar los gastos de este grupo.

Person AmtSpent
------ ---------
A       400  
B      1000  
C       100  
Total  1500

Ahora el gasto por persona es 1500/3 = 500. Lo que significa que B le da a A 100. B le da a C 400. Lo sé, puedo comenzar con la cantidad menos gastada y seguir subiendo.

alguien me puede decir lo mejor if Tú tienes.

En breve,

  1. Encuentre el gasto total y el gasto por cabeza.
  2. Encuentre la cantidad que cada uno debe o está pendiente (-ve denota pendiente).
  3. Comience con el valor mínimo +ve. Asignarlo a la cantidad -ve.
  4. Siga repitiendo el paso 3 hasta que se agote la cantidad -ve.
    s. Mover al siguiente número +ve más alto. Sigue repitiendo 3 y 4 hasta que haya +cinco números.

¿O hay una mejor manera de hacerlo?

La mejor manera de volver al estado cero (número mínimo de transacciones) se ha cubierto en esta pregunta aquí.

Creé una aplicación de Android que resuelve este problema. Puede ingresar gastos durante el viaje, incluso recomienda «quién debe pagar después». Al final calcula «quién debe enviar cuánto a quién». Mi algoritmo calcula el número mínimo requerido de transacciones y usted puede establecer la «tolerancia de transacciones» que puede reducir aún más las transacciones (no le importan las transacciones de $1). Pruébelo, se llama Liquidación:

https://mercado.android.com/detalles?id=cz.destil.settleup

Descripción de mi algoritmo:

Tengo un algoritmo básico que resuelve el problema con transacciones n-1, pero no es ideal. Funciona así: A partir de los pagos, calculo el saldo de cada miembro. El saldo es lo que pagó menos lo que debería haber pagado. Ordeno a los miembros según el saldo cada vez más. Así que siempre tomo los más pobres y los más ricos y la transacción está hecha. Al menos uno de ellos queda con saldo cero y se excluye de los cálculos posteriores. Por lo tanto, el número de transacciones no puede ser peor que n-1. También minimiza la cantidad de dinero en las transacciones. Pero no es ideal, porque no detecta subgrupos que puedan establecerse internamente.

Encontrar subgrupos que puedan establecerse internamente es difícil. Resuelvo esto generando todas las combinaciones de miembros y verificando if la suma de los saldos del subgrupo es cero. Comienzo con 2 pares, luego 3 pares… (n-1) par. Las implementaciones del generador de combinación están disponibles. Cuando encuentro un subgrupo, calculo las transacciones en el subgrupo utilizando el algoritmo básico descrito anteriormente. Por cada subgrupo encontrado, se guarda una transacción.

La solución es excelente, pero la complejidad aumenta a O(n!). Esto suena terrible, pero el truco es que en realidad solo habrá una pequeña cantidad de miembros. Lo probé en Nexus One (procesador de 1Ghz) y los resultados son: hasta 10 miembros: <100 ms, 15 membros: 1 s, 18 membros: 8 s, 20 membros: 55 s. Então até 18 membros o tempo de execução é bom. A solução alternativa para >15 miembros pueden usar simplemente el algoritmo básico (es rápido y correcto, pero no ideal).

Codigo fuente:

El código fuente está disponible dentro de un informe de algoritmo escrito en checo. El código fuente está al final y está en inglés:

https://web.archive.org/web/20190214205754/http://www.settleup.info/files/master-thesis-david-vavra.pdf

Posible respuesta

Ya describiste. Suma todos los gastos (1500 en tu caso), divide por el número de personas que comparten el gasto (500). Para cada individuo, deduzca de la cuota individual los aportes que hizo esa persona (para la persona A, descuente 400 de 500). El resultado es la red que esa persona «debe» al pool central. Si el número es negativo para cualquier persona, el grupo central «debe» a la persona.

Como ya ha descrito la solución, no estoy seguro de lo que está preguntando. ¿Quizás está tratando de resolver el problema sin el grupo central, el «banco»?

Tampoco sé a qué te refieres con «comenzar con la menor cantidad gastada e ir a por ello».

Posible respuesta

Hace poco escribí una entrada de blog describir un enfoque para resolver la liquidación de gastos entre los miembros de un grupo donde potencialmente todos deben a los demás else, de modo que el número de pagos necesarios para saldar las deudas sea el menor posible. Utiliza una formulación de programación lineal. También muestro un ejemplo usando un pequeño paquete R que implementa la solución.

Posible respuesta

Solución Javascript para el algoritmo aceptado:

const payments = 
  John: 400,
  Jane: 1000,
  Bob: 100,
  Dave: 900,
;

function splitPayments(payments) 
  const people = Object.keys(payments);
  const valuesPaid = Object.values(payments);

  const sum = valuesPaid.reduce((acc, curr) => curr + acc);
  const mean = sum / people.length;

  const sortedPeople = people.sort((personA, personB) => payments[personA] - payments[personB]);
  const sortedValuesPaid = sortedPeople.map((person) => payments[person] - mean);

  let i = 0;
  let j = sortedPeople.length - 1;
  let debt;

  while (i < j) 
    debt = Math.min(-(sortedValuesPaid[i]), sortedValuesPaid[j]);
    sortedValuesPaid[i] += debt;
    sortedValuesPaid[j] -= debt;

    console.log(`$sortedPeople[i] owes $sortedPeople[j] $$debt`);

    if (sortedValuesPaid[i] === 0) 
      i++;
    

    if (sortedValuesPaid[j] === 0) 
      j--;
    
  


splitPayments(payments);

/*
  C owes B $400
  C owes D $100
  A owes D $200
*/

Posible respuesta

Me gustaría hacer una sugerencia para cambiar los parámetros principales, desde el punto de vista de UX if no te importa mucho

Ya sea que sus servicios o productos se gasten entre un grupo, a veces estas cosas se pueden compartir. Por ejemplo, un aperitivo o sesiones privadas/semiprivadas en una conferencia.

Para cosas como una bandeja de fiesta de aperitivos, está implícito que todos tienen acceso, pero no necesariamente que todos lo tengan. Cobrar a cada persona para dividir el gasto cuando, digamos, solo el 30% de las personas que participaron pueden causar discordia a la hora de dividir la cuenta. Es posible que a otros grupos de personas no les importe. Entonces, desde un punto de vista algorítmico, primero debe decidir cuál de estas tres opciones usar, probablemente a expensas:

universalmente dividido
Dividido por los que participaron, en partes iguales
Dividido por proporción por participante

Personalmente, prefiero este último en general porque tiene la utilidad de manejar la propiedad de todos los gastos para los gastos utilizados solo por una persona, algunas de las personas y todo el grupo también. También resuelve la cuestión ética de las diferencias proporcionales con una generalización general de, if participó, está pagando una parte igual, independientemente de cuánto haya tenido personalmente. Como elemento social, consideraría a alguien que tiene una «pequeña muestra» de algo solo para probar y luego decide que ya no tiene motivos para eliminar a esa persona del personal que comparte los gastos.

Después, small-sampling != partaking 😉

Luego toma cada gasto e itera a través del grupo de quién participó en qué, y manipula atómicamente cada uno de esos elementos, y al final, da un total por persona.

Entonces, al final, tomas tu lista de gastos y la repites con cada persona. Al final de la verificación de gastos individuales, toma a las personas que participaron y aplica una división uniforme de ese gasto a cada persona y actualiza la división de la cuenta corriente para cada persona.

Perdón por el pseudocódigo:

list_of_expenses[] = getExpenseList()
list_of_agents_to_charge[] = getParticipantList()

for each expense in list_of_expenses
    list_of_partakers[] = getPartakerList(expense)
    for each partaker in list_of_partakers
       addChargeToAgent(expense.price / list_of_partakers.size, list_of_agents_to_charge[partaker])

Luego simplemente iterar a través de su list_of_agents_to_charge[] y reporte cada total para cada agente.

Puede agregar soporte para una propina simplemente tratando la propina como un gasto adicional a su lista de gastos.

Posible respuesta

Simple, como lo haces en tu texto:

Devuelve los gastos a pagar por todos en el original array. Valores negativos: esa persona vuelve

Solo entrega lo que debes al siguiente en la fila y luego vete. Si obtienes alguno, solo espera la segunda ronda. Cuando termine, invierta todo. Después de estas dos rondas, todos pagaron la misma cantidad.

procedure SettleDepth(Expenses: array of double);
var
  i: Integer;
  s: double;
begin
  //Sum all amounts and divide by number of people
  // O(n) 
  s := 0.0;
  for i := Low(Expenses) to High(Expenses) do
     s := s + Expenses[i];

  s := s / (High(Expenses) - Low(Expenses));

  // Inplace Change to owed amount
  // and hand on what you owe
  // drop out if your even 
  for i := High(Expenses) downto Low(Expenses)+1 do begin
     Expenses[i] := s - Expenses[i];
     if (Expenses[i] > 0) then begin
        Expenses[i-1] := Expenses[i-1] + Expenses[i];
        Expenses.Delete(i);
     end else if (Expenses[i] = 0) then begin
        Expenses.Delete(i);
     end;
  end;

  Expenses[Low(Expenses)] := s - Expenses[Low(Expenses)];
  if (Expenses[Low(Expenses)] = 0) then begin
     Expenses.Delete(Low(Expenses));
  end;

  // hand on what you owe
  for i := Low(Expenses) to High(Expenses)-1 do begin
     if (Expenses[i] > 0) then begin
        Expenses[i+1] := Expenses[i+1] + Expenses[i];
     end;
  end;
end;  

Posible respuesta

La idea (similar a lo que se pide, pero con un giro/usando un pequeño concepto de libro mayor) es usar la Cuenta del Fondo, donde por cada cuenta, los miembros pagan al Fondo o reciben del Fondo. Por ejemplo, en la imagen adjunta a continuación, los gastos de Costco los paga el Sr. P y necesita $93.76 del fondo común y otros miembros pagan $46.88 al fondo común.

Posible respuesta

Por supuesto, hay mejores maneras de hacer esto. Pero eso requeriría ejecutar un algoritmo de complejidad de tiempo NP que realmente podría mostrar su aplicación. De todos modos, así es como implementé la solución java para mi android suscripción usando colas de prioridad:

class calculateTransactions 
public static void calculateBalances(debtors,creditors) 
// add members who are owed money to debtors priority queue
// add members who owe money to others to creditors priority queue


public static void calculateTransactions() 
    results.clear(); // remove previously calculated transactions before calculating again
    PriorityQueue<Balance> debtors = new PriorityQueue<>(members.size(),new BalanceComparator()); // debtors are members of the group who are owed money, balance comparator defined for max priority queue
    PriorityQueue<Balance> creditors = new PriorityQueue<>(members.size(),new BalanceComparator()); // creditors are members who have to pay money to the group

    calculateBalances(debtors,creditors);

    /*Algorithm: Pick the largest element from debtors and the largest from creditors. Ex: If debtors = 4,3 and creditors=2,7, pick 4 as the largest debtor and 7 as the largest creditor.
    * Now, do a transaction between them. The debtor with a balance of 4 receives $4 from the creditor with a balance of 7 and hence, the debtor is eliminated from further
    * transactions. Repeat the same thing until and unless there are no creditors and debtors.
    *
    * The priority queues help us find the largest creditor and debtor in constant time. However, adding/removing a member takes O(log n) time to perform it.
    * Optimisation: This algorithm produces correct results but the no of transactions is not minimum. To minimize it, we could use the subset sum algorithm which is a NP problem.
    * The use of a NP solution could really slow down the app! */
    while(!creditors.isEmpty() && !debtors.isEmpty())  poor == null) 
            return;
        
        String richName = rich.name;
        BigDecimal richBalance = rich.balance;
        creditors.remove(rich); // remove the creditor from the queue

        String poorName = poor.name;
        BigDecimal poorBalance = poor.balance;
        debtors.remove(poor); // remove the debtor from the queue

        BigDecimal min = richBalance.min(poorBalance);

        // calculate the amount to be send from creditor to debtor
        richBalance = richBalance.subtract(min);
        poorBalance = poorBalance.subtract(min);

        HashMap<String,Object> values = new HashMap<>(); // record the transaction details in a HashMap
        values.put("sender",richName);
        values.put("recipient",poorName);
        values.put("amount",currency.charAt(5) + min.toString());

        results.add(values);

        // Consider a member as settled if he has an outstanding balance between 0.00 and 0.49 else add him to the queue again
        int compare = 1;
        if(poorBalance.compareTo(new BigDecimal("0.49")) == compare) 
            // if the debtor is not yet settled(has a balance between 0.49 and inf) add him to the priority queue again so that he is available for further transactions to settle up his debts
            debtors.add(new Balance(poorBalance,poorName));
        

        if(richBalance.compareTo(new BigDecimal("0.49")) == compare) 
            // if the creditor is not yet settled(has a balance between 0.49 and inf) add him to the priority queue again so that he is available for further transactions
            creditors.add(new Balance(richBalance,richName));
        
    


.
[ad_2]

nota: si aun no se resuelve tu pregunta por favor dejar un comentario y pronto le daremos una posible resolucion , muchas gracias

eso es todo,espero que te halla servido

¿Te ha resultado útil??

0 / 0

Deja una respuesta 0

Your email address will not be published. Required fields are marked *