Fork me on GitHub
#clojure-serbia
<
2021-03-27
>
Jovan Toroman18:03:17

evo ga neko moje gotovo rešenje. Radi i za slučajeve kada najbolja kombinacija novčića ne uključuje prvi, drugi, treći novčić. Nisam radio ček za nil, kontam da to nije bitno u ovom slučaju.

(defn coins-change
  "Given a value V, if we want to make change for V cents, 
  and we have infinite supply of each of C = { C1, C2, .. , Cm} 
  valued coins, what is the minimum number of coins to make the 
  change? If it's not possible to make change, print -1."
  [coins value]
  (apply min (for [c (range (count coins)) :let [sub-seq (drop c coins)]]
               (loop [current-coins sub-seq
                      current-value 0
                      min-coins     -1]
                 (let [can-add-first? (and (not-empty current-coins)
                                           (<= (+ current-value (first current-coins)) value))]
                   (if (or (= current-value value) (empty? current-coins))
                     min-coins
                     (if can-add-first?
                       (recur current-coins
                              (+ (first current-coins) current-value)
                              (if (= min-coins -1) 1 (inc min-coins)))
                       (recur (rest current-coins)
                              current-value
                              min-coins))))))))
P.S. Stres testirao sam ga sa traženjem vrednosti veličine 999999999 sa ulaznim nizom od jednog broja, [9]. Posle par sekundi da rezultat. E kad sam probao sa 9999999999, tad je već zablokirao, vrti u beskonačnost. Moguće da tad već prelazi u BigInt, koji ima više bajtova i samim tim su operacije sporije. Šta vi mislite?