作者gash55025502 (白影弓)
看板Grad-ProbAsk
標題[理工] 交大108資演 題組15
時間Mon Dec 16 16:19:14 2019
https://i.imgur.com/yjPlqqI.jpg
大家好 想問這題的後面兩小題
交大答案都是給A
想請問用什麼方法可以達到O(n)的時間呢？
因為我能想到的好像也都是要先排序好 這樣就花nlogn了
感謝大大
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.139.15.158 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1576484356.A.B64.html
1F：→ cossetannie: counting sort 12/16 16:23
2F：→ gash55025502: 樓上 他有給vi的值域嗎 為什麼可以用counting sort 12/16 17:15
3F：推 mistel: 問一下這個knapsack是指部分背包嗎？他也沒有定義出他的 12/16 18:33
4F：→ mistel: 問題 12/16 18:33
5F：→ gash55025502: 我是把他當01背包來解 12/16 18:33
6F：推 mistel: 不知道屬於[U]算不算給出值域 不過也知道U是大於2^32而已 12/16 18:40
7F：→ mistel: ... 12/16 18:40
8F：推 mistel: 不好意思我沒跟上 那為什麼01背包還要排序？有什麼幫助嗎 12/16 18:42
9F：→ mistel: ？ 12/16 18:42
10F：推 mistel: 喔等等我看懂了 腦袋打結 12/16 18:44
11F：推 pyramidinc: 第二小題如果說排序然後greedy解 O(n) 我還算能理解 12/16 18:48
12F：→ pyramidinc: 那為什麽第三小題也是O(n)呢？ 12/16 18:48
13F：推 mistel: +1同問，我發現我上個月寫的時候寫DBD orz 12/16 18:53
14F：推 pyramidinc: 我也寫dbd 哈哈 這份超難orz 很多演算法的東西 偏偏我 12/16 19:00
15F：→ pyramidinc: 演算法又最弱 12/16 19:00
16F：推 mistel: 我覺得今年真的爆幹難QQQ 我記得寫完演算法後崩潰到蹲在 12/16 19:03
17F：→ mistel: 我學校操場懷疑人生 12/16 19:03
18F：→ mistel: 然後再往前寫發現跟今年真是不一樣的世界，難道出題教授 12/16 19:04
19F：→ mistel: 覺得出選擇就可以難一點嗎== 12/16 19:04
20F：→ pyramidinc: 別難過 這份我37分而已 應該可以安慰到你... 12/16 19:05
21F：→ gash55025502: 不知道有沒有人可以提供立宇題庫班的解答xd 12/16 22:24
22F：推 b10007034: 這題的下面兩題都用DP，都可以O(n) 12/17 00:20
23F：→ gash55025502: b大可以稍微講詳細一點嗎QQ想不出來怎麼用DP解到O(n 12/17 11:27
24F：→ gash55025502: ) DP不是都要O(nm)嗎 12/17 11:27
25F：推 b10007034: 我想錯了，拍謝 12/17 11:37
26F：→ b10007034: 後來才看懂題目，第二題可以counting sort的話 12/17 11:37
27F：→ b10007034: 第三題也可以，先把重量為2的value都除以2（O(n)）， 12/17 11:37
28F：→ b10007034: 然後counting sort 12/17 11:37
29F：→ b10007034: O(n) 12/17 11:37
30F：→ gash55025502: 但第三題sort完可以用greedy取嗎？因為他的weight可 12/17 11:41
31F：→ gash55025502: 能1或2 不像第二題只有1 12/17 11:41
32F：推 b10007034: 是說題目這樣設計，包包有過載的情況嗎？ 12/17 11:46
33F：→ gash55025502: 過載是什麼意思？ 12/17 11:49
34F：推 jeremyyuan: 第三題我當初的想法是 用01取 所以是O(mn) 然後因為m= 12/17 13:04
35F：→ jeremyyuan: a*2^0+b*2^1 所以會是O(c*n)=O(n) 12/17 13:04
36F：推 FRAXIS: 第二題是 O(n lg n)，應該是不能 counting sort。 12/29 11:57
37F：推 FRAXIS: 第二題應該是 O(n) 我回文解釋如何解第三題 12/29 12:15
38F：推 zaqxsw2230: 我覺得第二題就是考慮最sort而已，用midium of midian 01/30 20:52
39F：→ zaqxsw2230: (不知道有沒有拼錯) 01/30 20:53
40F：→ zaqxsw2230: 然後他給m=theta(n^2) 所以就把它全取...就O(n)? 我是 01/30 20:54
41F：→ zaqxsw2230: 這樣想的 01/30 20:54