Pagar coletivamente o problema da fatura

Há $n$ pessoas em uma mesa. O ª pessoa tem que pagar dólares. $i$ $p_i$

Algumas pessoas não têm as contas certas para pagar exatamente , portanto, apresentam o seguinte algoritmo. $p_i$

Primeiro, todo mundo coloca um pouco de seu dinheiro na mesa. Então, cada indivíduo recebe de volta o dinheiro pago em excesso.

As notas têm um conjunto fixo de denominações (não faz parte da entrada).

Um exemplo: suponha que haja duas pessoas, Alice e Bob. Alice deve US $ 5 e tem cinco notas de US $ 1. Bob deve US $ 2 e tem uma nota de US $ 5. Depois que Alice e Bob colocam todo o seu dinheiro na mesa, Bob recebe US $ 3 e todo mundo fica feliz.

Claro, há momentos em que não é preciso colocar todo o dinheiro na mesa. Por exemplo, se Alice tinha mil notas de US $ 1, não é necessário que ela as coloque sobre a mesa e depois retire a maioria delas.

Quero encontrar um algoritmo com as seguintes propriedades:

A entrada especifica o número de pessoas, quanto cada pessoa deve e quantas notas de cada denominação cada pessoa possui.
O algoritmo diz a cada pessoa quais contas colocar na mesa na primeira rodada.
O algoritmo informa a cada pessoa quais contas remover da tabela na segunda rodada.
O número de notas colocadas na mesa + o número de notas removidas da mesa é minimizado.

Se não houver solução viável, o algoritmo retornará um erro.

algorithms optimization Chao Xu
fonte

As denominações das notas são fixadas antecipadamente (digamos, nas denominações americanas $ 1, $ 2, $ 5, $ 10, $ 20, $ 50 e $ 100) ou parte da entrada? Em outras palavras, o algoritmo precisa lidar com a possibilidade de Mefistófeles ter três notas de US $ 7, uma nota de US $ 13 e quinze de US $ 4 ?

Jeffe

As contas são fixas. Acho que nesse caso não posso reduzir a soma de subconjuntos e provar que é NP-Hard. Eu devo editá-lo.

Chao Xu

Você precisa de uma maneira de expressar 4/5 como uma única otimização. Não é possível otimizar para essas duas condições independentes. Sei o que você pretende, tive um problema semelhante antes, mas você precisa quantificar exatamente o que significa otimizar para ambas as condições.

edA-qa mort-ora-y

Eu acho que seria melhor, como ponto de partida, assumir que todos pagam a conta exatamente ou o algoritmo simplesmente relata falha.

9118 JeffE

Qual é exatamente a questão aqui, existem requisitos de complexidade? Escrever um algoritmo ingênuo parece trivial, ou estou faltando alguma coisa?

Stéphane Gimenez

Respostas:

Se você reafirmar o problema de uma maneira um pouco diferente (mas equivalente), um algoritmo se tornará mais óbvio:

Não há partes envolvidas: pessoas e um restaurante. Deixe ser a quantidade de partido dinheiro deve ter após a refeição é concluído e pago. Por exemplo, se Alice tem $ 36 e deve $ 25, Bob tem $ 12 e deve $ 11, e Carl tem $ 30 e deve 25, dizemos que é o restaurante e temos: $n$ $n-1$ $p_i$ $i$ $p_0$

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

Ou seja, quando a refeição termina, o restaurante deve ter US $ 61, Alice, US $ 11, Bob, US $ 1 e Carl, US $ 5.

$b$ $m$

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

As denominações das notas não importam, mas eu escolhi denominações da moeda americana em papel para este exemplo, porque elas são familiares.

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

Continuando nosso exemplo:

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 começou com $ 1, $ 5, $ 10, $ 20, Bob começou com $ 1, $ 1, $ 5, $ 5 e Carl começou com $ 10 e $ 20.

Novamente, o objetivo é minimizar o número de notas que mudam de mãos. Em outras palavras:

