拔河比赛 规矩把所有人分成A B两队,力气大的一方胜出 由于一开始不知道每个人力量多大,所以主持人分组定下如下策略: 根据每个人的体重尽可能的分配平均 分配的策略是:
- A B两队人数相差 <= 1
- A B两队人总量之差绝对值最小
=======================================================
比如某班级有N(可为奇数或者偶数)个人, 编号为0, 1, 2, ... (N-1) 每个人都有自身的体重, 比如 W0, W1, W2, ... W(N-1) 请问如何分配比赛两队的人数,保证双方人体重总和相差最小 打印出 A B两队的总体重(从小到大)
比如: 有7个人, 体重分别为 100 90 200 220 130 120 110
输出为(先输出体重小的两边总和): 470 500 请设计一个程序,根据人数自动来进行统计 注意输入的时候 第一个是输入的人个数,比如7个人后续输入的是7个人的体重
==================================================================
思路:
1.这是个什么问题
求的最小值
2.我的思路 把所有的可能都列出来,和所有人体重的一半相比,差绝对值最小的就是所要求的。
3如何实现我的思路
递归:n个里面选n (原始状态)<- (n + 1)个里面选n
如何实现n+1 ->n 取n+1数组中的前n个,然后最后一个和前面的元素进行交换,
交换方式:如下 1234 5
5234 1
5134 2
5124 3
5123 4
总思路实现如 1234(总体重一半就是5) 12(绝对值差2) 34
32(绝对值差0) 14-->这里可以设置break 直接跳出循环
31(绝对值差1) 24
41(绝对值差0) 23
42(绝对值差1)13
43(绝对值差2)12
========================================================== 实现代码如下:
#include <stdio.h>
#include <math.h>
void exch(int *a,int i,int j)
{//交换函数
int temp;
temp = a[i];a[i] = a[j];a[j] = temp;
}
float f1(int*a,int len,int i,float wei)
{//递归函数
int ii;
int jj;
float n;
float min = 11111;
int sum = 0;
if (i == len/2-1+len%2) {
for (ii = 0; ii <= i; ii++) {
sum+=a[ii];}
n = sum-wei;
// printf("n%f\n",n); 中间过程监视
if (n < 0) {
n = -1*n;}
if (n < min) {
min = n;
}
return n;
}
else{
for (ii = i; ii < len; ii++) {
for (jj = 0; jj < ii; jj++) {
n = f1(a, len, i-1, wei);
if (n < min) {
min = n;}
exch(a, ii, jj);
}
}
}
return min;
}
//主函数
int main(int argc, const char * argv[]) {
int count;
int i;
float n,min =9999;
printf("请输入人数");
scanf("%d",&count);//获得人数
int a[count];//用count 省点空间
int weicount = 0;
for (i = 0; i < count; i++) {
scanf("%d",&a[i]);//逐个赋值
weicount += a[i];
}
float w = weicount/2.0;
for (i = count/2-1+count%2; i < count; i++) {
n = f1(a,count,i,w);
// printf("%.1f\n",n);
if (n < min) {
min = n;
}
if (n == 0) {
break;
}
}
// printf("一半重量%f\n",w);
// printf("最优组合重量%f",w-min);
int bb = w-min;
// 按照题目要求输出
printf("%d %d",bb,weicount-bb);
return 0;
}