Para üstü problemi
Para üstü veren bir kasiyer sığan en büyük parayı, sonra bir sonrakini alır; euro veya dolarda bu her zaman en az madeni parayı verir. Ama paraları 1, 3 ve 4 yaparsanız aynı alışkanlık, ikisi yeterliyken 6'yı üç parayla öder. Dinamik programlama ise her para kümesi için gerçek en küçük sayıyı bulur.
İki soru
Para üstü probleminin iki türü vardır. İlki, tam bir tutarı oluşturan en az madeni parayı sorar; buna para üstü verme problemi de denir. İkincisi, o tutarı kaç farklı madeni para kombinasyonunun oluşturduğunu sorar. Her ikisinde de her madeni para çeşidi istediğiniz kadar kullanılabilir ve ikisi de her tutarın cevabını daha küçük tutarların cevaplarından kurarak çözülür.
Adım adım en az madeni para
0'dan hedefe kadar tutarlar için bir sıra hücre oluşturun. 0 tutarı 0 madeni para gerektirir; diğer her tutar sonsuzla başlar. Tutarları sırayla gezin ve her biri için sığan her c parasını deneyin: tutar eksi c hücresi artı bir madeni para bir adaydır. En küçüğünü tutun. Her hücre yalnızca solundaki, zaten kesinleşmiş hücrelere bağlıdır; bu yüzden tek bir geçiş sırayı doldurur.
Bir örnek
1, 3 ve 4 değerindeki paralarla: 1 tutarı 1 madeni para, 2 tutarı 2, 3 tutarı 1 (tek bir 3) ve 4 tutarı 1 madeni para gerektirir. 5 için 1'i (4 için 1 gerekir, yani 2 madeni para), 3'ü (2 için 2 gerekir, yani 3 madeni para) ve 4'ü (1 için 1 gerekir, yani 2 madeni para) deneyin: en iyisi 2. 6 için 1'i (5 için 2 gerekir, yani 3), 3'ü (3 için 1 gerekir, yani 2) ve 4'ü (2 için 2 gerekir, yani 3) deneyin: en iyisi 3 + 3 ile 2. Açgözlü yöntem 4 + 1 + 1 öderdi.
Yolları saymak
Kombinasyonları saymak için paraları birer birer ekleyin. Yalnızca ilk parayla her tutar ya tek bir yolla oluşturulabilir ya da hiç oluşturulamaz. Yeni bir c parası katıldığında, bir a tutarını oluşturmanın yolları, c olmadan kurulan eski yollar artı c yine kullanılabilirken a − c tutarını oluşturmanın yollarıdır; çünkü bunların her biri bir c daha eklenerek a tutarını oluşturmanın bir yolu olur. 1, 2 ve 5 değerindeki paralarla 5'i oluşturmanın 4 yolu vardır: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 ve 1 + 1 + 1 + 1 + 1.
Açgözlü yöntem ne zaman yeterlidir?
Açgözlü yöntemin her zaman en az madeni parayı verdiği bir para sistemine kanonik denir. Modern para birimlerinin çoğu bu şekilde tasarlanmıştır ve 1994'te David Pearson, bir para sistemini, para sayısıyla yalnızca polinom olarak artan sayıda adımda kontrol eden bir test tanımladı. Eski İngiliz paraları kanonik değildi: açgözlü yöntem 48 peniyi bir yarım kron, bir şilin ve bir altı penilikle öder; oysa iki florin yeterdi.
Kendiniz keşfedin
Uygulamayı açın, Tablo görünümüne geçin ve Adım'a basın. En az madeni para modunda turuncu hücre hesaplanan tutar, mavi hücre ise paranın geriye bıraktığı daha küçük tutardır; alttaki satır son madeni parayı saklar ve sonunda paralar bu satır boyunca geriye okunur. Yol sayısı moduna geçin ve her para katıldıkça sayıların satır satır büyümesini izleyin.
Sık sorulan sorular
Para üstü problemi bir sırt çantası problemi midir?
Yakın bir akrabasıdır. En az madeni para sürümü, her paranın ağırlığı kendi değeri olan bir nesne olduğu, çantanın tam olarak doldurulması gerektiği ve amacın en az nesne olduğu bir sınırsız sırt çantası problemidir.
Zaman karmaşıklığı nedir?
Her iki sürümde de k çeşit para ve A tutarı için O(k·A). En az madeni para tablosunda A + 1 hücre, yollar tablosunda ise (k + 1)·(A + 1) hücre vardır; ancak hücreler yerinde güncellenirse tek bir satır yeterlidir.
Paralar neden sabit bir sırayla sayılır?
Her tutar her parayı deneseydi, 1 + 2 ve 2 + 1 iki ayrı yol olarak sayılırdı. Paraları satır satır eklemek, bir kombinasyonun her zaman önce daha önceki paralardan kurulması demektir; böylece her biri tam olarak bir kez sayılır.
Yol sayısı için paralar geri okunabilir mi?
Tek bir cevap olarak hayır, çünkü çok sayıda kombinasyon vardır. En az madeni para sürümü her tutarın son madeni parasını saklar; bu da en iyi kombinasyonlardan birini yeniden kurmak için yeterlidir.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Para üstü problemini deneyin