[理工] 101清大計科

看板Grad-ProbAsk作者 (hikke)時間7年前 (2019/01/08 01:00), 7年前編輯推噓2(2推 0噓 11→)
留言13則, 4人參與, 7年前最新討論串1/1
由於身邊沒有解答 小弟來問一下 第一題的部分 https://i.imgur.com/6ZdhOFU.jpg
請問我的理解是對的嗎 從D[1][1]開始 位置是S 每一格就是佔B的大小 所以答案應該是我寫的那樣嗎 還有第八題我不太了解 https://i.imgur.com/xoXFrtT.jpg
整個的意思 是要用一種演算法去推出背包問題嗎 這種答案該怎麼表達 謝謝各位大大 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.246.43.238 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1546880449.A.1AA.html ※ 編輯: st474ddr (27.246.43.238), 01/08/2019 01:01:24
推
01/08 01:18, 7年前 , 1F
S+((i-1)*Y+(j-1))*d
01/08 01:18, 1F
※ 編輯: st474ddr (42.75.0.92), 01/08/2019 01:21:47
→
01/08 01:24, 7年前 , 2F
不是X嗎!!
01/08 01:24, 2F
→
01/08 01:27, 7年前 , 3F
第二題我是寫算出各Vi/Wi O(n)
01/08 01:27, 3F
→
01/08 01:27, 7年前 , 4F
然後用一個 O(nlogn)的排序
01/08 01:27, 4F
→
01/08 01:27, 7年前 , 5F
再來照順序取到滿 O(n)
01/08 01:27, 5F
→
01/08 01:27, 7年前 , 6F
不知道行不行
01/08 01:27, 6F
→
01/08 01:31, 7年前 , 7F
樓上的方法應該可以，雖然說寫greedy 要證明optimal sub
01/08 01:31, 7F
→
01/08 01:31, 7年前 , 8F
structure & greedy choice property 再寫比較好，不過
01/08 01:31, 8F
→
01/08 01:31, 7年前 , 9F
三分樓上的方法很夠了
01/08 01:31, 9F
→
01/08 13:46, 7年前 , 10F
感謝各位大大 那第一題為什麼不是乘上X 他是row-major
01/08 13:46, 10F
→
01/08 13:46, 7年前 , 11F
D[2][1]應該會是 S+XB才對吧
01/08 13:46, 11F
推
01/08 13:56, 7年前 , 12F
01/08 13:56, 12F
→
01/08 16:03, 7年前 , 13F
感謝大大 X rows 我茫了哈哈
01/08 16:03, 13F
‣ 更多 st474ddr 的文章
文章代碼(AID): #1SCuN16g (Grad-ProbAsk)