一个数值中有若干正整数,将此数组划分为两个子数组,使得两个数组各元素之和a,b的差最小(12年上交CS复试题),大家怎么看呢..... |
[技术| 编程·课件·Linux] [12年上交CS复试题]一道算法设计题..........
ayann204
· 发布于 2013-01-21 15:37
· 1565 次阅读
转载文章时务必注明原作者及原始链接,并注明「发表于 软院网 RuanYuan.Net 」,并不得对作品进行修改。
本帖最后由 X1n4n 于 2013-1-21 17:09 编辑 sort A[1...n] // Now A[1] >= A[2] >= ... A[n] Array A1[] // 记录一部分 Array A2[] // 记录另一部分 sum_1 = 0 sum_2 = 0 j = k = 1 for(i = 1 ; i <= n ; i++) { if(sum_1 < sum_2) { A1[j++] = i sum_1 += A } else { A2[k++] = i sum_2 += A } } while(--j) print(A[A1[j]]) // 打印结果 while(--k) print(A[A2[k]]) // 打印结果 没试验~~不知道靠不靠谱. 第一感觉就是 排序然后 两个变量记录两个部分的和,如果哪一部分小就把剩余元素中最大的并到小的那个部分里。。如此循环 |
点评
评分
本帖最后由 yel_hb 于 2013-1-21 19:38 编辑 额...不是牛人的飘过... 随机取了6个数试了一下,先用DP求最大值,然后返回去构造选入的数,比较凌乱=_=!。 [C++] 纯文本查看 复制代码 #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <ctime> #include <minmax.h> using namespace std; int main() { int iput[6]; int i, j, v, n, sum; int *f; srand(time(NULL)); sum = 0; for ( i = 0; i < 6; ++i ) { iput[i] = rand() % 100 ; sum += iput[i]; printf( "%d ", iput[i] ); } printf( "\n" ); sort( iput, iput + 6 ); n = sum / 2; f = new int[n + 1]; memset( f, 0, sizeof(int) * ( n + 1)); for ( i = 0; i < 6; ++i ) for ( v = n; v >= iput[i]; --v ) f[v] = max ( f[v], f[v - iput[i]] + iput[i] ); j = f[n]; for ( i = 5; i >= 0; --i ) { if( f[j] == f[j - iput[i]] + iput[i] ) { printf("%d ", iput[i] ); j -= iput[i]; } } printf( "\n%d\n", sum - 2 * f[n] ); return 0; } |