[理工] 演算法

[mistel (Mistel)]

https://i.imgur.com/R3LFDQu.jpg
請問這題是完全背包問題嗎？
看了蠻久的還是不太懂(a)小題M個子問題跟(b)小題每次有d個選項是怎麼來的


https://i.imgur.com/StqRuub.jpg
請問遞迴程式的好處並不包含易於debug嗎？為什麼？

感謝考題版

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.219.48 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1568116524.A.D15.html
推 mathtsai: 題目有誤i1,i2,...,id必須為非負整數才有解
→ mathtsai: 定義dp[k]為金額為k時，所需最少硬幣數量
→ mathtsai: dp[M] = min(dp[M], dp[M-i1]+1, ... , dp[M-id]+1)
→ mathtsai: dp[1]~dp[M]都必須求 所以有M個子問題
→ mathtsai: 每個子問題 每次有d個錢幣可以選擇
哦哦對耶，上樓梯的問題Q_Q
→ mathtsai: easier than WHAT？ 題目寫得不清不楚在幹嘛？
→ mathtsai: 等等我看懂了 應該是兩個要比較吧？
→ mathtsai: 但是這兩個程式 應該都很好debug啊= =
→ mathtsai: 他可能想考 Fib1的遞迴會被呼叫到好幾次的問題吧
瞭解
不好意思想再請教兩個問題
1.coin change problem可以用greedy方式解嗎？
我有查過是說要硬幣是鈔票的因數才可以？

2.
https://i.imgur.com/r8svDZ1.jpg
這一題的畫線部分應該是打錯了？
※ 編輯: mistel (114.136.219.48 臺灣), 09/11/2019 00:09:05
※ 編輯: mistel (114.136.219.48 臺灣), 09/11/2019 00:17:47
→ DLHZ: dp應該還是比較保險一點
→ DLHZ: 畫線應該是j才對
推 ekids1234: 35題的b有點看不懂，每次 d 種 : 即使幣值最高 10元，
→ ekids1234: 在算 M = 9 的時候也要考慮進去嗎？
我想電腦還是會考慮進去？！
→ ekids1234: 遞迴 debug 部分，"一般"是認為遞迴 coding 直觀但是
→ ekids1234:  debug 難(當初學的時候也是)
瞭解
→ mathtsai: 這題不能用greedy 因為他沒用greedy property
→ mathtsai: *沒有greedy property
知道greedy choice 一定在最佳解裡，但還是不確定要怎麼判斷一個問題有沒有greedy cho
ice property...
→ mathtsai: 然後第45題可以用segment tree做到O(n lg n) (笑)
QAQ 我真的太菜了
※ 編輯: mistel (223.137.50.75 臺灣), 09/11/2019 18:22:44