[理工] 101清大计科

楼主: st474ddr (hikke)   2019-01-08 01:00:47
由于身边没有解答
小弟来问一下
第一题的部分
https://i.imgur.com/6ZdhOFU.jpg
请问我的理解是对的吗
从D[1][1]开始 位置是S
每一格就是占B的大小 所以答案应该是我写的那样吗
还有第八题我不太了解
https://i.imgur.com/xoXFrtT.jpg
整个的意思
是要用一种算法去推出背包问题吗
这种答案该怎么表达
谢谢各位大大
作者: ANANquenchan (ananquenchana)   2019-01-08 01:18:00
S+((i-1)*Y+(j-1))*d
楼主: st474ddr (hikke)   2019-01-08 01:24:00
不是X吗!!
作者: moozkito (Once!)   2019-01-08 01:27:00
第二题我是写算出各Vi/Wi O(n)然后用一个 O(nlogn)的排序再来照顺序取到满 O(n)不知道行不行
作者: eggy1018 (羅密歐與豬過夜)   2019-01-08 01:31:00
楼上的方法应该可以,虽然说写greedy 要证明optimal substructure & greedy choice property 再写比较好,不过三分楼上的方法很够了
楼主: st474ddr (hikke)   2019-01-08 13:46:00
感谢各位大大 那第一题为什么不是乘上X 他是row-majorD[2][1]应该会是 S+XB才对吧
作者: ANANquenchan (ananquenchana)   2019-01-08 13:56:00
楼主: st474ddr (hikke)   2019-01-08 16:03:00
感谢大大 X rows 我茫了哈哈

Links booklink

Contact Us: admin [ a t ] ucptt.com