int dist = 0;
int temp = 0;
for( int i=0; i<N; i++){
if( abs(dist+A-B) < abs(dist+B-A) ){
dist += A-B;
}else{
change(A,B);
dist += A-B;
}
}
说明：上述程序的目标是使交换后A数组的和减去B数组的和的绝对值最小，也就是两者之间相差最少
最终dist保存的即为两者之间的差
我就写了个例子验证了一下上述程序
A：2 4 5 8
B：1 7 6 9
按照上述规则，交换5-6，8-9，最终dist==0
如有错误请大家指出
[ 本帖最后由 dark_ql 于 2006-11-18 23:59 编辑 ]
这个帖子有点无聊了。很多人都只看第一贴，自己重复了别人的错误还不知道。
要是说是微软面试题估计更火爆。
没想出好的算法 我的思路把2n个数放在一个数组里 然后用组合找出n个数 求和 另n个数也求和 做查
求出所有这样的差值的最小值，故复杂度为theta（ C(2n, n)）再把原数组的值经过有限次的交换 调整成最优解的数组值就行了
其中C(2n, n)用的是回溯 构架是
void select_combination(int l, int p)
{
int i;
if (l == n)
{
。。。
return;
}
for(i=p; i<=2*n-(n-l); ++i) //上个位置填的是num，本次从num开始试探
{
b = true;
select_combination(l+1, i+1); //填下一个位置
b = false;
}
}
下面是整个程序
#include <stdio.h>
#include <math.h>
const int n = 3;
int num;
bool b;
bool bc;
bool first = true;
int de, sumae, sumbe;
int mins;
void copy(bool p[], bool q[], int n)
{
for (int i = 0; i < n; ++i)
{
q = p;
}
}
void select_combination(int l, int p)
{
int i;
if (l == n)
{
int suma = 0, sumb = 0;
for (i=0; i<2*n; ++i)
{
if (b)
suma += num;
else
sumb += num;
}
if (first)
{
first = false;
mins = abs(suma - sumb);
de = mins;
sumae = suma;
sumbe = sumb;
}
else
{
int d = abs(suma - sumb);
if (d < mins)
{
mins = d;
copy(b, bc, 2*n);
de = mins;
sumae = suma;
sumbe = sumb;
}
}
return;
}
for(i=p; i<=2*n-(n-l); ++i) //上个位置填的是num，本次从num开始试探
{
b = true;
select_combination(l+1, i+1); //填下一个位置
b = false;
}
}
bool find(int a[], int n, int va, int& pos)
{
for (int i = 0; i < n; ++i)
{
if (va == a)
{
pos = i;
return true;
}
}
return false;
}
void swap(int& a, int& b)
{
int tem = a;
a = b;
b = tem;
}
int main()
{
int a = {1,4, 7};
int c = {2,5,12};
int i, suma = 0, sumc = 0;
for (i = 0; i < 2*n; ++i)
{
if (i < n)
{
num = a;
suma += a;
}
else
{
num = c;
sumc += c;
}
b = false;
}
select_combination(0, 0);
// 下面是追踪交换的顺序
int ac, cc, p = 0, q = 0;
for (i = 0; i < 2*n; ++i)
{
if (bc)
ac = num;
else
cc = num;
}
p = 0;
int pos;
// 使a中的值与ac中的值相同
while (p < n)
{
if (a == ac)
{
++p;
continue;
}
else
{
if (find(c, n, ac, pos))
{
printf("swap %d in a[%d] and %d in c[%d]\n",
a, p, c,pos);
swap(a, c);
}
// a 一定在数组a里 需交换3次
else
{
find(a, n, ac, pos);
printf("swap %d in a[%d] and %d in c[%d]\n",
a, p, c,0);
swap(a, c);
printf("swap %d in a[%d] and %d in c[%d]\n",
a, pos, c,0);
swap(a, c);
printf("swap %d in a[%d] and %d in c[%d]\n",
a, p, c,0);
swap(a, c);
}
}
++p;
}
// 使c中的值与cc中的值相同
q = 0;
while (q < n)
{
if (c == cc)
{
++q;
continue;
}
else
{
find(c, n, cc, pos);
printf("swap %d in c[%d] and %d in a[%d]\n",
c, q, a,0);
swap(c, a);
printf("swap %d in c[%d] and %d in a[%d]\n",
c, pos, a,0);
swap(c, a);
printf("swap %d in c[%d] and %d in a[%d]\n",
c, q, a,0);
swap(c, a);
}
++q;
}
printf("\n交换前suma: %d, sumb: %d\n", suma, sumc);
printf("交换后suma: %d, sumb: %d\n", sumae, sumbe);
return 0;
}
原帖由 mike_chen 于 2006-11-13 09:34 发表
放到一个临时数组里排序后，两头取，分别存在a,b里
我同意这个
你们还在讨论这个问题呢...题说交换，又没说要给出交换的过程。。所以完整程序很简单......变个思维想想么
呵呵
另外，xmyth 的算法是基于贪心的，所以并不是最优的，只不过大多时候是最优的而已
再罗嗦点.....认清此题问题本是NP问题，就不会去想一些自以为很好的算法了
老老实实回朔剪枝吧，此题剪枝才是优化的王道，目前我用了3处剪枝已经将速度加速了很多
比较遗憾的是题目没给n范围，所以不好考虑剪枝的代价，所以我认为不给出n的规模此题写起来没什么意义，
所以代码也就不贴了。。。。
参加tyc611 的帖子
发现xmyth算法的模型还是有问题，如tyc611的例子，同时交换不能只限于一个元素
我的想法：
也许可以拓展成只要找到x在(0, A], 合集，不是开集，就进行交换
例子如下：
3,5,6,7,13,14 sum = 48
1,3,7,8,10,17 sum = 46
因为a - b = 2,在(0, 2]之间, 且没有更逼近于A/2的选择，故交换之
3,3,7,8,10,17 sum = 48
1,5,6,7,13,14 sum = 46
现在a - b = 1, 在(0,2]之间， 交换
3,3,6,8,10,17 sum = 47
1,5,7,7,13,14 sum = 47
得到最佳结果
我前面提出的算法的确是错误的，贪婪算法在这种情况下不可行。
而楼上的想法也是错误的，比如这个简单的例子就行不通了
a = {11,12,8,91}
b = {1,2,17,100}
动态规划算法对这个题目应该是适用的
该题等价于在2n中元素中选取n个元素，使得这n个元素的和最接近于2n个元素总和的一半
/*
* 在数组c中的n个元素中选取m个元素，使得这m个元素的和最接近y
* func(c, n, m, y) 就表示这m个元素的和
* 然后通过比较func(c, n, m, y) 和 func(c + 1, n - 1, m, y) 就可以确定选取的这m个元素是哪几个
*/
func(int *c, int n, int m, int y) {
if (m == 0)
return 0;
if (n == m)
return sum(c, n);
a = func(c + 1, n - 1, m, y);
b = func(c + 1, n - 1, m - 1, y - *c) + *c;
return abs(y - a) <= abs(y - b) ? a:b;
}
[ 本帖最后由 xmyth 于 2006-11-21 21:01 编辑 ]