379      京東網上商城

NYOJ325-zb的生日

zb的生日
時間限製：3000 ms  |  內存限製：65535 KB
難度：2
描述
今天是陰曆七月初五，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

來源
ural

本來想用動態規劃做的，但是沒做出來，隻能用DFS了（還好數據量比較小，大了就一定超時）
用DFS  AC代碼：

#include<stdio.h>
#include<string.h>
int abs(int n)
{
    if(n<0)
    return -1*n;
    else
    return n;
}
int a[50],min;
void Fun(int sum1,int sum2,int i,int n)
{
   if(i==n)
   {
      if(abs(sum1-sum2)<min)
      min=abs(sum1-sum2);      
      return;
   }
   Fun(sum1+a[i],sum2,i+1,n);
   Fun(sum1,sum2+a[i],i+1,n);
}
int main()
{
    int i,j,n,m,sum1,sum2,num;
    while(scanf("%d",&n)!=EOF)
    {
       for(i=0;i<n;i++)
       scanf("%d",&a[i]);
       min=999999999;
       sum1=0;sum2=0;i=0;
       Fun(sum1,sum2,i,n);
       printf("%d\n",min);
    }
    return 0;
}

最後更新：2017-04-03 12:56:21

  上一篇： poj 1580 String Matching【gcd輾轉相除法】

  下一篇： 怎麼在csdn中找到自己發布的帖子