[理工] 演算法

看板Grad-ProbAsk作者 (Mistel)時間4年前 (2019/09/10 19:55), 4年前編輯推噓2(2推 0噓 16→)
留言18則, 3人參與, 4年前最新討論串9/11 (看更多)
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
推
09/10 20:03, 4年前 , 1F
題目有誤i1,i2,...,id必須為非負整數才有解
09/10 20:03, 1F
→
09/10 20:06, 4年前 , 2F
定義dp[k]為金額為k時，所需最少硬幣數量
09/10 20:06, 2F
→
09/10 20:07, 4年前 , 3F
dp[M] = min(dp[M], dp[M-i1]+1, ... , dp[M-id]+1)
09/10 20:07, 3F
→
09/10 20:08, 4年前 , 4F
dp[1]~dp[M]都必須求 所以有M個子問題
09/10 20:08, 4F
→
09/10 20:09, 4年前 , 5F
每個子問題 每次有d個錢幣可以選擇
09/10 20:09, 5F
哦哦對耶，上樓梯的問題Q_Q
→
09/10 20:11, 4年前 , 6F
easier than WHAT？ 題目寫得不清不楚在幹嘛？
09/10 20:11, 6F
→
09/10 20:13, 4年前 , 7F
等等我看懂了 應該是兩個要比較吧？
09/10 20:13, 7F
→
09/10 20:14, 4年前 , 8F
但是這兩個程式 應該都很好debug啊= =
09/10 20:14, 8F
→
09/10 20:15, 4年前 , 9F
他可能想考 Fib1的遞迴會被呼叫到好幾次的問題吧
09/10 20:15, 9F
瞭解 不好意思想再請教兩個問題 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
→
09/11 08:11, 4年前 , 10F
dp應該還是比較保險一點
09/11 08:11, 10F
→
09/11 08:23, 4年前 , 11F
畫線應該是j才對
09/11 08:23, 11F
推
09/11 11:36, 4年前 , 12F
35題的b有點看不懂，每次 d 種 : 即使幣值最高 10元，
09/11 11:36, 12F
→
09/11 11:36, 4年前 , 13F
在算 M = 9 的時候也要考慮進去嗎？
09/11 11:36, 13F
我想電腦還是會考慮進去？！
→
09/11 11:37, 4年前 , 14F
遞迴 debug 部分，"一般"是認為遞迴 coding 直觀但是
09/11 11:37, 14F
→
09/11 11:37, 4年前 , 15F
debug 難(當初學的時候也是)
09/11 11:37, 15F
瞭解
→
09/11 15:26, 4年前 , 16F
這題不能用greedy 因為他沒用greedy property
09/11 15:26, 16F
→
09/11 15:28, 4年前 , 17F
*沒有greedy property
09/11 15:28, 17F
知道greedy choice 一定在最佳解裡，但還是不確定要怎麼判斷一個問題有沒有greedy cho ice property...
→
09/11 15:40, 4年前 , 18F
然後第45題可以用segment tree做到O(n lg n) (笑)
09/11 15:40, 18F
QAQ 我真的太菜了 ※ 編輯: mistel (223.137.50.75 臺灣), 09/11/2019 18:22:44
‣ 更多 mistel 的文章
文章代碼(AID): #1TTuyiqL (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 9 之 11 篇)：
排序： 最舊先 | 最新先 | 留言數
理工
0
5
[理工] 演算法 演算法
a613204
12年前, 09/02
理工
2
7
[理工] 演算法 演算法
TokiyoHot
11年前, 11/13
理工
3
7
[理工] 演算法 演算法
f111222003
8年前, 01/05
理工
4
12
[理工] 演算法 演算法
a866662
7年前, 12/30
理工
2
6
[理工] 演算法 演算法
juiminliu
5年前, 08/07
理工
2
18
[理工] 演算法 演算法
mistel
4年前, 09/10
理工
2
5
[理工] 演算法 演算法
achicn3
4年前, 11/12
在新視窗開啟完整討論串 (共11篇)
‣ 更多 mistel 的文章
文章代碼(AID): #1TTuyiqL (Grad-ProbAsk)