做那道华为面试题 写了个递归 不会剪枝 求解

[anuan]

华为的题:

有两个序列a,b，大小都为n,序列元素的值任意整形数，无序；
要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。

我的解:

import random
a=[]
b=[]
for x in xrange(10):
a.append(int(random.random()*1000))
b.append(int(random.random()*1000))
print a
print b
#----------------------------------------------
#----------------------------------------------
#---------------------------------------------
a=a+b
half= sum(a)/2
s=0
p=[-1]
j=half
result=[]
count=0
def do(n,m,s,p):
if n==1:
for i in xrange(m):
_t=p[-1]+i+1
_k=abs(half-s-a[_t])
global j,result,count
count=count+1
if _k<j:
j=_k
result=p+[_t]
return
else:
for i in xrange(m):
_t=p[-1]+i+1
_s=s+a[_t]
_p=p+[_t]
do(n-1,m-i-1,_s,_p)

do(10,20,s,p)

print count
print j
l=[a[x] for x in result if x+1]
print l
print sum(l),sum(a)

现在问题是 count发现遍历次数多了一半 因为如果[1,3,5]计算了,那么[2,4,6]就应该不用计算 怎然剪掉

如果 我得到 j=0那就是所求的解 怎样跳出递归

[Rujia Liu]

现在问题是 count发现遍历次数多了一半 因为如果[1,3,5]计算了,那么[2,4,6]就应该不用计算 怎然剪掉

规定第1个元素一定在a里

如果 我得到 j=0那就是所求的解 怎样跳出递归

do函数返回一个标志表示是否已经找到完美解，所有do调用改成 if do(): return true
 

[victor lee]

动态规划啊。

2009/12/12 Rujia Liu <ruji...@gmail.com>

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:pyth...@googlegroups.com
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

[Rujia Liu]

题目说任意整形数，听上去是在暗示不要动态规划。。。。呵呵，不过也没说n很小就是了

2009/12/12 victor lee <victor...@gmail.com>

[yuting cui]

2009/12/12 Rujia Liu <ruji...@gmail.com>:
> 题目说任意整形数，听上去是在暗示不要动态规划。。。。呵呵，不过也没说n很小就是了
>
汗，怎么会有这种面试题...没碰到过这种问题不是会被活活害死...要先证明这个是个npc问题，然后才能知道别想啥可以多项式时间完成的精确解了...
--
-----BEGIN GEEK CODE BLOCK-----
Version: 3.12
G! d- s:->: a- C++(++++)$
UL++++ P L++(++++) E(++)
W+(+++) N+ o? K? w++(+++)
!O !M V? PS PE Y+ PGP !t
!5 !X R !tv b++ DI+ D+
G e* h+ r* y?
------END GEEK CODE BLOCK------

[anuan]

我知道了 改成都包含a[-1]
if n==1:
_k=abs(half-s-a[-1])

global j,result,count
count=count+1
if _k<j:
j=_k

result=p+[-1]
return

On Dec 12, 10:41 pm, yuting cui <yuting...@gmail.com> wrote:
> 2009/12/12 Rujia Liu <rujia....@gmail.com>:> 题目说任意整形数，听上去是在暗示不要动态规划。。。。呵呵，不过也没说n很小就是了

[anuan]

二楼的办法更好

这个算法本身就是 动态规划
题目里强调递归 是我想知道 当得到最优解(j==0)后 怎么中断递归
现在 只能在do():后面跟一句 if j==0 :return

ps:
随机20个数 能分成相等的两拨的概率有多大
我怎么每次都能得到 差为0的解

[yuting cui]

2009/12/13 anuan <anua...@gmail.com>:

> 二楼的办法更好
>
> 这个算法本身就是 动态规划
> 题目里强调递归 是我想知道 当得到最优解(j==0)后 怎么中断递归
> 现在 只能在do():后面跟一句 if j==0 :return
>
> ps:
> 随机20个数 能分成相等的两拨的概率有多大
> 我怎么每次都能得到 差为0的解
>
>

在整数范围大到一定程度的时候，这不是个动态规划就能变成多项式时间可解的（至少在P=NP没被证明的时候）...
另外，你的做法是强制变成1000以内了，对于20个数的序列来说，你需要一个循环更长（超过10^60）的伪随机数生成器才能保证各种分布都会出现

[Chen GUO]

