Kapan algoritma serakah dapat memecahkan masalah perubahan koin?

Diberikan satu set koin dengan denominasi berbeda dan nilai v Anda ingin menemukan jumlah koin paling sedikit yang diperlukan untuk mewakili nilai v. $c1, ... , cn$

Misalnya untuk coinet 1,5,10,20 ini memberikan 2 koin untuk jumlah 6 dan 6 koin untuk jumlah 19.

Pertanyaan utama saya adalah: kapan strategi serakah dapat digunakan untuk menyelesaikan masalah ini?

Poin bonus: Apakah pernyataan ini tidak benar? (Dari: Bagaimana cara mengetahui apakah algoritma serakah cukup untuk masalah perubahan koin minimum? )

Namun, makalah ini memiliki bukti bahwa jika algoritma serakah bekerja untuk denom terbesar pertama + nilai denom terbesar kedua, maka ia bekerja untuk mereka semua, dan itu menyarankan hanya menggunakan algoritma serakah vs algoritma DP optimal untuk memeriksanya. http://www.cs.cornell.edu/~kozen/papers/change.pdf

Ps. perhatikan bahwa jawaban di utas itu sangat payah - itu sebabnya saya mengajukan pertanyaan baru.

algorithms combinatorics greedy-algorithms Kucing Unfun
sumber

Untuk masalah biner ransel ada kriteria yang mudah dirumuskan: algoritma serakah memecahkan masalah jika untuk semua denominasi . Tidak mudah untuk mengganti koin (ransel dengan variabel integral sewenang-wenang). Apakah Anda memerlukan eksposisi Majalah, Nemhauser dan Trotter?

c_{i} > Σ_{j = 1}^{i - 1} c_{j}

$c_i > \Sigma_{j=1}^{i-1} c_j$

Dmitri Chubarov

Pernyataan dalam makalah oleh Dexter Kozen mengatakan bahwa jika algoritma serakah setuju dengan yang optimal untuk semua , maka itu akan memberikan solusi optimal untuk arbitrary . Saya tidak melihat ada yang salah dengan pernyataan ini.

v < c_{n - 1} + c_{n}

$v < c_{n-1} + c_n$

v

$v$

Dmitri Chubarov

@ Dmitri Chubarov Terima kasih, sekarang saya mengerti cara kerja q bonus. Apakah ini mirip dengan induksi yang kuat? Mengenai pertanyaan Anda yang lain, saya ingin jawaban yang memberikan solusi dan lebih baik bukti.

The Unfun Cat

Saya akan menjawab pertanyaan itu dan jika tidak ada yang melompat, rangkum MNT dengan beberapa contoh selama akhir pekan.

Dmitri Chubarov

Lihat juga pertanyaan terkait ini ; khususnya, kertas yang ditautkan oleh Shallit mungkin menarik.

Raphael

Jawaban:

Sistem koin adalah kanonik jika jumlah koin yang diberikan dalam perubahan oleh algoritma serakah optimal untuk semua jumlah.

Makalah D. Pearson. Algoritma waktu polinomial untuk Masalah Perubahan-Perubahan. Operations Reseach Letters, 33 (3): 231-234, 2005 menawarkan algoritma untuk memutuskan apakah sistem koin kanonik, di mana adalah jumlah berbagai jenis koin. Dari abstrak: $O(n^3)$ $n$

Kami kemudian memperoleh satu set nilai yang mungkin yang harus mengandung sampel tandingan terkecil. Masing-masing dapat diuji dengan operasi aritmatika , memberikan kita algoritma . $O(n^2)$ $O(n)$ $O(n^3)$

Makalahnya cukup pendek.

Untuk sistem koin non-kanonik, ada jumlah yang algoritma serakahnya menghasilkan jumlah koin suboptimal; disebut sampel balik . Sistem koin ketat jika sampel tandingan terkecilnya lebih besar dari koin tunggal terbesar. $c$ $c$

Makalah Sistem Koin Canonical untuk Masalah Pembuatan Perubahan menyediakan kondisi yang diperlukan dan memadai untuk sistem koin hingga lima koin menjadi kanonik, dan algoritma untuk memutuskan apakah sistem koin ketat dari koin adalah kanonik. $O(n^2)$ $n$

Ada juga beberapa diskusi dalam pertanyaan ini .

Mark Dominus
sumber

Terima kasih. Saya melihat pertanyaannya jauh lebih terlibat daripada yang saya kira - saya kira itu sebabnya Anda tidak memposting kriteria yang sebenarnya? Ide saya bahwa "jika semua koin adalah kelipatan satu sama lain, algoritma serakah memberikan hasil yang optimal" jelas terlalu sederhana.

The Unfun Cat

Saya tidak memposting kriteria yang sebenarnya karena saya tidak ingat begitu saja dan saya tidak punya waktu untuk membaca ulang kertas. Anda harus, tentu saja, merasa bebas untuk mengedit jawaban saya.

Mark Dominus

Saya membaca jawaban dan artikel beberapa kali, tetapi saya tidak dapat menemukan kriteria yang dapat dibaca manusiacanonical coin system . Akan lebih bagus jika Anda dapat menambahkan contoh, yaitu cara menguji sistem yang disarankan1,5,10,20

The Godfather