\begin{aligned} Minimize: & \sum_{i = 0}^{n - 1} \sum_{j = 0}^{m - 1} C_{i, j} x_{Eu, j} \\ sujeito a: & \sum_{Eu = 0 0}^{n - 1} x_{Eu, j} = 1 para 0 0 \leq j < m, \\ \sum_{j = 0 0}^{m - 1} x_{Eu, j} b_{j} = p_{Eu} para 0 0 \leq Eu < n, \\ e & x_{Eu, j} \geq 0 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}$

A primeira restrição diz que a solução pode atribuir apenas uma fatura específica a uma parte e a segunda garante que todos paguem o valor apropriado.

Esse é o problema de 0,1 INTEGER PROGRAMMING e está completo em NP (consulte [ Karp 1972 ]). A página da Wikipedia sobre programação linear possui informações sobre diferentes algoritmos que podem ser usados para esses tipos de problemas.

Existem potencialmente várias soluções ideais; manualmente, a primeira solução para o exemplo que surgiu foi:

x = [\begin{array}{cccccccccc} 0 0 & 1 & 0 0 & 1 & 1 & 0 0 & 0 0 & 1 & 1 & 1 \\ 1 & 0 0 & 1 & 0 0 & 0 0 & 0 0 & 0 0 & 0 0 & 0 0 & 0 0 \\ 0 0 & 0 0 & 0 0 & 0 0 & 1 & 0 0 & 0 0 & 0 0 & 0 0 & 0 0 \\ 0 0 & 0 0 & 0 0 & 0 0 & 0 0 & 0 0 & 1 & 0 0 & 0 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]$

o que significa que Alice paga exatamente US $ 5 e US $ 20, Bob paga exatamente US $ 1, US $ 5 e US $ 5, e Carl paga US $ 10 e US $ 20 e depois remove US $ 5 da mesa.

Também usei o módulo Programa Linear Inteiro Misto do sistema Sage Math , que tem a capacidade de usar diferentes back- end do solucionador ( GLPK , COIN , CPLEX ou Gurobi ). A primeira solução que deu foi

x = [\begin{array}{cccccccccc} 0 0 & 1 & 0 0 & 1 & 0 0 & 1 & 0 0 & 1 & 1 & 1 \\ 1 & 0 0 & 1 & 0 0 & 0 0 & 0 0 & 0 0 & 0 0 & 0 0 & 0 0 \\ 0 0 & 0 0 & 0 0 & 0 0 & 1 & 0 0 & 0 0 & 0 0 & 0 0 & 0 0 \\ 0 0 & 0 0 & 0 0 & 0 0 & 0 0 & 0 0 & 0 0 & 1 & 0 0 & 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]$

que é quase o mesmo, exceto que Carl levou os "outros" US $ 5 que Bob colocou na mesa.

$C$ $x$

Identifica um subconjunto de pessoas que podem pagar o total reduzido? Ou talvez um subconjunto de pessoas que ainda possam pagar a conta inteira, ou seja, paguem pelo amigo.

Seu extrato final faz parecer que você está interessado no caso de as denominações das notas serem fixas, mas isso não muda o problema.

$O(1)$

David
fonte

Que esse problema pode ser expresso como IP foi (quase?) Claro; mas quão boa é essa solução? Os IPs do formulário criado podem ser resolvidos com eficiência? Caso contrário, existe um algoritmo mais rápido?

Raphael

Existe uma forma mais condensada desse PI, possuindo uma variável para o número de notas de uma denominação específica do que uma variável 0,1. As denominações fixas alteram um pouco a complexidade; se o número de pessoas também é fixo, o algoritmo de Lenstra pode resolvê-lo em tempo polinomial.

Chao Xu

-2

Certamente, algumas etapas básicas podem incluir as menores faturas disponíveis para atingir o valor total da fatura geral. Se você não quiser permitir contas de US $ 2, cada pessoa pode simplesmente remover a maior conta que pode receber da piscina e chegar lá com relativa rapidez. A nota de US $ 2 joga isso fora, pois não se subdivide muito bem nas outras denominações e complica muito o problema. Certamente, também existem várias outras otimizações que podem ser feitas para fazer observações sobre a necessidade de adicionar mais fundos durante a primeira rodada (por exemplo, se o número total de notas de US $ 1 for suficiente para cobrir a conta, então todos pode parar de incluir, a menos que ainda não tenham investido o suficiente para pagar sua conta).

AJ Henderson
fonte