老见人说“动态规划”，就是不知道具体怎么做了才算是动态规划。但是就这个题目：
已知：
a=[a0, a1, ..., a(n-1)]
b=[b0, b1, ..., b(n-1)]
1，构造：
c[n-1, n-1], c(i, j)=ai-bj
2，计算：
A=sigma(a)
B=sigma(b)
diff = A-B
3，求得c(i, j)，满足res=abs(c(i, j)-diff)最小，交换ai和bj，记录res
4，重复1-3，若求出的res比上一次的更大，则停止，上一次的结果就是解
大概其就是这么个思路，没仔细想，晚上回去好好考虑一下
俺从来只关心动词，不怎么留意名词，只记得怎么做，不知道这个方法叫什么名字，后来也确实吃了不少这个亏。比方某一次面试，被人问起“是否了解数据库设计的第三范式”，俺只好回答“不知道”，后来仔细一查书才知道，原来老子在实际项目里设计的第一个数据库，就几乎是完全遵循第三范式做的

[老光]

> 3，求得c(i, j)，满足res=abs(c(i, j)-diff)最小，交换ai和bj，记录res

这句首先要改：diff改为diff/2。

粗想了一下，楼上的不能得到正确答案。
比如以下面俩数组为例：
A = [13,20,11,51]
B = [8,26,17,44]
sum(A) = 95
sum(B) = 97
差值为2，用楼上解法，已经是最佳了。
但实际上，如果同时交换1，2两个数，则能使两个数组相等。

至此，我也很困惑：如果是1000个数的数组，难道要直到计算A，B各自任意500个数之和的差值为最小，才能得到准确答案？那解法就太耗时了！或者象楼主，直接把A,B对接起来，求2000个数中，每1000个数之和最接近M/2的和，然后去指定交换，但这是不是更违背题意？2000的阶剩个数组。。。太大了吧
是不是题意是只有对应位置的数才能交换？

另to某楼：要最后两个数组差解大一点，你初始化A的时候乘以1000，初始化B的时候剩以1000000嘛！

[yuting cui]

2009/12/14 老光 <yaogua...@cq.chinatelecom.com.cn>:

> 这句首先要改：diff改为diff/2。
>
> 粗想了一下，楼上的不能得到正确答案。
> 比如以下面俩数组为例：
> A = [13,20,11,51]
> B = [8,26,17,44]
> sum(A) = 95
> sum(B) = 97
> 差值为2，用楼上解法，已经是最佳了。
> 但实际上，如果同时交换1，2两个数，则能使两个数组相等。
>
> 至此，我也很困惑：如果是1000个数的数组，难道要直到计算A，B各自任意500个数之和的差值为最小，才能得到准确答案？那解法就太耗时了！或者象楼主，直接把A,B对接起来，求2000个数中，每1000个数之和最接近M/2的和，然后去指定交换，但这是不是更违背题意？2000的阶剩个数组。。。太大了吧
> 是不是题意是只有对应位置的数才能交换？
>
> 另to某楼：要最后两个数组差解大一点，你初始化A的时候乘以1000，初始化B的时候剩以1000000嘛！
>
>

这个是背包问题的特例，一样是np完全的，别想了...

[Chen GUO]

我开始也想过/2，但是后来觉得，确实需要计算所有的diff，因为不是对称的……正负有区别，区别在于A和B
如yuting所说，NPC级别，所以，没有正解，只有在一定概率下最接近的最优解

[Mu Qiao]

说一下我的拙见
用贪心可以比较容易的写出这个程序，但却是局部最优。
用DP可以按背包问题的思路去解，求出两个序列之和，用和的一半作为包的大小去装序列中的元素。具体的可以用其中一个序列作为包，每一步都要维护当前包的容量，只不过这个题目中，背包容量是可以溢出的，只要满足一个序列中的元素和最接近总和的一半，另一个序列就不用考虑了。当然可能还要考虑一些细节问题。这样应该可以求得最终结果。
还请大家指点

2009/12/15 Chen GUO <gcd...@gmail.com>

--
Best wishes,
Qiao Mu

[minglong yu]

说一下我的拙见，不知道可否？

首先通过标识每个元素，然后合并两个序列，再冒泡排序，然后同序列标识交换切割，切割成两个序列，这样就可以切割成两个差值最小的序列了

不知道我的想法错在什么地方

--
个人技术博客
http://www.vouov.com

[zeal]

贴一下我的代码，没有理论验证，欢迎大家指教。

#!/usr/bin/env python

# -*- coding: utf-8 -*-

import random

