d890-3-禮物分配(gift)

上傳作業：http://203.68.236.9/problem/b0032

出處 http://zerojudge.tw/ShowProblem?problemid=d890

內容：

台北禮品公司老闆即將退休，退休前他想確認兩位高階經理中，那一位比較適合當他的接班人。因此他想出了下列測試方式。他將公司的n個禮品分給兩位經理，在由他們想辦法在最短的時間內推銷給客戶。每個禮品的單價最低0元(贈品)，最高k元。為了公平起見，兩位經理分配到的禮品個數可以不一樣多，但是禮品的總價必須越接近越好。請寫一個程式幫老闆將公司的禮品公平分配給兩位經理。

條件限制

(1)禮品數量 1<=n<=500

(2)禮品單價最低為0元，最高k<=100元

輸入說明：

輸入檔第一行有兩個數字(兩數字間有一個空白):n,k，分別代表禮品數量以及禮品最高單價。接下來的n行每行有一個數字:x代表某一禮品的單價，0<=x<=k

輸出說明：

請輸出兩個整數，及兩位經理所分配到的禮品總金額，金額較低者在前。

範例輸入：

4 25

範例輸出：

35 35

提示：

(1)測資有誤請告知感謝

(2)另外兩題本人都只過了局部測資

請會的人幫忙出吧

(3)北市賽時本題測資似乎有誤

出處：

99北市賽 (管理：leopan0922)

解題策略

0-1 Knapsack 背包負重上限為所有禮物單價總和除以2，物品重量與價值相同，取能放入背包的最大價值。