关于java 问题，是一道面试题，要用算法去实现的，求帮忙看看

Question

面试官问我：我有100块质量有可能相同，也有可能不同的小石头，你怎么分两部分，让这两部分质量相差最近？？要考虑好各种情况，比如，有可能1-98，质量非常小，而后两个质量非常大！ 面试官当着我的面问的，不是做题，他就在我旁边让我回答。

Answer 1

先将石头按质量从大到小放到数组stone[0]~stone[99]中。然后对A、B两个组按贪心法进行选择：1、让A先取；2、循环进行剩下的99次选取，每次选取时，总重量小的具有选取权。具体过程描述可如下：//前提条件：数组stone中从大到小存放了100个数。list listA, listB;list *p;listA.Insert(stone[0]);for(int i = 1; i < 100; i++) {p = listA.Sum( ) < listB.Sum( ) ? &listA : &listB;*p.Insert(stone[i]);}

Answer 2

这是一个典型的动态规划里面的数组分割问题。给你找出来一个可以作为类比的题目，其实实质是一模一样的：题目概述：有一个没有排序，元素个数为2N的正整数数组。要求把它分割为元素个数为N的两个数组，并使两个子数组的和最接近。假设数组A[1..2N]所有元素的和是SUM。模仿动态规划解0-1背包问题的策略，令S(k, i)表示前k个元素中任意i个元素的和的集合。显然：S(k, 1) = {A[i] | 1<= i <= k}S(k, k) = {A[1]+A[2]+…+A[k]}S(k, i) = S(k-1, i) U {A[k] + x | x属于S(k-1, i-1) }按照这个递推公式来计算，最后找出集合S(2N, N)中与SUM最接近的那个和，这便是答案。这个算法的时间复杂度是O(22N).因为这个过程中只关注和不大于SUM/2的那个子数组的和。所以集合中重复的和以及大于SUM/2的和都是没有意义的。把这些没有意义的和剔除掉，剩下的有意义的和的个数最多就是SUM/2个。所以，我们不需要记录S(2N,N)中都有哪些和，只需要从SUM/2到1遍历一次，逐个询问这个值是不是在S(2N,N)中出现，第一个出现的值就是答案。我们的程序不需要按照上述递推公式计算每个集合，只需要为每个集合设一个标志数组，标记SUM/2到1这个区间中的哪些值可以被计算出来。关键代码如下：for(i = 0; i < N+1; i++)for(j = 0; j < sum/2+1; j++)flag[i][j] = false;flag[0][0] = true;for(int k = 1; k <= 2*N; k++) {for(i = k > N ? N : k; i >= 1; i--) {//两层外循环是遍历集合S(k,i)for(j = 0; j <= sum/2; j++) {if(j >= A[k] && flag[i-1][j-A[k]])flag[i][j] = true;}}}for(i = sum/2; i >= 0; i--) {if(flag[N][i]) {cout << "minimum delta is " << abs(2*i - sum) << endl;break;}}