0
我試圖解決這個問題:硬幣找零優化
假設我有一組N個硬幣{A_1,A2,...,A_N}。總是會出現一個值爲 1的硬幣。 I 需要達到M的最小數量的硬幣是多少?
約束條件是:
- 1≤N≤25
- 1≤米≤10^6
- 1≤A_I≤100
好的,我知道這是改變的問題。 我試圖解決這個問題,使用廣度優先搜索,動態編程和貪婪(這是不正確的,因爲它並不總是提供最佳的解決方案)。但是,我得到超時限制(3秒)。
所以我想知道是否有這個問題的優化。 描述和約束稱爲我的注意,但我不知道如何使用它對我有利:
- 總是會出現值爲1的硬幣。
- 1≤A_I≤100
我在維基百科看到,這個問題也可以通過「與概率卷積樹動態規劃」來解決。但我什麼都聽不懂。
你能幫我嗎? 這個問題可以在這裏找到:http://goo.gl/nzQJem
謝謝你的回答。我試圖實現這一點,在某些情況下速度很快,但在其他情況下速度很慢。然後我嘗試了記憶,但它變成了O(n * m)。 – skide 2014-09-19 02:14:20
我認爲它可以在O(n * min(M,a_n * a_ {n-1}))中完成記憶。不需要在M-a_n * a_ {n-1}下面搜索。 – Ante 2014-09-19 07:19:56
非常聰明的解決方案!現在我得到了AC。非常感謝你! – skide 2014-09-20 14:40:46