→ cossetannie: counting sort 12/16 16:23
→ gash55025502: 樓上 他有給vi的值域嗎 為什麼可以用counting sort 12/16 17:15
推 mistel: 問一下這個knapsack是指部分背包嗎？他也沒有定義出他的 12/16 18:33
→ mistel: 問題 12/16 18:33
→ gash55025502: 我是把他當01背包來解 12/16 18:33
推 mistel: 不知道屬於[U]算不算給出值域 不過也知道U是大於2^32而已 12/16 18:40
→ mistel: ... 12/16 18:40
推 mistel: 不好意思我沒跟上 那為什麼01背包還要排序？有什麼幫助嗎 12/16 18:42
→ mistel: ？ 12/16 18:42
推 mistel: 喔等等我看懂了 腦袋打結 12/16 18:44
推 pyramidinc: 第二小題如果說排序然後greedy解 O(n) 我還算能理解 12/16 18:48
→ pyramidinc: 那為什麽第三小題也是O(n)呢？ 12/16 18:48
推 mistel: +1同問，我發現我上個月寫的時候寫DBD orz 12/16 18:53
推 pyramidinc: 我也寫dbd 哈哈 這份超難orz 很多演算法的東西 偏偏我 12/16 19:00
→ pyramidinc: 演算法又最弱 12/16 19:00
推 mistel: 我覺得今年真的爆幹難QQQ 我記得寫完演算法後崩潰到蹲在 12/16 19:03
→ mistel: 我學校操場懷疑人生 12/16 19:03
→ mistel: 然後再往前寫發現跟今年真是不一樣的世界，難道出題教授 12/16 19:04
→ mistel: 覺得出選擇就可以難一點嗎== 12/16 19:04
→ pyramidinc: 別難過 這份我37分而已 應該可以安慰到你... 12/16 19:05
→ gash55025502: 不知道有沒有人可以提供立宇題庫班的解答xd 12/16 22:24
推 b10007034: 這題的下面兩題都用DP，都可以O(n) 12/17 00:20
→ gash55025502: b大可以稍微講詳細一點嗎QQ想不出來怎麼用DP解到O(n 12/17 11:27
→ gash55025502: ) DP不是都要O(nm)嗎 12/17 11:27
推 b10007034: 我想錯了，拍謝 12/17 11:37
→ b10007034: 後來才看懂題目，第二題可以counting sort的話 12/17 11:37
→ b10007034: 第三題也可以，先把重量為2的value都除以2（O(n)）， 12/17 11:37
→ b10007034: 然後counting sort 12/17 11:37
→ b10007034: O(n) 12/17 11:37
→ gash55025502: 但第三題sort完可以用greedy取嗎？因為他的weight可 12/17 11:41
→ gash55025502: 能1或2 不像第二題只有1 12/17 11:41
推 b10007034: 是說題目這樣設計，包包有過載的情況嗎？ 12/17 11:46
→ gash55025502: 過載是什麼意思？ 12/17 11:49
推 jeremyyuan: 第三題我當初的想法是 用01取 所以是O(mn) 然後因為m= 12/17 13:04
→ jeremyyuan: a*2^0+b*2^1 所以會是O(c*n)=O(n) 12/17 13:04
推 FRAXIS: 第二題是 O(n lg n)，應該是不能 counting sort。 12/29 11:57
推 FRAXIS: 第二題應該是 O(n) 我回文解釋如何解第三題 12/29 12:15
推 zaqxsw2230: 我覺得第二題就是考慮最sort而已，用midium of midian 01/30 20:52
→ zaqxsw2230: (不知道有沒有拼錯) 01/30 20:53
→ zaqxsw2230: 然後他給m=theta(n^2) 所以就把它全取...就O(n)? 我是 01/30 20:54
→ zaqxsw2230: 這樣想的 01/30 20:54