简单的贪心算法 : http://love-oriented.com/pack/P01.html 说实话 我是喜欢 动态规划的.......但是省赛迫在眉睫 , 只好先 学 搜索了 , 赶紧 结束了 这三十道 搜索 然后 去开始 心爱的 动态规划!!! 下面 附上本人的 渣渣 代码
1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<vector> 8 using namespace std; 9 int main() 10 { 11 int n,a[25],f[200005],ave,i,total; 12 while(scanf("%d",&n)!=EOF) 13 { 14 for(ave=i=0;i<n;i++) 15 { 16 scanf("%d",&a[i]); 17 ave+=a[i]; 18 } 19 total=ave; 20 ave/=n; 21 memset(f,0,sizeof(f)); 22 for(int i=0;i<n;i++) 23 { 24 for(int j=ave;;j--) 25 { 26 if(ave-a[i]>=0) 27 break; 28 f[j]=max(f[j],f[j-a[i]]+a[i]); 29 } 30 } 31 printf("%d",total-2*f[ave]); 32 } 33 }
然而现在学的是搜索 所以 还是 在用 搜索 在写一次吧 ,
搜搜搜 , 搜了半天 , 发现三目运算符能节省大量的时间 , 以后少用 max min 多用三目运算符吧 .
还有就是 稍微换一下搜索的方式 就会wr 我也没找到原因 , 方正以后还是 多写标准的.
1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<vector> 8 #include<set> 9 #include<stack> 10 #include<string> 11 #include<sstream> 12 #include<map> 13 #include<cctype> 14 using namespace std; 15 int n,visited[22]; 16 double tem,minx,a[22]; 17 void DFS(int i,double sum) 18 { 19 if(minx>sum) 20 { 21 minx=minx>sum?sum:minx; // 太夸张了吧? 只是 把 min 改成三目运算符而已 , 就能让时间从888ms 到 400 ? 22 return ; 23 } 24 if(minx==0) 25 return ; 26 if(sum-a[i]>=0) 27 DFS(i+1,sum-a[i]); 28 DFS(i+1,sum); 29 } 30 int main() 31 { 32 int i; 33 double sum; 34 while(scanf("%d",&n)==1) 35 { 36 sum=0; 37 for(i=0;i<n;i++) 38 { 39 scanf("%lf",&a[i]); 40 sum+=a[i]; 41 } 42 double tem=sum/2; 43 minx=tem-1; 44 DFS(0,tem); 45 printf("%.0lf ",2*minx); 46 } 47 return 0; 48 }