寫一題基本一點的題目~
連結：UVa10664 Luggage
題目：
有N個不同重量的行李，判斷是否能分出兩堆相同重量的行李放在兩台車上。
(0<N<=20)
(0<N<=20)
做法：
先想暴力，即在每個重量前放上＋或－號，可以枚舉2^N種結果
若有存在結果為0的就代表可以達成
不過，顯然地總和若為奇數是無法達成的
總和必須是偶數，平分後車上的行李重量恰是總和的一半
所以我們發現，我們也可以由"是否能挑出某些行李 其重量和是總重量和(sum)的一半"來判斷
於是問題轉換成容量為sum/2的01背包，複雜度為O(N*sum)，在此題最多是20*200，頗小
code:
沒有留言:
張貼留言