作者mistel (Mistel)
看板Grad-ProbAsk
標題[理工] 演算法
時間Tue Sep 10 19:55:22 2019
https://i.imgur.com/R3LFDQu.jpg
請問這題是完全背包問題嗎？
看了蠻久的還是不太懂(a)小題M個子問題跟(b)小題每次有d個選項是怎麼來的
https://i.imgur.com/StqRuub.jpg
請問遞迴程式的好處並不包含易於debug嗎？為什麼？
感謝考題版
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.219.48 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1568116524.A.D15.html
1F：推 mathtsai: 題目有誤i1,i2,...,id必須為非負整數才有解09/10 20:03
2F：→ mathtsai: 定義dp[k]為金額為k時，所需最少硬幣數量09/10 20:06
3F：→ mathtsai: dp[M] = min(dp[M], dp[M-i1]+1, ... , dp[M-id]+1)09/10 20:07
4F：→ mathtsai: dp[1]~dp[M]都必須求 所以有M個子問題09/10 20:08
5F：→ mathtsai: 每個子問題 每次有d個錢幣可以選擇09/10 20:09
哦哦對耶，上樓梯的問題Q_Q
6F：→ mathtsai: easier than WHAT？ 題目寫得不清不楚在幹嘛？09/10 20:11
7F：→ mathtsai: 等等我看懂了 應該是兩個要比較吧？09/10 20:13
8F：→ mathtsai: 但是這兩個程式 應該都很好debug啊= =09/10 20:14
9F：→ mathtsai: 他可能想考 Fib1的遞迴會被呼叫到好幾次的問題吧09/10 20:15
瞭解
不好意思想再請教兩個問題
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
10F：→ DLHZ: dp應該還是比較保險一點09/11 08:11
11F：→ DLHZ: 畫線應該是j才對 09/11 08:23
12F：推 ekids1234: 35題的b有點看不懂，每次 d 種 : 即使幣值最高 10元， 09/11 11:36
13F：→ ekids1234: 在算 M = 9 的時候也要考慮進去嗎？ 09/11 11:36
我想電腦還是會考慮進去？！
14F：→ ekids1234: 遞迴 debug 部分，"一般"是認為遞迴 coding 直觀但是 09/11 11:37
15F：→ ekids1234: debug 難(當初學的時候也是) 09/11 11:37
瞭解
16F：→ mathtsai: 這題不能用greedy 因為他沒用greedy property 09/11 15:26
17F：→ mathtsai: *沒有greedy property 09/11 15:28
知道greedy choice 一定在最佳解裡，但還是不確定要怎麼判斷一個問題有沒有greedy cho
ice property...
18F：→ mathtsai: 然後第45題可以用segment tree做到O(n lg n) (笑) 09/11 15:40
QAQ 我真的太菜了
※ 編輯: mistel (223.137.50.75 臺灣), 09/11/2019 18:22:44