[理工] 101清大計科

[st474ddr (hikke)]

由於身邊沒有解答
小弟來問一下
第一題的部分
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
推 ANANquenchan: S+((i-1)*Y+(j-1))*d
※ 編輯: st474ddr (42.75.0.92), 01/08/2019 01:21:47
→ st474ddr: 不是X嗎!!
→ moozkito: 第二題我是寫算出各Vi/Wi  O(n)
→ moozkito: 然後用一個 O(nlogn)的排序
→ moozkito: 再來照順序取到滿 O(n)
→ moozkito: 不知道行不行
→ eggy1018: 樓上的方法應該可以，雖然說寫greedy 要證明optimal sub
→ eggy1018: structure & greedy choice property 再寫比較好，不過
→ eggy1018: 三分樓上的方法很夠了
→ st474ddr: 感謝各位大大 那第一題為什麼不是乘上X 他是row-major
→ st474ddr: D[2][1]應該會是 S+XB才對吧
推 ANANquenchan: https://i.imgur.com/9BYNaWy.jpg
→ st474ddr: 感謝大大 X rows 我茫了哈哈