Algoritma untuk menemukan denominasi mata uang yang optimal

Mark tinggal di negara kecil yang dihuni oleh orang-orang yang cenderung terlalu memikirkan banyak hal. Suatu hari, raja negara memutuskan untuk mendesain ulang mata uang negara untuk membuat perubahan memberikan lebih efisien. Raja ingin meminimalkan jumlah koin yang diperlukan untuk membayar jumlah yang tepat hingga (tetapi tidak termasuk) jumlah tagihan kertas terkecil.

Misalkan unit mata uang terkecil adalah Koin. Tagihan kertas terkecil di kerajaan bernilai Koin. Raja memutuskan bahwa seharusnya tidak ada lebih dari denominasi koin yang berbeda yang beredar. Masalahnya, kemudian, adalah untuk menemukan -set bilangan bulat dari yang meminimalkan tunduk pada .$n$$m$$m$$\{d_1, d_2, ..., d_m\}$$\{1, 2, ..., n - 1\}$$\frac{1}{n-1}\sum_{i = 1}^{n-1}{c_1(i) + c_2(i) + ... + c_m(i)}$$c_1(i)d_1 + c_2(i)d_2 + ... c_m(i)d_m = i$

Misalnya, ambil USD standar dan denominasi koinnya dari . Di sini, tagihan kertas terkecil bernilai 100 dari koin terkecil. Dibutuhkan 4 koin untuk menghasilkan 46 sen menggunakan mata uang ini; kami memiliki . Namun, jika kami memiliki denominasi koin , hanya dibutuhkan 3 koin: . Manakah dari set denominasi ini yang meminimalkan jumlah koin rata-rata untuk menghasilkan jumlah hingga dan termasuk 99 sen?$\{1, 5, 10, 25, 50\}$$c_1(46) = 1, c_2(46) = 0, c_3(46) = 2, c_4(46) = 1, c_5(46) = 0$$\{1, 15, 30\}$$c_1(46) = 1, c_2(46) = 1, c_3(46) = 1$

Lebih umum, mengingat dan , bagaimana mungkin secara algoritmik menentukan set optimal? Jelas, seseorang dapat menghitung semua sub-set layak- dan menghitung jumlah rata-rata koin yang diperlukan untuk membuat jumlah dari 1 hingga , melacak yang optimal sepanjang jalan. Karena ada sekitar subset (tidak semuanya layak, tetapi masih), ini tidak akan menjadi sangat efisien. Bisakah Anda melakukan lebih baik dari itu?$n$$m$$m$$n - 1$$C(n - 1, m)$ $m$

Ini terkait dengan masalah pembuatan perubahan yang terkenal . Sudah dipelajari, pada kenyataannya, bahwa pertanyaan ini telah diselidiki untuk [1] menggunakan kekuatan kasar. Pada tahun 2003, kekerasan untuk menemukan denominasi yang optimal tampaknya menjadi masalah terbuka.$m \leq 7$

Jika Anda memeriksa artikel yang mengutip Shallit, sepertinya denominasi yang memungkinkan strategi perubahan rakus menjadi perhatian khusus. Jelaslah bahwa denominasi semacam itu memiliki keunggulan dalam praktik.

1. What This Country Needs is a 18c Piece oleh Jeffrey Shallit (2003)

Saya menduga (salah, tapi tahan dengan saya) bahwa seri koin akan menjadi optimal, karena koin akan ditempatkan secara eksponensial, sehingga mengurangi nilai yang tersisa sebanyak mungkin per koin tambahan. Sebagai contoh Anda, ini akan menjadi .$\{b^i |\ b = \lceil n^{1/m} \rceil, 0 \leq i < m\}$$\{1,3,9,27,81\}$

Ini kedudukan yang lebih baik ( ) daripada denominasi USD ( ), tetapi itu tidak harus berarti apa-apa.$390/99$$420/99$

Saya menulis skrip Haskell untuk mendapatkan beberapa angka dengan kekerasan, karena saya tidak yakin sekarang bagaimana cara pendekatan ini secara analitis.
Ternyata, distribusi eksponensial tidak selalu yang terbaik: kadang-kadang ada yang sedikit lebih baik, misalnya, untuk kita mendapatkan untuk tetapi untuk . Mesin lambat saya tidak bisa mencapai , jadi kami harus menggunakan angka yang lebih kecil, di sini.$(m,n) = (4,30)$$75/29$$\{20,8,3,1\}$$87/29$$\{27,9,3,1\}$$(5,100)$

Namun, saya perhatikan bahwa kesalahannya tampaknya cukup kecil. Sebagian besar waktu, pembagian jumlah menghasilkan sesuatu yang dimulai dengan 1,0 ..., jadi saya menjalankan beberapa tes lagi.

Dari set uji dengan dan , kami mendapatkan kesalahan rata-rata pertumbuhan eksponensial kami dibandingkan dengan solusi terbaik dengan standar deviasi .$3 \leq m \leq 5$$6 \leq n \leq 40$$1.12$$0.085$

Anda mungkin berpendapat bahwa parameter pengujian agak kecil, tetapi seperti yang Anda tunjukkan, itu hanya banyak untuk memaksa jika Anda menetapkan (kemungkinan besar ada solusi yang lebih baik, tapi ini adalah alasan yang sangat baik untuk mengendur dan melakukan beberapa Haskell).$n = 100$

Ini adalah ruang tes saya, jika Anda ingin mencobanya:

getopt :: [Integer] -> Integer -> [Integer]
getopt _ 0 = []
getopt coins target = choice:(getopt viable $ target - choice)
                          where
                            viable = filter ((>=) target) coins
                            choice = maximum $ viable

getsum :: [Integer] -> Integer -> Int
getsum coins n = sum $ map length $ map (getopt coins) [1..(n-1)]

buildall :: Integer -> Integer -> [[Integer]]
buildall 1 _ = [[1]]
buildall m n = foldl1 (++) $ map (\am -> map (\x -> x:am) [((head am)+1) .. (n-1)]) $ buildall (m-1) n

buildguess :: Integer -> Integer -> [Integer]
buildguess m n = reverse $ map ((^) $ ceiling $ (fromInteger n)**(1.0/(fromInteger m))) [0..(m-1)]

findopt :: Integer -> Integer -> ([Integer],Int)
findopt m n = foldl1 (\(l@(_,lhs)) -> (\(r@(_,rhs)) -> (if (lhs < rhs) then l else r)))
            $ map (\arr -> (arr,getsum arr n)) $ buildall m n

intcast :: (Integral a,Num b) => a -> b
intcast = fromInteger.toInteger

esterror :: Integer -> Integer -> Double
esterror m n = (intcast $ getsum (buildguess m n) n) / (intcast best)
                 where (_,best) = findopt m n

Saya menjalankan tes dengan

map (uncurry esterror) [(m,n) | m <- [3..5], n <- [6..40] ]