[理工] 交大108資演 題組15

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