数组处理效率问题

zp307300084

a和b数组元素互换，交换后a数组相加值和b数组相加值为组合最小值

下面是我网上借鉴的代码，不过基本没有什么效率，大家能看出哪出了问题不？

新写一个也行？


# -*- coding: cp936 -*-
def  minus(total):
    n = len(total)/2
    a = total[:n]
    b = total[n:]
    return abs(sum(a) - sum(b)),a,b

def func(total,k):
    mi,am,bm = minus(total)
    global minSN,an,bn
    if mi< minSN:
        minSN = mi
        an,bn = am,bm
    for i in range(k,len(total)):
        total[k],total[i] = total[i],total[k]
        func(total,k+1)
        total[k],total[i] = total[i],total[k]   
   
if __name__ == '__main__':
    a = [1,2,3,4]
    b = [6,7,8,9]
    an,bn = a[:],b[:]
    total = a + b
    minSN,am,bm = minus(total)
    func(total,0)
    print an
    print bn
    print  minSN

Hadron74

回复 1# zp307300084

这个疑似是我以前贴的一个程序，呵呵！

现在我有了一个更好的方法，用0-1背包问题来解决这个问题。思路是，给一个总和长的select数组，记录a/b的状态，True表示在a中，False表示在b中。
用递归遍历所有选取n个元素在a中的可能，就遍历了所有可能的交换。这个算法的复杂度小于O（2^(2n)).

其算法可以参考http://www.cnblogs.com/Myhsg/archive/2009/08/29/1556460.html

下面是代码

1. def  minus():
   
2.     global total,select,number
   
3.     a = [ total[i] for i in range(number) if select[i] ]
   
4.     b = [ total[i] for i in range(number) if not select[i] ]
   
5.     return abs(sum(a) - sum(b)),a,b
   
6. 
   
7. def func(sumN,k):
   
8.     global select,number,halfnumber,minSN,an,bn
   
9.     if k==number:
   
10.         return
    
11.     if sumN == halfnumber:
    
12.         mi,am,bm = minus()
    
13.         if mi< minSN:
    
14.             minSN = mi
    
15.             an,bn = am,bm
    
16.         return
    
17.     select[k] = True
    
18.     func(sumN+1,k+1)
    
19.     select[k] = False
    
20.     func(sumN,k+1)
    
21.    
    
22. if __name__ == '__main__':
    
23.     a = [1,2,3,4]
    
24.     b = [6,7,8,9]
    
25.     total = a + b
    
26.     an, bn = a[:], b[:]
    
27.     minSN = abs(sum(a)-sum(b))
    
28.     number = len(total)
    
29.     halfnumber = number/2
    
30. 
    
31.     select = map(lambda x: False,total)
    
32. 
    
33.     func(0,0)
    
34. 
    
35.     print minSN
    
36.     print an
    
37.     print bn
    

复制代码

结果：

1. 0
   
2. [1, 4, 7, 8]
   
3. [2, 3, 6, 9]

复制代码

linux_c_py_php

这是《编程之美》上的DP问题，思路非常新颖。

DP的两个维度分别是sum和num_of_elems_in_set.

Hadron74

回复 3# linux_c_py_php

没有这本书，你能不能贴个程序上来，大家看看。谢谢！


   

linux_c_py_php

别让我写算法了, 放下好久了.

DP原理: bool dp[sum][num]; 表示num个数字能否加和等于sum. 实现是外层依次遍历所有元素, 将每个元素将入到之前的dp组合考虑中, 很像Floyd的三层循环DP, 可以体会一下.

编程之美里的讲解是逐层深入的, 先从普通的递推枚举方法, 最后演变到DP, 以前上学时读的书, 启发是蛮大的.

Hadron74 发表于 2012-09-12 19:21
回复 3# linux_c_py_php

没有这本书，你能不能贴个程序上来，大家看看。谢谢！

Hadron74

回复 5# linux_c_py_php


    回复 3# linux_c_py_php

谢谢你的建议的书，我在网上下了拜读了，贴在这里。并附上我写的程序。原书中的解法只对正整数，且有一点小问题。
我改正了错误，并把它推广到了支持负数的问题。

1. if __name__ == '__main__':
   
2.     a = [1,2,3,44]
   
3.     b = [6,7,8,-9]
   
4.     total = a + b
   
5. 
   
6.     minAB = min(a+b)
   
7.     modcut = max([0,-minAB+1]) # Deal with negative numbers by add a minmum negive number
   
8. 
   
9.     halfSumAll = (sum(total)+(modcut)*len(total))/2
   
10.     modifyTotal = [ modcut + i for i in total] # Motify numbers to all positive
    
11.     n = len(total)/2
    
12. 
    
13.     isOK=[]
    
14.     for i in range(halfSumAll+1):
    
15.         isOK.append([None for i in range(n+1)])
    
16.     isOK[0][0]=set()
    
17. 
    
18.     from pprint import pprint
    
19.     for k in range(1,len(total)+1):
    
20.         value = modifyTotal[k-1]
    
21.         truevalue = total[k-1]
    
22.         for i in range(min(n,k),0,-1): # Should from Max to minum to avoid calulate a k for twice in one run
    
23.             for v in range(value,halfSumAll+1): # to cut value to select larger v to calulate
    
24.                 if isOK[v-value][i-1] is not None:
    
25.                     isOK[v][i] = set(isOK[v-value][i-1])
    
26.                     isOK[v][i].add(k-1) # set index of select item
    
27.    
    
28.     for v in range(halfSumAll,0,-1):
    
29.         if isOK[v][n] is not None:
    
30.             print "Minumum abs(a-b):",(halfSumAll-v)*2
    
31.             a = [total[k] for k in isOK[v][n]]
    
32.             b = [total[k] for k in range(len(total)) if k not in isOK[v][n]]
    
33.             print "a:",a
    
34.             print "b:",b
    
35.             break
    
36. 
    
37. 
    

复制代码

linux_c_py_php

恩, 的确是这个, 楼主很有耐心啊.