Yakın zamanda meslektaş benim bu sorunu çözmek için bir algoritma yazmak için meydan okudu:

Paraları en az sayı olan 1 99 sent herhangi bir değişiklik yapmak gerekli bulmak. Paraları sadece peni (1), beşlik (5), onluk (10) ve çeyrek (25) ve yapabilir her değeri 1 ila 99 (1 % artışlarla) kullanarak bu paralar.

Ancak, aslında bunu kendim paraları mümkün olan her kombinasyonu inceleyerek olmadan nasıl yapacağımı bilmiyorum fark ettim. Orada olmak için iyi bir yol bu sorunu çözme ama bilmiyorum ne genel bu tip algoritma olurdu aradı ve çözemedim bir şekilde kolaylaştırmak ötesine bakmayı her çözüm.

Eğer herkes doğru yönde bana gelin diye merak ediyordum, ya da daha verimli bir algoritma sunuyoruz.

Sizin için ne arıyorsanızDinamik Programlama.

Aslında önceki cevaplar üzerine inşa edebilirsiniz, çünkü tüm olası değerleri için tüm olası kombinasyonları numaralandırma, gerek yok.

Algoritma 2 parametreleri almak gerekir:

• Olası para değerleri listesi burada [1, 5, 10, 25]
• Kapak aralığı, [1, 99] burada

Ve gol paraları bu dizi için gerekli minimum set hesaplamak için.

En basit şekilde alt-moda: bir devam etmektir

Range     Number of coins (in the minimal set)
          1   5   10   25
[1,1]     1
[1,2]     2
[1,3]     3
[1,4]     4
[1,5]     5
[1,5]*    4   1             * two solutions here
[1,6]     4   1
[1,9]     4   1
[1,10]    5   1             * experience tells us it's not the most viable one :p
[1,10]    4   2             * not so viable either
[1,10]    4   1   1
[1,11]    4   1   1
[1,19]    4   1   1
[1,20]    5   1   1         * not viable (in the long run)
[1,20]    4   2   1         * not viable (in the long run)
[1,20]    4   1   2

Biraz kolay, her adımda en fazla bir para ekleyerek devam edebiliriz, sadece nerede olduğunu bilmek gerekir. Bu [x,y 1] minimal set [x,y] minimal set içermelidir böylece 5 ** Aralık [x,y 1] dahil olması için aşağı kaynar.

Ama sizin de fark ettiğiniz gibi, bazen birden fazla setleri paralar aynı sayıda yani tereddütleri var. Bu durumda, ancak daha sonra atılacak olan karar olabilir.

Para ekleme genellikle sizin için eklediğiniz bir o kadar daha geniş bir yelpazede karşılamak için izin verir fark ettiğin zaman çalışan zaman geliştirmek mümkün olabilir sanırım.

Örneğin, not:

 [1,5]    4*1  1*5
 [1,9]    4*1  1*5

[1,5] kapak için bir nikel ekliyoruz ama bu [1,9] bizi bedavaya veriyor!

Ancak, zaman ile ilgili çok çirkin bir giriş setleri [2,3,5,10,25] kapak [2,99], ben emin olarak nasıl hızlı bir şekilde kontrol aralığı kapsamında yeni set, ya da olurdu aslında daha verimli.