[理工] 102成大資工程式設計 entryword PTT批踢踢實業坊

作者: entryword (chiahua) 2014-02-21 16:07:45

http://ppt.cc/WcTN
二、計算題的第2小題
題意看不太懂
(a)我理解是此問題轉成recursion tree後總共有幾個node
(b)就真的看不懂了, 甚麼叫有幾個最佳化的選擇
有人知道嗎?
謝謝QQ

作者: kiki86151 (魯飯) 2014-02-21 16:28:00

DynamicProgramming的面值問題http://ppt.cc/H8Qb 演算法筆記很清楚簡單來說有8元可以換1,4,6 換最少的數為多少最佳解結構就是先8元換1 8元換4 8元換6 觀察哪個最少可以推到遞迴

作者: john2557 (Wanger) 2014-02-21 16:46:00

所以這一題是要寫algo而已嗎？

作者: kiki86151 (魯飯) 2014-02-21 17:58:00

差不多吧反正懂後就嘴砲而已 M就是總錢數(8) 那個c代表有d(1,4,6)面值可換 i指那些面值可換的數要換最少(4*2)

作者: entryword (chiahua) 2014-02-21 19:04:00

我是不知道a, b小題要回答什麼@@這題不是問演算法吧不過寫上去大概還是有一點分?

作者: WashFreeID (免洗) 2014-02-21 19:34:00

第一題是M?第二題d-1? 不確定

作者: kiki86151 (魯飯) 2014-02-21 19:46:00

第一題感覺比較複雜不是M吧應該要畫遞迴樹第二題我覺得是d 就是選M-c1,M-c2....M-cd這些子問題最小在+1而已找到一個有實作code類似的網站http://ppt.cc/CT5l 它那顆樹就是5換1,2,3子問題就是樹的node 只有3換1出現2次

作者: jeremy4849 (yang) 2014-02-22 00:00:00

第一題有different ，感覺是M-1

繼續閱讀