'''

经过分析发现，通过交换a,b序列中的元素得到的将的a,b序列，可以得到a+b序列的所有排列组合方式，

所以，以下分析将基于合并a,b序列得到c序列，然后将其拆分成a_new,b_new两个序列，并使用两序列间的差最小。

具体计算步骤如下：

1 合并a,b序列到c序列中

2 倒排序c序列，其中元素的大小为倒序，这是以下计算的基础

3 从c序列中移出第一个元素（最大的元素），放置到a_new序列中

4 循环比较a_new和b_new序列的总和大小，将c序列中的第一个元素移至较小的序列中

5 循环至a_new或b_new序列的长度为c序列长度的一半结束

6 将c序列中的剩余元素放至a_new和b_new序列中长度较小的序列中

7 比较a_new和b_new之间的差

'''

#随机数初始化a和b序列

a=[]

b=[]

for x in xrange(10):

   a.append(int(random.random()*1000))

   b.append(int(random.random()*1000))

print a

print b

#合并a和b序列至c序列中，并倒序排列

c = []

c.extend(a)

c.extend(b)

c.sort()

c.reverse()

#定义a_new和b_new序列，用于存放交换后的新序列

new_length = len(c)/2

a_new = [c[0]]

a_count = c[0]

b_new = []

b_count = 0

c.remove(c[0])

#循环添加c序列中的元素至a_new和b_new序列中（算法见描述）

while(new_length>len(a_new) and new_length>len(b_new)):

    if a_count<b_count:

        a_new.append(c[0])

        a_count += c[0]

    else:

        b_new.append(c[0])

        b_count += c[0]

    c.remove(c[0])

if len(a_new)<len(b_new):

    a_new.extend(c)

else:

    b_new.extend(c)

#打印运算结果

print a_new,'\tNew Array A'

print b_new,'\tNew Array B'

print abs(a_count-b_count),'\tdiff'

print a_count,'\tsum(new_a)'

print b_count,'\tsum(new_b)'

#如果需要计算元素交换的次数，需要进行额外计算

[wenfeng wang]

不错 参考答案的算法

[Xi Shen]

2009/12/31 zeal <snow31...@gmail.com>:

> --
> 来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:pyth...@googlegroups.com
> 退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
> 详情: https://groups.google.com/group/python-cn
> 严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

这个算法只是把所有的数交替的放到两个数组里吧。假设a,b如下：
a=[100,1]
b=[2,3]

合并，排序后的数组是：
c=[100,3,2,1]

按你的算法交替的放到两个数组里，结果是：
a=[3,1]
b=[100,2]

sum(b)-sum(a) = 98

但正确的结果应该是：
a=[100]
b=[1,2,3]

sum(a)-sum(b) = 94

解这个题的关键是考察数组元素和的值，不是数组元素的个数。

--
Best Regards,
David Shen

http://twitter.com/davidshen84/
http://meme.yahoo.com/davidshen84/

[Jacques Dong]

> 这个算法只是把所有的数交替的放到两个数组里吧。假设a,b如下：
> a=[100,1]
> b=[2,3]
>
> 合并，排序后的数组是：
> c=[100,3,2,1]
>
> 按你的算法交替的放到两个数组里，结果是：
> a=[3,1]
> b=[100,2]
>
> sum(b)-sum(a) = 98
>
> 但正确的结果应该是：
> a=[100]
> b=[1,2,3]
>
> sum(a)-sum(b) = 94
>
>
> 解这个题的关键是考察数组元素和的值，不是数组元素的个数。

原题要求的是任意交換a, b两个序列， zeal 的解法没错

[Jacques Dong]

2010/1/9 Jacques Dong <jacqu...@gmail.com>:

>> 这个算法只是把所有的数交替的放到两个数组里吧。假设a,b如下：
>> a=[100,1]
>> b=[2,3]
>>
>> 合并，排序后的数组是：
>> c=[100,3,2,1]
>>
>> 按你的算法交替的放到两个数组里，结果是：
>> a=[3,1]
>> b=[100,2]
>>
>> sum(b)-sum(a) = 98
>>
>> 但正确的结果应该是：
>> a=[100]
>> b=[1,2,3]
>>
>> sum(a)-sum(b) = 94

交换后，应该是
a = [100, 1]
b = [3, 2]

>>
>>
>> 解这个题的关键是考察数组元素和的值，不是数组元素的个数。

照你的思路， 如果只是要 a, b 差异最小 而不管两个序列的个数，就没什么难度了。

[yuting cui]

2010/1/9 Jacques Dong <jacqu...@gmail.com>:

>
> 照你的思路， 如果只是要 a, b 差异最小 而不管两个序列的个数，就没什么难度了。
>

...请想在这个主题下发布新的解法的同学看看
http://en.wikipedia.org/wiki/Partition_problem
如果在看完之后还能确定自己的解法是多项式时间下的最优解，那么快去申请图灵奖吧