以前的一个面试题,当时没答上.
题目:
有2N个学生,现在要将这2N个学生分到A班,B班.
要求:
A班与B班的学生人数要一样.
两个班学生分数总和要相差最小.
问怎么分配学生.
题目:
有2N个学生,现在要将这2N个学生分到A班,B班.
要求:
A班与B班的学生人数要一样.
两个班学生分数总和要相差最小.
问怎么分配学生.
解决方案
20
第一种方法，似乎是背包
20
先排序，
排序从大到小 n[2N]
从0到结束
sum B > sum A && count A < N
把n[i] 放入 A ，更新 sum ,count
Else
放入 B ，更新 B sum , count
排序从大到小 n[2N]
从0到结束
sum B > sum A && count A < N
把n[i] 放入 A ，更新 sum ,count
Else
放入 B ，更新 B sum , count
20
看了下各楼的回复。本人本人总结了个想法，经过手动举例验证还是不对的，先想到这里了，先贴出来。
（1）求出2N个同学成绩的平均值，记为变量average；
（2）对2N个铜须的成绩进行排序，从小到大，和从大到小都可以；
（3）选出2N个数（2N个同学的的成绩），离平均值最近的两个数，例如说是x1，x2。
把x1,x2任意分配到对应的A班和B班，例如分数为x1对应的同学分到A班，分数为x2对应的同学分配到B版。
（4）选出距离平均值第二近的两个数，例如说是y1,y2。A班的成绩记为sumA，B班的成绩记为sumB。
假如把y1分配到A班，则A班现在的成绩是sumA = x1 + y1，B班现在的成绩是sumB = x2 + y2;
假如把y2分配到A班，则A班现在的成绩是sumA = x1 + y2，B班现在的成绩是sumB = x2 + y1;
（1）求出2N个同学成绩的平均值，记为变量average；
（2）对2N个铜须的成绩进行排序，从小到大，和从大到小都可以；
（3）选出2N个数（2N个同学的的成绩），离平均值最近的两个数，例如说是x1，x2。
把x1,x2任意分配到对应的A班和B班，例如分数为x1对应的同学分到A班，分数为x2对应的同学分配到B版。
（4）选出距离平均值第二近的两个数，例如说是y1,y2。A班的成绩记为sumA，B班的成绩记为sumB。
假如把y1分配到A班，则A班现在的成绩是sumA = x1 + y1，B班现在的成绩是sumB = x2 + y2;
假如把y2分配到A班，则A班现在的成绩是sumA = x1 + y2，B班现在的成绩是sumB = x2 + y1;
假如((x1 + y1) – (x2 + y2))的绝对值 > ((x1 + y2) – (x2 + y1))的绝对值，则将分数y2对应的同学分配到A班，分数y1对应的同学分配到B班。
这样保证每班两个同学时，分数总和的差距是最小的。
（5）以此类推，保证每班多分一个学生时，分数总和的差距都是最小。
举个最简单的实例：4个同学（2N中的N=2），成绩分别是60,55,80,78。
（1）平均值是68.25；
（2）排序结果是55,60,78,80;
（3）离平均值最近的两个数是60,78; 60对应的同学分到A班，78对应的同学分到B班；
（4）距离平均值第二近的两个数是55,80。|(60+55)-(78+80)| > |(60+80)-(78+55)|，
故将55,78的同学分到A班，60,80的同学分到B班，这样成绩总差为7是最小的。
但是（60 + 78） – （55 + 80） = 3，将60,78的同学分到A班，55,80的同学分配到B班分数差才是最小的……
所以最开始将60和78分开就是个bug……
10
两个班总分之差最小,即两个班总分都是接近(全部学生成绩总分和)/2,然后贪心
10
仅供参考：
//给出12个随机数,分成三组求和,每组的个数不定,要求求出来的三个数之间相差最小,最完美的情况是三个数相等.
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <limits.h>
int i,j,k;
int g[12][3]={//可能的分组大小
{ 1, 1,10},
{ 1, 2, 9},
{ 1, 3, 8},
{ 1, 4, 7},
{ 1, 5, 6},
{ 2, 2, 8},
{ 2, 3, 7},
{ 2, 4, 6},
{ 2, 5, 5},
{ 3, 3, 6},
{ 3, 4, 5},
{ 4, 4, 4},
};
int n[12];
int m[12];
int f[12];//当前最小时各数
int g1,g2,g3;//1,2,3组可分配的个数
int n1,n2,n3;//1,2,3组已分配的个数
int f1,f2;//当前最小时1,2组的个数
int s1,s2,s3;//123组的和
int d;//1-2,2-3,3-1组中各数和之间差的绝对值之和
int dmin=INT_MAX;//保存当前d的最小值
void swap(int *pi1,int *pi2) {
int t;
t=*pi1;*pi1=*pi2;*pi2=t;
}
void test() {
s1=0;
for (i=0;i<g1;i++) s1=s1+n[i];
s2=0;
for (i=g1;i<g1+g2;i++) s2=s2+n[i];
s3=0;
for (i=g1+g2;i<12;i++) s3=s3+n[i];
d=abs(s1-s2)+abs(s2-s3)+abs(s3-s1);
if (d<dmin) {
dmin=d;
f1=g1;
f2=g2;
for (i=0;i<12;i++) f[i]=n[i];
printf("(");
for (i=0;i<g1;i++) printf("%2d,",n[i]);
printf(") (");
for (i=g1;i<g1+g2;i++) printf("%2d,",n[i]);
printf(") (");
for (i=g1+g2;i<12;i++) printf("%2d,",n[i]);
printf(") %4d\n",dmin);
} else {
printf("(");
for (i=0;i<g1;i++) printf("%2d,",n[i]);
printf(") (");
for (i=g1;i<g1+g2;i++) printf("%2d,",n[i]);
printf(") (");
for (i=g1+g2;i<12;i++) printf("%2d,",n[i]);
printf(") %4d\n",d);
}
}
void main() {
srand(time(NULL));
for (i=0;i<12;i++) m[i]=rand()%100;
for (i=0;i<12;i++) printf("%2d,",m[i]);
printf("\n");
for (i=1;i<12;i++) {
for (j=0;j<i;j++) {
if (m[i]>m[j]) swap(&m[i],&m[j]);//冒泡排序从大到小
}
}
for (i=0;i<12;i++) printf("%2d,",m[i]);
printf("\n");
for (k=0;k<12;k++) {//在12种分组方法中
//取第i种分组方法
g1=g[k][0];
g2=g[k][1];
g3=g[k][2];
printf("%2d-%2d,%2d,%2d\n",k,g1,g2,g3);
//将从大到小12个数双向轮流分配到三个组中
n1=0;
n2=0;
n3=0;
for (j=0;j<12;j++) {
switch (j%6) {
case 0:
redo:
if (n1<g1) {
n[n1]=m[j];
n1++;
break;
}
case 1:
if (n2<g2) {
n[g1+n2]=m[j];
n2++;
break;
}
case 2:
if (n3<g3) {
n[g1+g2+n3]=m[j];
n3++;
break;
}
case 3:
if (n3<g3) {
n[g1+g2+n3]=m[j];
n3++;
break;
}
case 4:
if (n2<g2) {
n[g1+n2]=m[j];
n2++;
break;
}
case 5:
if (n1<g1) {
n[n1]=m[j];
n1++;
break;
}
default:goto redo;
}
}
test();
}
printf("--\n");
g1=f1;
g2=f2;
for (i=0;i<12;i++) n[i]=f[i];
printf("(");
for (i=0;i<g1;i++) printf("%2d,",n[i]);
printf(") (");
for (i=g1;i<g1+g2;i++) printf("%2d,",n[i]);
printf(") (");
for (i=g1+g2;i<12;i++) printf("%2d,",n[i]);
printf(") %4d\n",dmin);
}
10
本人的思路
1， 先算平均值 av
2， 各个分数 – av 得到 差值 var
3， 设置2个Flag ， FlagA = FlagA + var , FlagB = FlagB + var
4， 在var list中取得值，是FlagA 和FlagB 都接近于0.
1， 先算平均值 av
2， 各个分数 – av 得到 差值 var
3， 设置2个Flag ， FlagA = FlagA + var , FlagB = FlagB + var
4， 在var list中取得值，是FlagA 和FlagB 都接近于0.
20
这是个0/1背包问题，可以用动态规划搞，看这里
http://blog.csdn.net/pegasuswang_/article/details/25081783
http://blog.csdn.net/pegasuswang_/article/details/25081783
100
