Secara kolektif membayar masalah tagihan

Ada orang di meja. Orang ke- harus membayar dolar. $n$ $i$ $p_i$

Beberapa orang tidak memiliki tagihan yang tepat untuk membayar tepat , sehingga mereka membuat algoritma berikut. $p_i$

Pertama, semua orang menaruh sebagian uang mereka di atas meja. Kemudian setiap individu mengambil kembali uang yang mereka bayarkan.

Tagihan memiliki denominasi tetap (bukan bagian dari input).

Contoh: Misalkan ada dua orang, Alice dan Bob. Alice berutang $ 5 dan memiliki lima tagihan $ 1. Bob berhutang $ 2 dan memiliki satu tagihan $ 5. Setelah Alice dan Bob meletakkan semua uang mereka di atas meja, Bob mengambil kembali $ 3, dan semua orang senang.

Tentu saja, ada saat-saat di mana seseorang tidak harus meletakkan semua uangnya di atas meja. Sebagai contoh, jika Alice memiliki seribu $ 1 tagihan, tidak perlu baginya untuk meletakkan semuanya di atas meja dan kemudian mengambil sebagian besar dari mereka kembali.

Saya ingin mencari algoritme dengan properti berikut:

Masukan tersebut menentukan jumlah orang, berapa banyak setiap orang berutang dan berapa banyak tagihan dari setiap denominasi yang dimiliki masing-masing orang.
Algoritme memberitahu setiap orang tagihan mana yang harus diletakkan di atas meja pada putaran pertama.
Algoritme memberitahu setiap orang tagihan mana yang harus dihapus dari tabel di babak kedua.
Jumlah tagihan yang diletakkan di atas meja + jumlah tagihan yang dihapus dari tabel diminimalkan.

Jika tidak ada solusi yang layak, algoritma hanya mengembalikan kesalahan.

algorithms optimization Chao Xu
sumber

Apakah denominasi tagihan ditetapkan di muka (katakan kepada denominasi Amerika $ 1, $ 2, $ 5, $ 10, $ 20, $ 50, dan $ 100), atau bagian dari input? Dengan kata lain, apakah algoritme harus menangani kemungkinan bahwa Mephistopheles memiliki tiga tagihan $ 7, tagihan $ 13, dan lima belas $ 4 tagihan ?

JeffE

Tagihan sudah diperbaiki. Saya kira dalam hal itu saya tidak dapat mengurangi jumlah subset dan membuktikannya NP-Hard. Saya akan mengeditnya.

Chao Xu

Anda memerlukan cara untuk mengekspresikan 4/5 sebagai satu optimasi. Tidak dimungkinkan untuk mengoptimalkan kedua kondisi independen ini. Saya tahu tentang apa yang Anda maksudkan, saya memiliki masalah yang sama sebelumnya, tetapi Anda perlu mengukur dengan tepat apa artinya mengoptimalkan untuk kedua kondisi tersebut.

edA-qa mort-ora-y

Saya pikir akan lebih baik, sebagai titik awal, untuk mengasumsikan bahwa setiap orang membayar tagihan dengan tepat atau algoritme hanya melaporkan kegagalan.

JeffE

Apa sebenarnya pertanyaannya di sini, apakah ada persyaratan kompleksitas? Menulis algoritma naif tampaknya sepele, atau apakah saya kehilangan sesuatu?

Stéphane Gimenez

Jawaban:

Jika Anda menyatakan kembali masalah dengan cara yang sedikit berbeda (tetapi setara), suatu algoritma menjadi lebih jelas:

Ada pihak yang terlibat: orang, dan satu restauarant. Biarkan menjadi jumlah pesta uang yang harus miliki setelah makan selesai dan dibayar. Misalnya, jika Alice memiliki $ 36 dan berutang $ 25, Bob memiliki $ 12 dan berutang $ 11, dan Carl memiliki $ 30 dan berutang $ 25, kami mengatakan bahwa adalah restoran dan memiliki: $n$ $n-1$ $p_i$ $i$ $p_0$

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

Yaitu, ketika makan di atas restoran harus memiliki $ 61, Alice harus memiliki $ 11, Bob harus memiliki $ 1 dan Carl harus memiliki $ 5.

Sekarang mari menghitung semua tagihan yang terlibat. Sebagai contoh: $b$ $m$

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

Denominasi tagihan tidak masalah, tetapi saya telah memilih denominasi mata uang kertas AS untuk contoh ini karena mereka akrab.

