原我犯了很多数人一样的错误
主观一定认为最大的两个数一定要分开
[ 本帖最后由 lih928 于 2006-11-17 16:46 编辑 ]
原帖由 xmyth 于 2006-11-14 17:04 发表
当前数组a和数组b的和之差为
A = sum(a) - sum(b)
a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a + b - (sum(b) - b + a)
= sum(a) - sum(b) - 2 (a - b) ...
当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，x越接近A/2效果越好, 如果找不到在(0,A)之间的x，则当前的a和b就是答案。
当这样的X不存在时，并不能结束算法。还可能存在如下情形，可以得到更小的差值：
例如： A=｛3， 5， 6， 7， 13， 14｝
B=｛1， 3， 7， 8， 10， 17｝
此时有，sum(A) - sum(B) = 2 ，并且不存在（0， 2）之间的x值。
但将A中的5和6与B中的3和7同时交换，得到
A=｛3， 3， 7， 7， 13， 14｝
B=｛1， 5， 6， 8， 10， 17｝
此时有：sum(A) - sum(B) = 0，此时的数组才是解。
我觉得这个算法难在如何有效寻找a(i)]和b上
[ 本帖最后由 tyc611 于 2006-11-17 23:54 编辑 ]
>为啥上边的回复后部分斜了呢
知道了，原来是a中的在作祟:em02:
[ 本帖最后由 tyc611 于 2006-11-17 23:58 编辑 ]
建2各数组,把那些数从大到小,分别放入数组就成把. 放的时候判断一下就行了.
if (sum(a)>sunm(b))
a.push_back(num)
else
b.push_back(num)
xmyth 兄从事什么专业?
能够快速的把实际问题模式化,并行成正确的数学思维,论证严谨.
而且整个模型具有智能的味道,佩服佩服
令我收益非浅那~~:em05:
int abs(int n)
{
return n >= 0 ? n : -n;
}
int sum(int *array, int count)
{
int sum = 0;
for (int i = 0; i < count; i++)
sum += array;
return sum;
}
void exchange(int *array1, int *array2, int count)
{
int sum1 = sum(array1, count);
int sum2 = sum(array2, count);
if (sum1 == sum2)
return;
int diff = abs(sum1 - sum2);
for (int i = 0; i < count; i++) {
for (int j = 0; j < count; j++) {
int s1 = sum1 + array2 - array1;
int s2 = sum2 + array1 - array2;
if (abs(s1 - s2) < diff) {
int tmp = array1;
array1 = array2;
array2 = tmp;
sum1 = s1;
sum2 = s2;
diff = abs(sum1 - sum2);
if (diff == 0)
return;
}
}
}
}
[ 本帖最后由 svenwang 于 2006-11-17 23:41 编辑 ]
先把数据放到一个临时数组中，排序且求和sum；用背包算法，尽量是一个数组大小为n的存放的数字和为sum／2
原帖由 slsl8460 于 2006-11-17 19:09 发表
先把数据放到一个临时数组中，排序且求和sum；用背包算法，尽量是一个数组大小为n的存放的数字和为sum／2
原题说了数组里面元素的值任意，背包算法的效率线性于最大容积K，这里就是sum/2，如果这个数字可以任意，那背包算法也没什么意义了。
关注．．．．
搞一个数组C 包含了全部ab的数据 并排序（再生成C的时候就排序）
然后在C里面选1个 放到A第2n个放到B第2个放到A第2n-1个放到B。。。。。。。
[ 本帖最后由 geba168 于 2006-11-18 22:23 编辑 ]