- 论坛徽章:
- 0
|
个人认为在8分钟内想出一个动态规划或者是其他方案的算法不现实，毕竟还要写出代码。
我认为一种可行的方案是使用组合，对于A、B数组中的数据存放在一个数组Data中，假设两个数组各有NUM个元素。那么我们在Data数组中选择有NUM个元素的所有情况（使用组合代数），计算选出子数组的和与未选数据的和之间的差值。记录最小差值的情况，然后显示之。
当然，这种方案显然不是最优解，但是确实有个可行的方案。（其实，我认为即使使用该方案在8分钟内实现C代码也是不现实的，除非是伪代码）
下面给出该实现：
#include <stdio.h>
#include <stdlib.h>
#define NUM 10
int A[NUM] = {11, 20, -3, 123, 18, 19, 171, 19, 123, 10};
int B[NUM] = {1, 23, 19, 41, 39, 123, 190, 238, 179, 25};
int Data[NUM*2]; // 包含了数组A和B中的所有元素
int Data_inc[NUM]; // 保存了从Data数组中选出的NUM个元素
int Data_temp[NUM]; // 记录了当前能产生差值最小情况的NUM个元素
void Print(int *a, int n){
int i;
for(i=0;i<n;++i)
printf("%d ",a[i]);
printf("\n");
}
int get_sum(int *a, int n){
int sum,i;
for(sum=0,i=0;i<n;i++)
sum += a[i];
return(sum);
}
static int diff = 0; // 保存了当前的最小差值
static int counter = 0;
void Handle(int sum){
int sum0, sum1, i;
sum0 = get_sum(Data_inc, NUM);
sum1 = sum - sum0;
if(counter==0 || diff > abs(sum0-sum1)){
diff = abs(sum0-sum1);
for(i=0;i<NUM;i++)
Data_temp[i] = Data_inc[i];
}
counter++;
}
void Com(int n, int m, int sum){ // 使用组合算法从Data数组中选出NUM个元素保存在Data_inc数组中
int i;
for(i=n;i>=m;--i){
Data_inc[m]=Data[i];
if(m>0)
Com(i-1,m-1, sum);
else
Handle(sum);
}
}
int main()
{
int i;
for(i=0;i<NUM*2;i++)
if(i<NUM)
Data[i] = A[i];
else
Data[i] = B[i-NUM];
printf("Sum in A: %d, Sum in B: %d\n", get_sum(A, NUM), get_sum(B, NUM));
Print(Data, NUM*2);
Com(NUM*2-1,NUM-1, get_sum(Data, NUM*2));
Print(Data_temp, NUM);
printf("Diff Value is %d. \n", diff);
return 0;
}
|
[ 本帖最后由 BillStone 于 2009-6-17 21:59 编辑 ] |
|
免费注册
楼主: forrestgang
发表于 2009-06-15 22:36
