/* 代码总体步骤是:(代码中的数字对应这些步骤) 1.先求出总和除以二为平均数 2.然后用母函数的代码 求出这些西瓜可以组成的 平均数一下的全部可能的重量 3.用bool数组把他们存起来 4.最后找出离平均数最近的那个数,就可以求出结果 */ #include<stdio.h> #include<string.h> int w[22]; int totle; bool p[100010]; int main() { int n,i,j,max; while(~scanf("%d",&n)) { max=0; memset(p,0,sizeof(p)); totle=0; p[0]=1; for(i=0;i<n;i++) { scanf("%d",&w[i]); totle+=w[i];//第一步 } for(i=0;i<n;i++)//第二步 { if(max!=totle/2)max+=w[i]; if(max>totle/2)max=totle/2;//这里优化了一下,时间减少很多哦! for(j=max;j-w[i]>=0;j--)//标准的应该是j=totle/2;但很多都没有用到,所以定义个max记录最大重量,从max开始就可以了 if(p[j-w[i]])p[j]=1;//第三步 } for(i=totle/2;!p[i];i--);//第四步 printf("%d\n",totle-2*i); } return(0); }
/* 这个方法比较好理解 f()函数执行的步骤: 要第一个西瓜 不要第一个西瓜 -------第一次f() 要第二个西瓜 不要第二个西瓜 要第二个西瓜 不要第二个西瓜-------第二次f() ... ... ... ... ... ... ... ... -------第n次 f() 优化: 如果哪一个分支超过了总数的一半,那个分支就不用算了。 */ #include<stdio.h> int w[22],totle,min,n,i,term; int abs(int x){return x>0?x:-x;} void f(int cur=0,int a=0)//cur记录第几个西瓜,a记录前cur个西瓜各种方式组成的重量 { if(cur==n)return; term=abs(totle-a-a); if(term<min)min=term;//记录计算过程中遇到的最符合的结果 if(a>totle/2)return;//优化了一下,如果超过了总数一半的重量,就不用往下算了! f(cur+1,a);//要第cur个西瓜 f(cur+1,a+w[cur]);//不要第cur个西瓜 } int main() { while(~scanf("%d",&n)) { min=100000,totle=0; for(i=0;i<n;i++)scanf("%d",&w[i]),totle+=w[i]; f(); printf("%d\n",min); } return(0); }
/* 这个方法跟第二个方法差不多,不过采用了各种优化手段使降低时间复杂度。 同时,为了配合优化,深度搜索的顺序也改变了(从后面向前面搜索) 下面大家慢慢体会代码的巧妙~ */ #include <stdio.h> #define max(a,b) a>b?a:b int avg,ans,n,w[21],sum[21]; void dfs(int i=n,int cnt=0)//i为第i个西瓜 cnt为第i个西瓜以后的重量的各种组合 { if(i == 0)//二叉树往下找出所有的cnt,ans为最大的cnt { ans = max(ans,cnt);//找出最大的结果(因为下面的代码保证了结果不会超过平均数,最大结果就是最优解) return ; } if(ans == avg || cnt+sum[i] <= ans) return ;//如果找到平均数或者cnt加上前面所有的西瓜重量都不超过这个最优解,那么就不用往下算了! if(cnt+w[i] <= avg)dfs(i-1,cnt+w[i]);//要第i个西瓜(如果要了第i个西瓜就超过了平均数,就不要了) dfs(i-1,cnt);//不要第i个西瓜 } int main() { while(~scanf("%d",&n)) { ans = 0; for(int i=1;i<=n;i++)//注意第一个西瓜存在w1里,而不是w0 { scanf("%d",&w[i]); sum[i] = sum[i-1] + w[i];//求出前n项和 } avg = sum[n]/2;//求出平均数 dfs();//开始遍历,注意要求的是最大的不超过平均数的数 printf("%d\n",sum[n]-2*ans);//输出结果 } return 0; }
相关推荐
南阳理工oj离线题库
南阳理工学院OJ第1版解题报告V1.0.pdf
南阳理工学院OJ_个人AC代码包(Java提交) 是Java初学者登堂入室的很好例子。
南阳理工学院stl练习场全部ac代码!
南阳理工ACM离线题库
哈理工OJ1084答案哈理工OJ1084答案哈理工OJ1084答案哈理工OJ1084答案哈理工OJ1084答案
(1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj...
西安理工大学学生在线实验系统编程题答案(超级详细)
基于Laravel 5.0的OJ题解网站 , 目前涵盖安科OJ,南阳OJ,杭电OJ ,北大OJ,浙大OJ.zip
山东理工大学2016级OJ进程,始于悦行,终于诚信。
趣味题:柱状图排序 西安理工大学学生在线实验系统 oj
西南科技大学OJ题
DFS:depth first search深度优先搜索(迷宫寻路) BFS:breadth first search宽度优先搜索(迷宫最短路径) OJ习题答案
已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及先序遍历结果,要求输出其后序遍历结果...
SWUST OJ : 1055、1056、1057、1058、1059、1060、1061、1062、1063、1064、1065、1066、1067、1068、1069、1070、1071、1072、1075、1086题答案
湖南理工学院OJ的0-100题解.rar
在线OJ网址大全在线OJ网址大全在线OJ网址大全在线OJ网址大全
实在写不出来,这个可以提供一些思路,慎重《copy》
厦门理工学院软件工程重点课件,考试前抱佛脚可用。
山东理工大学2016级OJ题目1833