拔河比赛分组算法

组织亲子运动会，如接力赛或拔河比赛 #生活乐趣# #生活分享# #亲子生活互动# #亲子户外运动#

拔河比赛

题目

一个学校举行拔河比赛，所有的人被分成了两组，每个人必须（且只能够）在其中的一组，要求两个组的人数相差不能超过1，且两个组内的所有人体重加起来尽可能地接近。

输入

输入数据的第1行是一个n，表示参加拔河比赛的总人数，n<=100，接下来的n行表示第1到第n个人的体重，每个人的体重都是整数（1<=weight<=450）。

输入样例

3 100 90 200 1234

输出

输出数据应该包含两个整数：分别是两个组的所有人的体重和，用一个空格隔开。注意如果这两个数不相等，则请把小的放在前面输出。

输出样例

190 200 1

思路

假设a[i]表示第i个人的体重。f[i,j,k]表示在前i个人中选j个人在一组，他们的重量之和等于k是否可能。
这道题虽然看似要用三维，但是，因为第一维只和i和i-1有关系，所以，我们可以把第一维给省略掉。那么，动态转移方程就为：
f [ j , k ] = f [ j , k ] ∣ ∣ f [ j − 1 , k − a [ i ] ] ; f[j,k]=f[j,k]||f[j-1,k-a[i]]; f[j,k]=f[j,k]∣∣f[j−1,k−a[i]];
然后，我们可以将其转化为：
i f ( f [ j ] [ k ] ) f [ j + 1 ] [ k + a [ i ] [ 0 ] ] = 1 ; if (f[j][k]) f[j+1][k+a[i][0]]=1; if(f[j][k])f[j+1][k+a[i][0]]=1;

代码

#include<cstdio> #include<iostream> using namespace std; int n,a[101][2]; bool f[101][45001]; int main() {scanf("%d",&n);//读入f[0][0]=1;//标记初值for (register int i=1;i<=n;i++)//枚举前i个人{scanf("%d",&a[i][0]);//顺便读入for (register int j=i;j<=n;j++) a[j][1]+=a[i][0];//求前缀和for (register int j=i;j>=0;j--)//枚举选j个人for (register int k=0;k<=a[i][1];k++)//枚举重量if (f[j][k]) f[j+1][k+a[i][0]]=1;//如果之前选j个人重量为k是可以的，那么选j+1个人重量为k+a[i]也是可以的}for (register int i=0;;i++)//从下到大枚举相差量{if (f[n/2][a[n][1]/2+i])//比中间值大{printf("%d %d",min(a[n][1]/2+i,a[n][1]-a[n][1]/2-i),max(a[n][1]/2+i,a[n][1]-a[n][1]/2-i));//a[n][1]/2+i分一半，剩下的就是另一半a[n][1]-a[n][1]/2-i了return 0;//直接结束}if (f[n/2][a[n][1]/2-i])//比中间值小{printf("%d %d",min(a[n][1]/2-i,a[n][1]-a[n][1]/2+i),max(a[n][1]/2-i,a[n][1]-a[n][1]/2+i));//a[n][1]/2-i分一半，剩下的就是另一半a[n][1]-a[n][1]/2+i了return 0;//直接结束}} }

123456789101112131415161718192021222324252627282930313233

网址：拔河比赛分组算法 https://www.yuejiaxmz.com/news/view/563528

相关内容

【算法】网球循环赛比赛日程表
河塘中心幼儿园教师厨艺DIY比赛活动方案
建设行业选拔赛瓷砖贴面及抹灰与隔墙系统两赛项日前开赛
第十六届全国大学生智能车竞赛创意组别
“我是小小设计家”！这场比赛，拼的就是创意~~
第十一届未来设计师大赛校内选拔赛圆满落幕
我校举办第三届校园马拉松比赛
多图欣赏！拔火罐、肚脐贴……神秘“东方力量”频频亮相巴黎奥运赛场
叫河中心幼儿园保育员“桌面消毒”技能比赛
拔草哦：比价购物的智能伙伴

随便看看