[理工] 交大108資演題組15 gash55025502 PTT批踢踢實業坊

作者: gash55025502 (白影弓) 2019-12-16 16:19:14

https://i.imgur.com/yjPlqqI.jpg
大家好想問這題的後面兩小題
交大答案都是給A
想請問用什麼方法可以達到O(n)的時間呢？
因為我能想到的好像也都是要先排序好這樣就花nlogn了
感謝大大

作者: cossetannie (paa) 2019-12-16 16:23:00

counting sort

作者: gash55025502 (白影弓) 2019-12-16 17:15:00

樓上他有給vi的值域嗎為什麼可以用counting sort

作者: mistel (Mistel) 2019-12-16 18:33:00

問一下這個knapsack是指部分背包嗎？他也沒有定義出他的問題

作者: gash55025502 (白影弓) 2019-12-16 18:33:00

我是把他當01背包來解

作者: mistel (Mistel) 2019-12-16 18:40:00

不知道屬於[U]算不算給出值域不過也知道U是大於2^32而已...不好意思我沒跟上那為什麼01背包還要排序？有什麼幫助嗎？喔等等我看懂了腦袋打結

作者: pyramidinc (PyramidInc) 2019-12-16 18:48:00

第二小題如果說排序然後greedy解 O(n) 我還算能理解那為什麽第三小題也是O(n)呢？

作者: mistel (Mistel) 2019-12-16 18:53:00

+1同問，我發現我上個月寫的時候寫DBD orz

作者: pyramidinc (PyramidInc) 2019-12-16 19:00:00

我也寫dbd 哈哈這份超難orz 很多演算法的東西偏偏我演算法又最弱

作者: mistel (Mistel) 2019-12-16 19:03:00

我覺得今年真的爆幹難QQQ 我記得寫完演算法後崩潰到蹲在我學校操場懷疑人生然後再往前寫發現跟今年真是不一樣的世界，難道出題教授覺得出選擇就可以難一點嗎==

作者: pyramidinc (PyramidInc) 2019-12-16 19:05:00

別難過這份我37分而已應該可以安慰到你...

作者: gash55025502 (白影弓) 2019-12-16 22:24:00

不知道有沒有人可以提供立宇題庫班的解答xd

作者: b10007034 (Warren) 2019-12-17 00:20:00

這題的下面兩題都用DP，都可以O(n)

作者: gash55025502 (白影弓) 2019-12-17 11:27:00

b大可以稍微講詳細一點嗎QQ想不出來怎麼用DP解到O(n) DP不是都要O(nm)嗎

作者: b10007034 (Warren) 2019-12-17 11:37:00

我想錯了，拍謝後來才看懂題目，第二題可以counting sort的話第三題也可以，先把重量為2的value都除以2（O(n)），然後counting sortO(n)

作者: gash55025502 (白影弓) 2019-12-17 11:41:00

但第三題sort完可以用greedy取嗎？因為他的weight可能1或2 不像第二題只有1

作者: b10007034 (Warren) 2019-12-17 11:46:00

是說題目這樣設計，包包有過載的情況嗎？

作者: gash55025502 (白影弓) 2019-12-17 11:49:00

過載是什麼意思？

作者: jeremyyuan (阿元) 2019-12-17 13:04:00

第三題我當初的想法是用01取所以是O(mn) 然後因為m=a*2^0+b*2^1 所以會是O(c*n)=O(n)

繼續閱讀