※ 引述《sophialiege ()》之銘言：
: ※ 引述《DJWS (...)》之銘言：
: : 恩 討論版很多人說這一題可以用 0/1 knapsack 的演算法來做
: : 可是我想了將近一個學期 還是想不出來要怎麼解決
: : 有人可以指導一下嗎?
: 我不記得我以前是怎麼寫的
: 不過我現在有個點子
: 這一題正常的DP要二維table是吧
: 可是他有一個維度最多只有50
: 再考慮你的DP方式,是不是很合適用bitwise operation
: (long long 有 64 bits)
: 接下來算複雜度=> 5000*100*110 這樣要過應該 ok
謝謝你 我看懂了你的方法 (這還是我第一次用bit來存資訊...挺有趣的)
也寫出來了 :)
我是將一個數目 將可以湊成這個數目的數字個數 以bit的方式存在表格中
如此便可以將所有情形都列舉在一條陣列裡面
然後檢驗全部的情形 便可以求出解
我覺得這一題用bit來存放資訊 同時也壓縮了時間複雜度
若不用bitwise operation 鐵定會超時的 而且也會浪費很多記憶體空間
是否有更好的方法呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.167.12.162