随机算法：
呵呵，声明这篇里我们不谈科学的严谨，下面这道题听别人说用DF，DP等，我不知道怎

么DP，DF。因此弄了个随机数，随机分配硬币，当然也要用点小技巧，开始随机次数太

大搞了几次 Time Limit Exceeded，最后恼火了开了 100，我靠 ，这次 Wrong Answer，最后一

次了我搞了个 1000 ，终于 Accepted ！
这主要是在比赛的时候，如果实在没办法做，可以尝试用随机算法，运气好一次就可以
Accepted ，当然也不排除永远不能 Accepted，主要看它的测试数据强不强了。
呵呵，这样太没技术含量了，哪位朋友如果有好的解决办法，贴出来分享下啊 ！

分硬币 
一个背包里面最多有100枚硬币，要将这些硬币分给两个人，使得两人得到的钱差距最小

。每枚硬币的面值范围是1分到500分，不允许将一枚硬币分开。

 
Input
第一行有一个非负整数m（m<=100），表示硬币数。第二行有m个正整数，表示每枚硬币

的面值，中间用空格分开。

 
Output
每组仅输出一个非负整数，表示两人所分到钱的最小差值。

 
Sample Input
3
2 3 5
4
1 2 4 6

 
Sample Output
0
1
 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define TIMES 1000
int mycmp(const int*a,const int*b){
 if(*a > *b)
  return 1;
 if(*a < *b)
  return -1;
 return 0;
}
int    main(){
 int i,j,a[110],asave[110],min;
 int suma,sumb,k,t;
 
 while(scanf("%d",&i) != EOF){
  for(j = 0; j < i; j++)
   scanf("%d",&a[j]);
        memcpy(asave,a,sizeof(int)*i);
  qsort(a,i,sizeof(int),mycmp);
  for(min = 10000,j = 0; j < TIMES; j++){
   for(suma = sumb = k = 0; k < i; k++){
    t = rand()%i;
    if(a[t] == -1){
     for(t = 0; a[t] == -1; t++)
      ;
    }
    if(sumb > suma)
     suma += a[t];
    else
     sumb += a[t];
    a[t] = -1;
   }
   memcpy(a,asave,sizeof(int)*i);
   t = (suma > sumb ? suma-sumb : sumb - suma);
   if(t < min)
    min = t;
  }
  printf("%d\n",min);
 }
 return 0;

}

评论