NYOJ 325 ZB的生日

NYOJ 325 ZB的生日

zb的生日

描述

今天是陰歷七月初五，acm隊員zb的生日。zb正在和C小加、never在武漢集訓。他想給這兩位兄弟買點什麼慶祝生日，經過調查，zb發現C小加和never都很喜歡吃西瓜，而且一吃就是一堆的那種，zb立刻下定決心買了一堆西瓜。當他准備把西瓜送給C小加和never的時候，遇到了一個難題，never和C小加不在一塊住，只能把西瓜分成兩堆給他們，為了對每個人都公平，他想讓兩堆的重量之差最小。每個西瓜的重量已知，你能幫幫他麼？

輸入

多組測試數據（<=1500）。數據以EOF結尾
第一行輸入西瓜數量N (1 ≤ N ≤ 20)
第二行有N個數，W1, …, Wn (1 ≤ Wi ≤ 10000)分別代表每個西瓜的重量

輸出

輸出分成兩堆後的質量差

樣例輸入

5
5 8 13 27 14

樣例輸出

3

因為最多只會有20個西瓜，DFS搜索的話勢必秒過，嘗試用01背包解的，發現稍微控制不好dp數組和程序中的循環處理就會引發TM，不過勉強2000+ms還是可以過得去的！！！

#include
#include
#include
int a[25];
int dp[100005];
int max(int a,int b)
{return a>b?a:b;}
int main()
{
    int n,i,j,k;
    while(scanf("%d",&n!=EOF))
    {
        int sum=0;
        memset(dp,0,sizeof(dp));
        for(i=0;i=a[i];j--)
                dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
        printf("%d\n",sum-dp[k]*2);
    }
    return 0;
}