Kami berupaya meminimalkan jumlah tagihan yang berpindah tangan, jadi kami mengaitkan "biaya" dengan orang yang tinggalkan dengan tagihan dengan menggunakan matriks . Entri 0 dalam matriks ini menunjukkan tagihan mana yang dimulai dengan masing-masing pihak ( untuk semua karena restoran dimulai tanpa tagihan). $i$ $j$ $\{0,1\}$ $C$ $C_{0,j} = 0$ $j$

Melanjutkan contoh kami:

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

menunjukkan bahwa Alice mulai dengan $ 1, $ 5, $ 10, $ 20, Bob mulai dengan $ 1, $ 1, $ 5, $ 5, dan Carl mulai dengan $ 10 dan $ 20.

Sekali lagi, tujuannya adalah untuk meminimalkan jumlah tagihan yang berpindah tangan. Dengan kata lain:

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

Batasan pertama mengatakan bahwa solusi hanya dapat menetapkan tagihan tertentu untuk satu pihak, dan yang kedua memastikan bahwa setiap orang membayar jumlah yang sesuai.

Ini adalah 0,1 INTEGER PROGRAMMING problem dan NP-complete (lihat [ Karp 1972 ]). Halaman Wikipedia tentang pemrograman linier memiliki informasi tentang berbagai algoritma yang dapat digunakan untuk jenis masalah ini.

Ada beberapa solusi optimal yang berpotensi; dengan tangan solusi pertama untuk contoh yang saya buat adalah:

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

yang berarti Alice membayar tepat $ 5 dan $ 20, Bob membayar tepat $ 1, $ 5 dan $ 5, dan Carl membayar lebih dari $ 10 dan $ 20 dan kemudian mengeluarkan $ 5 dari tabel.

Saya juga menggunakan modul Program Integer Linier Campuran sistem Sage Math yang memiliki kemampuan untuk menggunakan backend solver yang berbeda ( GLPK , COIN , CPLEX , atau Gurobi ). Solusi pertama yang diberikannya adalah

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

yang hampir sama kecuali bahwa Carl mengambil $ 5 "lainnya" yang diletakkan Bob di atas meja.

Merumuskan masalah dengan cara ini memenuhi semua properti yang Anda daftarkan (Anda dapat memperkirakan tagihan mana yang berasal dari dan matriks solusi ). Pengecualian mungkin # 4 yang dibahas dalam komentar pertanyaan. Tidak jelas bagi saya apa yang ingin Anda lakukan dalam situasi bahwa tidak ada solusi yang layak untuk himpunan persamaan linear: $C$ $x$

Identifikasi subset orang yang dapat membayar jumlah yang dikurangi? Atau mungkin sebagian orang yang masih bisa membayar seluruh tagihan, yaitu mereka membayar teman mereka.

Pernyataan akhir Anda membuatnya seolah-olah Anda tertarik pada kasus bahwa denominasi tagihan ditetapkan, namun ini tidak mengubah masalah.

Bagaimanapun, ada juga solusi di mana setiap orang membayar dengan kartu kredit. $O(1)$

David
sumber

Bahwa masalah ini dapat dinyatakan sebagai IP (hampir?) Jelas; tetapi seberapa bagus solusi ini? Apakah IP dari formulir yang dibuat dapat diselesaikan secara efisien? Jika tidak, apakah ada algoritma yang lebih cepat?

Raphael

Ada bentuk IP yang lebih kental, dengan memiliki variabel untuk jumlah tagihan dari denominasi tertentu daripada variabel 0,1. Denominasi tetap memang sedikit mengubah kompleksitas, jika jumlah orang juga diperbaiki, algoritma Lenstra dapat menyelesaikannya dalam waktu polinomial.

Chao Xu

-2

Tentu saja beberapa permulaan dasar dapat mencakup tagihan terkecil yang tersedia untuk mencapai jumlah total tagihan keseluruhan. Jika Anda tidak peduli untuk mengizinkan tagihan $ 2, setiap orang bisa dengan mudah menghapus tagihan terbesar yang bisa mereka ambil dari kolam itu dan akan sampai di sana relatif cepat. Uang kertas $ 2 membuang itu karena tidak membagi dengan baik ke dalam denominasi lain dan sangat memperumit masalah. Ada juga tentu saja sejumlah optimasi lain yang dapat dilakukan untuk membuat pengamatan tentang perlunya dana lebih lanjut untuk ditambahkan selama putaran 1 (misalnya, jika jumlah total tagihan $ 1 pernah cukup untuk menutupi tagihan, maka semua orang dapat berhenti memasukkan kecuali mereka belum memasukkan cukup untuk tagihan mereka).

AJ Henderson
sumber