2011-06-10 21:15:16Morris
d890. 3.禮物分配(gift)
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 15 20 10 25
範例輸出 ：
35 35
提示
：
(1)測資有誤請告知感謝
(2)另外兩題本人都只過了局部測資
請會的人幫忙出吧
(3)北市賽時本題測資似乎有誤
出處
：
/**********************************************************************************/
/* Problem: d890 "3.禮物分配(gift)" from 99北市賽 */
/* Language: C */
/* Result: AC (12ms, 456KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-09 22:41:57 */
/**********************************************************************************/
#include<stdio.h>
main() {
int n, k, a, b, A[500];
while(scanf("%d %d", &n, &k) == 2) {
int DP[50001] = {}, sum = 0, half;
for(a = 0; a < n; a++)
scanf("%d", &A[a]), sum += A[a];
half = sum /2;
for(a = 0; a < n; a++)
for(b = half - A[a]; b >= 0; b--)
if(DP[b+A[a]] <= DP[b] + A[a])
DP[b+A[a]] = DP[b] + A[a];
int max = 0;
for(a = 0; a <= half; a++)
max = (max > DP[a]) ? max : DP[a];
if(max < sum - max)
printf("%d %d\n", max, sum - max);
else
printf("%d %d\n", sum - max, max);
}
return 0;
}