输入十个数(int型), 把这十个数分两组A和B,A组数的和为sum1,B组数的和为sum2,问怎样分,可使sum1和sum2相差最小。
讨论一下解题思路。
比如:
90 25 65 30 58 268
70 28 60 40 55 253 差15
90 25 60 30 55 260
70 28 65 40 58 261 差1
我有一种想法,不知道是否正确:
按顺序找出每整数及其相差绝对值最小的整数,让它们配对。
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#define MAX 10
#define GREATEST 858993460
typedef struct
{
int elem;
bool used;
}Number;
void Choose(Number *num, int *agroup, int *bgroup)
{
int n = 0,a = 0, b = 0;
int finish = 0;
int compare;
int id;
int length = MAX;
int halfLength = length/2;
do
{
if(!num[n].used)
{
num[n].used = true;
compare = GREATEST;
agroup[a] = num[n].elem;
a++;
for(int i = n + 1; i < length; i++)
{
int com = num[n].elem - num[i].elem;
com = (com < 0)?(-com):com;
if(compare > com)
{
compare = com;
id = i;
}
}
num[id].used = true;
bgroup[b] = num[id].elem;
b++;
}
n++;
finish++;
}
while(finish <= halfLength);
}
void main()
{
Number *num = new Number[MAX];
int *a = new int[MAX/2];
int *b = new int[MAX/2];
srand( (unsigned) time(NULL));
for(int i = 0; i < MAX; i++)
{
num[i].elem = rand()%100;
num[i].used = false;
}
Choose(num, a, b);
cout<<"the result is:"<<endl;
cout<<"a : ";
for(i = 0; i < MAX/2; i++)
cout<<" "<<a[i]<<" ";
cout<<endl<<"b : ";
for(i = 0; i < MAX/2; i++)
cout<<" "<<b[i]<<" ";
}
垃圾代码 凑合这看吧
#include<iostream.h>
#include<math.h>
void f1(int a[])/*排序*/
{
for(int i=0;i<10;i++)
for(int j=i;j<10;j++)
if(a[i]>a[j+1]){int temp=a[i];a[i]=a[j+1];a[j+1]=temp;}
}
main()
{
int a[10],A[5],B[5],p1=0,p2=0,x=0,i;
for(i=0;i<10;i++)
cin>>a[i];
f1(&a[0]);
for(i=0;i<10;i=i+2)
if(abs((p1+a[i])-(p2+a[i+1]))<=abs((p1+a[i+1])-(p2+a[i])))/*比较差值大小*/
{p1=p1+a[i];p2=p2+a[i+1];A[x]=a[i];B[x++]=a[i+1];}/*进行赋值*/
else
{p1=p1+a[i+1];p2=p2+a[i];A[x]=a[i+1];B[x++]=a[i];}/*进行赋值*/
for(i=0;i<5;i++)/*输出*/
cout<<A[i]<<' ';
cout<<p1<<"\n";
for(i=0;i<5;i++)
cout<<B[i]<<' ';
cout<<p2<<"\n";
}