亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

Chinaunix

標題: 【華為公司Python面試題】,要求10分鐘寫出代碼。。。 [打印本頁]

作者: 天魔封神霸    時間: 2009-06-26 14:13
標題: 【華為公司Python面試題】,要求10分鐘寫出代碼。。。
有兩個序列a,b,大小都為n,序列元素的值任意整形數(shù),無序;
要求:通過交換a,b中的元素,使[序列a元素的和]與[序列b元素的和]之間的差最小。



附帶一下我們的組織:
游戲開發(fā)-2群:Python(78676826),主要討論:
桌面:WxWidget、TK、GTK、QT
游戲:pyOGRE、pyGame、"python.h"
Web:Zope、Django
網(wǎng)絡(luò):Twisted
只要心中有夢就可以與我們?yōu)槲椋ame Developer歡迎志同道合的朋友加入。

[ 本帖最后由 天魔封神霸 于 2009-6-26 14:41 編輯 ]
作者: bawbaw    時間: 2009-06-27 10:29
def look(a, max = 0):
    a.sort()
    while 1:
        if len(a) == 0:return None
        val = a.pop()
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if val <= max:return val


def ab(a , b):
&nbsp;&nbsp;&nbsp;&nbsp;a.extend(b)
&nbsp;&nbsp;&nbsp;&nbsp;sum = reduce(lambda x,y:x+y, a)
&nbsp;&nbsp;&nbsp;&nbsp;arvg = sum / 2.0

&nbsp;&nbsp;&nbsp;&nbsp;rs1 = []
&nbsp;&nbsp;&nbsp;&nbsp;def qq(arvg, pick = None):
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if pick is None:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pick = a.pop()
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a.remove(pick)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;rs1.append(pick)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arvg -= pick
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pick = look(a[:], max = arvg)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if pick is not None:qq(arvg, pick)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;qq(arvg)
&nbsp;&nbsp;&nbsp;&nbsp;print rs1, a
ab([1,2,5,3],[6,7,8,9,10])


[ 本帖最后由 bawbaw 于 2009-6-27 10:44 編輯 ]
作者: broader    時間: 2009-06-27 15:47
原帖由 天魔封神霸 于 2009-6-26 14:13 發(fā)表
有兩個序列a,b,大小都為n,序列元素的值任意整形數(shù),無序;
要求:通過交換a,b中的元素,使[序列a元素的和]與[序列b元素的和]之間的差最小。

http://wiki.services.openoffice.org/w/images/7/7e/Python_po ...

題面描述中:“整形數(shù)”是什么數(shù)?正整數(shù)、整數(shù)還是什么其它的數(shù)?
如果是正整數(shù),想到的一個算法描述如下:
1 將a、b序列中的元素合并到一個長度為2n的list中并排序,假定此list名稱為c;
3 創(chuàng)建兩個空list分別命名為x,y
2 構(gòu)建一個函數(shù)假設(shè)名稱為add2list,該函數(shù)的作用是將兩個正整數(shù)添加到x,y中,保證這x,y的元素之和的差值的絕對值最。
3 對c中的元素依次兩兩分組遞歸調(diào)用前面的函數(shù)add2list
4 最后得到的x,y即為所求之結(jié)果

[ 本帖最后由 broader 于 2009-6-28 11:32 編輯 ]
作者: 天魔封神霸    時間: 2009-06-28 13:56
整形數(shù),我沒說清楚,就是指 整數(shù)
作者: ruiqingzheng    時間: 2009-06-28 17:20
標題: 回復 #1 天魔封神霸 的帖子
比如 [1..100]  這樣的一個list
切成兩個LIST 并讓兩個list的和之間的差的絕對值最小
不就是[1..25] [100..76] 組成一個list
另外的[26..75] 組成一個list
這兩個LIST的元素和的差為0 當然是絕對值最小的了

所以  只用把兩個LIST 排序成一個LIST后切片    就可以得到這樣的兩個LIST , 對吧?
作者: iamkey9    時間: 2009-07-01 13:48
最小怎么定義,這個是問題,0不是最小。
作者: guijia8427    時間: 2009-07-01 14:30
10分鐘? 有難度哦
作者: weizhe86    時間: 2009-07-01 14:35
ruiqingzheng

發(fā)表于 2009-6-28 17:20
            比如 [1..100]  這樣的一個list
切成兩個LIST 并讓兩個list的和之間的差的絕對值最小
不就是[1..25] [100..76] 組成一個list
另外的[26..75] 組成一個list
這兩個LIST的元素和的差為0 當然是絕對值最小的了

所以  只用把兩個LIST 排序成一個LIST后切片    就可以得到這樣的兩個LIST , 對吧?
肯定不對嘍[1,2,3,4,5,6,700,800],如何
作者: gdh    時間: 2009-07-02 01:25
提示: 作者被禁止或刪除 內(nèi)容自動屏蔽
作者: weizhe86    時間: 2009-07-02 07:58
標題: 回復 #9 gdh 的帖子
也不對
S=[10001,10000,100,90,50,1]
如何
是a=[10001,90,50]
   b=[10000,100,1]
差為40
還是a=[10001,100,1]
      b=[10000,90,50]
差為38
您的方案顯然是前者。
作者: nkchenz    時間: 2009-07-02 12:29
貼一個試試

#l = range(1, 11)
l = [10001,10000,100,90,50,1]
#l = [1,2,3,4,5,6,700,800]
l.sort(reverse = True)

def sl(l):
    s = 0
    for i in l:
        s += i
    return s

avg = sl(l) / 2 # 求和的平均
print avg

r = []
for i in l: # 從大到小遍歷
    s = sl(r + [i])
    if s < avg:
        r.append(i)
    elif s == avg:
        r.append(i)
        break
    else:
        # 當新加入的i大于avg時,需要特殊處理。
        if not r:
            r.append(i)
            continue
        t1 = s - i
        t2 = sl(r[:-1]) + i
        if abs(t1 - avg) > abs(t2 -avg): # 看新的i是否比上一個i為優(yōu)
            r = r[:-1] + [i]

print r


[ 本帖最后由 nkchenz 于 2009-7-2 12:34 編輯 ]
作者: eookoo    時間: 2009-07-02 14:05
標題: 回復 #11 nkchenz 的帖子
如果:
l = [12312, 12311, 232, 210, 30, 29, 3, 2, 1, 1]

# ur answer:
12551 = [12312, 232, 3, 2, 1, 1]  
12580 = [12311, 210, 30, 29]      
差 29


12559 = [12312, 210, 30, 3, 2, 1, 1]
12572 = [12311, 232, 29]
差13
作者: gdh    時間: 2009-07-02 16:22
提示: 作者被禁止或刪除 內(nèi)容自動屏蔽
作者: nkchenz    時間: 2009-07-02 17:28
標題: 回復 #12 eookoo 的帖子
理解上也有偏差,題目要求最后的兩個列表還是等長
作者: weizhe86    時間: 2009-07-03 14:12
標題: 回復 #13 gdh 的帖子
Source List:    [1, 2, 3, 4, 5, 6, 700, 800]
Result List:    [1, 4, 5, 800] [2, 3, 6, 700]
Distance:       99

應該是

Source List:    [1, 2, 3, 4, 5, 6, 700, 800]
Result List:    [1,2,3,800] [4,5,6,700]
Distance:       91

另外
Source List:    [1, 1, 2, 3, 29, 30, 210, 232, 12311, 12312]
Result List:    [1, 3, 29, 232, 12311] [1, 2, 30, 210, 12312]
Distance:       21
也不對

應該是
a=[1,1,29,232,12311]
b=[2,3,30,210,12312]
差為17

[ 本帖最后由 weizhe86 于 2009-7-3 15:10 編輯 ]
作者: gdh    時間: 2009-07-03 16:19
提示: 作者被禁止或刪除 內(nèi)容自動屏蔽
作者: weizhe86    時間: 2009-07-03 22:36
標題: 回復 #11 nkchenz 的帖子
sl可以直接使用sum函數(shù)嘛
另外你少考慮一些東西
作者: weizhe86    時間: 2009-07-04 16:41
標題: 大家可以用這個程序檢測自己的結(jié)果是不是正確
#coding=utf-8
souce=[12312, 12311, 232, 210, 30, 29, 3, 2, 1, 1]
souce.sort(reverse=True)
l=len(souce)
avg=sum(souce)/2.0
def changeone(n,liu):
    li=liu
    lis=[[v for v in li]]
    for i in range(l):
        if not i in liu:
            li[n]=i
            lis.append([v for v in li])
    lin=[]
    if n<l/2-1:
        for lii in lis:
            lin+=(changeone(n+1,lii))
    return lin+lis
li=changeone(1,range(l/2))
mincha=sum([souce[x] for x in li[0]])
for i in li:
    s=sum([souce[x] for x in i])
    if abs(s-avg)<abs(avg-mincha):
        mincha=s
        print mincha*2-sum(souce),[souce[x] for x in i]

將所有分組方法的結(jié)果都計算出來,輸出差值最小的那種分法。效率最慢(華為不會使用這種方法的),能保證準確性,隨意推薦給大家做檢查用。
作者: needspeedboy    時間: 2009-07-05 04:05
把兩個序列合并,然后排序,然后索引奇分一個列,索引偶數(shù)再分一個列就行了.
作者: weizhe86    時間: 2009-07-06 17:16
標題: 回復 #19 needspeedboy 的帖子
你覺得華為會出這么幼稚的題目嗎
作者: wudi626    時間: 2009-07-07 00:07
# coding=gb2312
# 有兩個序列a,b,大小都為n,序列元素的值任意整形數(shù),無序;
# 要求:通過交換a,b中的元素,使[序列a元素的和]與[序列b元素的和]之間的差最小。

def FindTargetItem(diff,lst):
    for item in lst:
        if diff >= item:
            return lst.index(item)
        else:
            return -1

def Process(lstA,lstB):
    sumA = sum(lstA)
    sumB = sum(lstB)
   
    lstA.sort()
    lstB.sort()
   
    if sumA == sumB:
        return
    elif sumA > sumB:
        diff = sumA - sumB
        while diff >= 0:
            targetIndex = FindTargetItem(diff,lstA)
            if targetIndex == -1:
                return
            else:
                lstB.append(lstA.pop(targetIndex))
            sumA = sum(lstA)
            sumB = sum(lstB)
            diff = sumA - sumB
    else:
        diff = sumB - sumA
        while diff >= 0:
            targetIndex = FindTargetItem(diff,lstB)
            if targetIndex == -1:
                return
            else:
                lstA.append(lstB.pop(targetIndex))
            sumA = sum(lstA)
            sumB = sum(lstB)
            diff = sumB - sumA
    return
作者: wudi626    時間: 2009-07-07 00:24
原帖由 wudi626 于 2009-7-7 00:07 發(fā)表
# coding=gb2312
# 有兩個序列a,b,大小都為n,序列元素的值任意整形數(shù),無序;
# 要求:通過交換a,b中的元素,使[序列a元素的和]與[序列b元素的和]之間的差最小。

def FindTargetItem(diff,lst):
    for ...



仔細看了下,這個算法不符合要求!
作者: edgar    時間: 2009-07-07 11:35
'''
Created on 2009-7-7

@author: Edgar
'''
def getDif(aList,bList):
    asum=0;
    bsum=0;
   
    for eachItemIndex in range(len(aList)):
        asum+=aList[eachItemIndex];
        bsum+=bList[eachItemIndex];
    return bsum-asum
def getMaxValue(aList,bList):
    aList.sort()
    aMax=aList[-1]
    bList.sort()
    bMax=bList[-1]
    if aMax<bMax:
        return bMax
    else:return aMax
   
def getTheProperPairs(aList,bList):
    theDif=getDif(aList, bList)
    theMinmum={"aList":0,"bList":0,"diff":getMaxValue(aList, bList)}
    for i in aList:
        for k in bList:
            theTempDif=2*(k-i)
            if theTempDif==theDif:
                theMinmum["diff"]=theTempDif
                theMinmum["aList"]=i
                theMinmum["bList"]=k
                return theMinmum
               
            if theMinmum["diff"]>abs(theTempDif-theDif):
                theMinmum["diff"]=abs(theTempDif-theDif)
                theMinmum["aList"]=i
                theMinmum["bList"]=k
   
    return theMinmum
是說只準交換一個嗎?還是允許交換多個?交換位置有要求嗎?
我這個程序是只準許一個,交換位置沒有要求
作者: sysengcn    時間: 2009-07-07 13:19
為什么童鞋們總喜歡把簡單問題復雜化呢?

其實只要想著讓 sum(X) 和 sum(Y) 都往 ( sum(A) + sum(B) ) / 2 上靠不就完了嗎。(這里假設(shè) A, B 為源 list, X, Y 為所求的 list。)

因為只有當 sum(X) 和 sum(Y) 都最靠近那個中間點的時候,他們的差才會最小,對吧?


A = [1, 2, 700, 6]
B = [4, 3, 5, 800]
X = []
Y = []

pivot = ( sum(A) + sum(B) ) / 2

C = A + B
C.sort()

def next_one(sum) :
    if sum > pivot :
        return C.pop(0)
    else :
        return C.pop(-1)

while len(C) :
    if abs(sum(X) - pivot) > abs(sum(Y) - pivot) :
        # X is further away to pivot than Y, let X pick first
        X.append( next_one( sum(X) ) )
        Y.append( next_one( sum(Y) ) )
    else :
        # otherwise let Y pick first
        Y.append( next_one( sum(Y) ) )
        X.append( next_one( sum(X) ) )

print X
print Y
print abs(sum(X) - sum(Y))


[ 本帖最后由 sysengcn 于 2009-7-6 21:21 編輯 ]
作者: edgar    時間: 2009-07-08 09:17
sysengcn ,你這是不限次數(shù)的調(diào)換啊……
作者: weizhe86    時間: 2009-07-08 23:26
標題: 提醒大家一個問題
一,題目要求的是差值最小的方案,所以交換一對數(shù)據(jù)是不能實現(xiàn)的。
二,最后交換一對數(shù)據(jù)無法使差值減小,但是存在同時交換兩對(還有更多對)數(shù)據(jù)可以減小差值的可能。
作者: weizhe86    時間: 2009-07-08 23:30
標題: 回復 #24 sysengcn 的帖子
你這個問題,前邊已經(jīng)說過不對了,為什么還要發(fā)。
作者: newman0708    時間: 2009-07-21 15:46


  1. def sumlist(list1):
  2.     retsum=0
  3.     for i in list1:
  4.         retsum=retsum+i
  5.     return retsum


  6. def getminutegap(a1):
  7.     minutegap=[]
  8.     for i in xrange(len(a1)-1):
  9.         val1=a1[i]
  10.         val2=a1[i+1]
  11.         gap=abs(val1-val2)
  12.         minutegap.append(gap)
  13.     return minutegap

  14. def getmaxvalueindex(list1):
  15.     maxv=max(list1)
  16.     return list1.index(maxv)
  17.    
  18. def dividelist(a1,b1):
  19.     a1.extend(b1)
  20.     aaa=[]
  21.     bbb=[]
  22.     a1.sort()
  23.     a1.reverse()
  24.     print a1

  25.     while(len(a1)>1):
  26.         maxgapindex=getmaxvalueindex(getminutegap(a1))
  27.         if sumlist(aaa)<=sumlist(bbb):
  28.             aaa.append(a1[maxgapindex])
  29.             bbb.append(a1[maxgapindex+1])
  30.         else:
  31.             aaa.append(a1[maxgapindex+1])
  32.             bbb.append(a1[maxgapindex])            
  33.         a1.remove(a1[maxgapindex])
  34.         a1.remove(a1[maxgapindex])

  35.     if (len(a1)>0) and (sumlist(aaa)<sumlist(bbb)):
  36.         aaa.append(a1[0])

  37.     aaasum=sumlist(aaa)
  38.     bbbsum=sumlist(bbb)
  39.     print aaa,aaasum,bbb,bbbsum,(sumlist(aaa)-sumlist(bbb))

  40.         

  41.    
  42. #dividelist([1,2,5,3],[6,7,8,9,10])
  43. #dividelist([300, 200],[ 150, 53, 12, 3])




  44. dividelist([10001,10000],[100,90,50,1])
  45. # 1001 1000 10 8 5 1
  46. # 1001 8  5  =1014
  47. # 1000 10 1  =1011

  48. # 1001 10 1  =1012
  49. # 1000 8  5  =1013

  50. dividelist([101,100],[10, 8, 5, 1])
  51. # 101 100 10 8 5 1
  52. # 101 8  5  =113
  53. # 100 10 1  =111

  54. # 101 10 1  =112
  55. # 100 8  5  =113


復制代碼

作者: luxyi    時間: 2009-08-04 14:35
這題目就是考算法,跟 Python 沒什么關(guān)系。
作者: doctorwho    時間: 2009-08-05 00:54
網(wǎng)上Google到的,覺得有道理,大家討論一下,有更好的算法嗎?
   
   求解思路:

    當前數(shù)組a和數(shù)組b的和之差為
    A = sum(a) - sum(b)

    a的第i個元素和b的第j個元素交換后,a和b的和之差為
    A' = sum(a) - a + b[j] - (sum(b) - b[j] + a)
           = sum(a) - sum(b) - 2 (a - b[j])
           = A - 2 (a - b[j])
    設(shè)x = a - b[j]

    |A| - |A'| = |A| - |A-2x|

    假設(shè)A > 0,

    當x 在 (0,A)之間時,做這樣的交換才能使得交換后的a和b的和之差變小,x越接近A/2效果越好,

    如果找不到在(0,A)之間的x,則當前的a和b就是答案。

    所以算法大概如下:

    在a和b中尋找使得x在(0,A)之間并且最接近A/2的i和j,交換相應的i和j元素,重新計算A后,重復前面的步驟直至找不到(0,A)之間的x為止。


[ 本帖最后由 doctorwho 于 2009-8-5 00:56 編輯 ]
作者: Lonki    時間: 2009-08-05 14:11
動態(tài)規(guī)劃
Python會有這樣的面試, 還是10分鐘, 還是廣告...
作者: starfuck    時間: 2009-08-24 00:57
本帖最后由 starfuck 于 2019-11-26 23:48 編輯













作者: ypyf3000    時間: 2009-08-26 11:33
十分鐘怎么可能做出來,蒙人
作者: szwe    時間: 2009-08-28 17:27
窮舉好了,又沒要求算法的最優(yōu),反正也就是o(N^3)的復雜度
作者: shopokey    時間: 2009-08-29 00:41
都有幾個月沒看python的代碼了,看到這個題目還真的搞不出...
作者: toakee    時間: 2009-08-31 08:56
標題: 回復 #1 天魔封神霸 的帖子
#!/usr/bin/env python
# python 2.4+

a = [20,5,3]
b = [2,1,1]

def sum(lst):
    return reduce(lambda x,y: x+y,lst)

def do(d):
    global a,b
    x = -1

    for i in xrange(a):
        for j in xrange(b):
            c = a[ i] - b[j]
            if c > 0 and c <= d/2:
                if x == -1 or  c > x:
                    x = c
                    ai = i
                    bj = j

    if x == -1:
        return False
    else:
        a[ai],b[bj] = b[bj],a[ai]
        return True

def main():
    global a,b
    while True:
        if sum(a) < sum(b):
            a,b = b,a
        a.sort(reverse=True)
        b.sort(reverse=True)
        Diff = sum(a) - sum(b)

        if do(Diff):
            continue
        else:
            print a
            print b
            break

if __name__ == '__main__':
    main()


[root@web ~]# python test.py
[20, 1, 1]
[2, 5, 3]

雖然代碼比較臃腫,但基本功能能實現(xiàn)。

[ 本帖最后由 toakee 于 2009-9-8 10:42 編輯 ]
作者: starfuck    時間: 2009-09-02 00:39
本帖最后由 starfuck 于 2019-11-26 23:48 編輯













作者: redskywy    時間: 2009-09-07 09:56
負數(shù)不比0小的嗎?
作者: 愛斯基摩寂寞    時間: 2009-09-10 15:42
我覺得樓主很無聊 大家每說一個他就說也不對 比如。。。。你干脆給出答案得了 賣什么關(guān)子 你說成ibm的面試題得了
作者: tangboyun    時間: 2010-01-29 20:55
解法思路在此:

http://blog.csdn.net/tangboyun/archive/2010/01/29/5270785.aspx
                                                                                      
為什么我說我的解法是這個問題的最優(yōu)解?

依賴于三個特性:

一、就是交換a1和b1中的元素后,得到的新的a'和b'序列,它們依舊是從大到小排列的。無需再sort!

二、得到的a1和b1序列,其下標,和之后用以操作swap函數(shù)的下標及求最合適石塊(最合適的數(shù)值差),存在一個簡單的轉(zhuǎn)換關(guān)系。

三、 $smallRock[0]一定是原先2n個元素中,任意兩元素差值的最小值!。∵@個對用來測試最后還要不要交換,是至關(guān)重要的,沒有這個概念的解法,不可能得到正確答案。。!
作者: shhgs    時間: 2010-01-29 23:40
很難。10分鐘肯定不夠。我想算法得20分鐘。真正出代碼得一個小時。

順便說一句,針對這道題,所有“投機取巧”的算法,我都表示懷疑。因為你們沒有辦法用數(shù)學證明你們的算法是可靠的。

[ 本帖最后由 shhgs 于 2010-1-29 23:52 編輯 ]
作者: lxguidu    時間: 2010-01-29 23:48
看來我的能力不行啊,各位都是高手,領(lǐng)教了!
作者: shhgs    時間: 2010-01-30 00:06
其實這道題還真不是考你們算法的。這是考你們的數(shù)據(jù)結(jié)構(gòu)的。照著題目的意思,用swap元素的方式調(diào)整。要說算法,其實就是設(shè)計一個停止的條件。就是判斷當前情況下,沒有可調(diào)整的元素了。


  1.     a1          a2          a3      a4 ...
  2. b1  (1,1),m1   (1,2),m2     ...
  3. b2  ...
  4. b3  ...
  5. .
  6. .
  7. .
復制代碼

很明顯,這是一個dict,鍵就是序列a和b的下標(tuple),值就是他們的差。

這里的停止條件是,n = sum(a) - sum(b) 和這個dict里面的所有值的比較(假設(shè)某個值為m)。有兩個條件
1. m 和 n 符號相同(同正或同負)
2. |m - n| < n
然后,選 |m - n| 最小的那個m,找出其對應的a和b的下標,swap兩個元素。

[ 本帖最后由 shhgs 于 2010-1-30 06:22 編輯 ]
作者: nankai559    時間: 2010-04-28 22:45
以上所有非指數(shù)級算法都不對,因為此問題至少是NP-Complete.

理由:
將兩個數(shù)組合并后從小到大排序,然后a'取前一半小值,b'取后一半大值。
這里假設(shè)一種簡化情況,就是我們只需交換a',b'中相同位置的元素就可獲得最優(yōu)解(實際情況要更加復雜)。
然后我們將數(shù)組C設(shè)為b'-a',是一組正整數(shù); 設(shè)正整數(shù)T為(sum(b')-sum(a'))/2,F(xiàn)在問題變?yōu)?

1. 一組正整數(shù)集合C,目標正整數(shù)T, 求C中的一個子集使得此子集的和在不超過T的情況下越大越好,

2. 一組正整數(shù)集合C,目標正整數(shù)T, 求C中的一個子集使得此子集的和在不小于T的情況下越小越好。

問題1被稱為子集和問題(subset sum problem),可以看做是背包問題的一個特例。此問題是NP-Complete的。

兩個關(guān)于subset sum problem的鏈接:
http://www.cs.dartmouth.edu/~ac/ ... /nanda-scribe-3.pdf
http://en.wikipedia.org/wiki/Subset_sum_problem

因為本問題的一個簡化情況都是NP-Complete的,所以這個問題本身至少是NP-Complete的。
作者: Kabie    時間: 2010-05-20 08:09
  1. def gotans(a,b):
  2.         c=sorted(a+b,reverse=(sum(a+b)>0))
  3.         S=sum(c)
  4.         s=abs(S)
  5.         S=S/2
  6.         for i in itertools.combinations(c,len(a)):
  7.                 tmp = abs(sum(i)-S)
  8.                 if tmp<s:
  9.                         s=tmp
  10.                         print(s,sum(i),i)
  11.                         if tmp==0 or tmp==0.5:
  12.                                 break
復制代碼
...10分鐘也只好先窮舉了……效率非常低。。。。
作者: litanhe    時間: 2010-05-21 19:24
1. 合并兩個數(shù)組
2. 數(shù)組排序,
3. 如果最小數(shù)是負數(shù),則所有元素先加上其絕對值
4. 分配序列:
   序列1和序列2默認sum為零
    分配序列到序列1,直到求和大于序列2,然后其余數(shù)分配到序列2,直到序列2求和和大于序列1
  終止:某個序列數(shù)目達到n,未分配序列分配到另一序列組
這樣得到的兩個序列求和差值是否最。
作者: aoma    時間: 2010-05-28 23:15
我的想法
數(shù)組從大到小排序得到數(shù)組A(A1,A2,A3,...A2n)
建兩個新數(shù)組B,C,先從A取最大的兩個元素,分別給B,C,到底sum(B)和sum(C)誰大不重要,如果B大則C取第三個,如果C大則B取第三個,第四個元素取最后的元素A2, B和C得到兩個元素后,開始計算sum,誰小取第A4個元素,依次類推
作者: pikyshen    時間: 2010-05-30 21:03
提示: 作者被禁止或刪除 內(nèi)容自動屏蔽
作者: fisherjams    時間: 2010-06-05 01:41
給你個思路八

兩個序列合并求和并求平均值avg
min=avg-avg*n/2
max=avg+avg*n/2

最后a序列為>=min且<=max的數(shù),b序列為其他

用a,b交換實現(xiàn)上述結(jié)果
作者: fisherjams    時間: 2010-06-05 01:50
在進一步

先對ab分別排序,a從大向小,b從小向大

a和b 在min和max之間有交集,對交集互換,過avg點后交換方向相反
作者: FisherGray    時間: 2011-03-10 17:44
  1. def fun(list_a,list_b,index):     
  2.     if list_a[index+1] >= list_b[index]:
  3.         _copy=list_b[index]
  4.         list_b[index]=list_a[index+1]
  5.         list_a[index+1]=list_b[index+1]
  6.         list_b[index+1]=_copy
  7.     elif list_a[index+1] < list_b[index] and list_a[index+1] > list_b[index+1]:
  8.         _copy=list_b[index+1]
  9.         list_b[index+1] = list_a[index+1]
  10.         list_a[index+1] = _copy
  11.     return list_a,list_b

  12. def exchange_elments_of_two_lists(list_a,list_b):   
  13.     list_a.sort(reverse=True)
  14.     list_b.sort(reverse=True)
  15.     for index in xrange(0,len(list_a)-1):
  16.         if list_a[index] > list_b[index]:           
  17.             [list_a,list_b]=fun(list_a,list_b,index)        
  18.         elif list_a[index] < list_b[index]:           
  19.             [list_b,list_a]=fun(list_b,list_a,index)         
  20.     return list_a,list_b
復制代碼

作者: FisherGray    時間: 2011-03-10 17:48
python made it easy, Right?
作者: a515200    時間: 2011-03-10 18:31
和上次我發(fā)的最大子段和實現(xiàn)算法一樣,仍用遞歸實現(xiàn),我將把效率拋諸腦后,
作者: weihengsi    時間: 2011-03-11 12:50
華為就是不一樣啊

思路是有啊,可是10分鐘有點少啊,說不定是打錯字什么的,都要使時間超過10分鐘啊,這人生啊
作者: ixuh    時間: 2011-03-12 14:09
  1. la = [3, 34, 435, 45, 3, 34, 678, 3245]
  2. lb = [23, 3, 12, 3245, 234, 457, 345, 435]

  3. def split(lst):
  4.     halfsize = len(lst) / 2
  5.     return lst[:halfsize], lst[halfsize:]

  6. la, lb = split(sorted(la + lb))
  7. print sum(la) - sum(lb)
復制代碼

作者: a515200    時間: 2011-03-12 22:37
不要一大堆人圍進來,整天喊著思路,要么你就貼代碼,要么你們就飄過

好比大學生學數(shù)據(jù)結(jié)構(gòu),概念理論說的頭頭是道,編起程來一個代碼都敲不了
作者: a515200    時間: 2011-03-12 22:37
看清楚題目,大佬..
作者: ixuh    時間: 2011-03-14 13:03
回復 57# a515200


    有什么不對呢? 難道你能找到比-8917更小的差...
作者: a515200    時間: 2011-03-14 13:41
這個題目實際上應該叫做    兩序列元素的總和之差的絕對值應為最小,我想華為的人是故意這樣做的,有點故弄玄虛


題目要求是:
要求:通過交換a,b中的元素,使[序列a元素的和]與[序列b元素的和]之間的差最小。
應該列出兩個交換后的序列
作者: 專操五毛    時間: 2011-03-18 14:26
本帖最后由 專操五毛 于 2011-03-18 14:30 編輯

.....................................................................................................
作者: d_bsky    時間: 2012-05-06 19:36
按照我的思想,就是先合并兩個序列a跟b,得到c,然后排序c,再分割c,左右端同時取值,一次放d,一次放e,最后得到de兩個list,這個應該就是差值最小的了吧
作者: qinscx    時間: 2012-05-07 11:57
按照我的思想,就是先合并兩個序列a跟b,得到c,然后排序c,再分割c,左右端同時取值,一次放d,一次放e,最后得到de兩個list,這個應該就是差值最小的了吧

樓上的思路和我的一樣,另一種等同的做法是:合并之后排序,按奇偶分割成兩個序列即為所求。
理由:合并排序后,針對第一個元素,試想序列里元素,誰和他的差距最。慨斎皇堑诙䝼。這樣,一二元素分離。再來考慮第三個元素,同樣的道理,三四元素分開。這樣,最后的結(jié)果是:元素最小差距1 + 元素最小差距2 + 。。。 = 兩個序列的最小差距。
作者: dknlnl    時間: 2012-05-07 21:34
本帖最后由 dknlnl 于 2012-05-07 22:11 編輯

每個序列之和越靠近總和的1/2,那么是兩個序列這差越小.
考慮反貪心算法.
將兩個序列合并,排序,記為sortList.
設(shè)x,y為結(jié)果序列.
x依次從sortList中取數(shù),從最小的開始取.直到sum(x)>=sum(sortList)/2.

假設(shè)x從sortList取出一個數(shù)k反,sum(x)從小于sum(sortList)/2變?yōu)榇笥诨虻扔趕um(sortList)/2,根據(jù)以下條件判斷k是否放入x:
如果將k加入x后,x的和與y(y就是sortList減于x啦)之差小于將k不放入x,那么k放入x.
以上是不要求結(jié)果序列等長的.

作者: CMAX    時間: 2012-06-01 17:54
本帖最后由 CMAX 于 2012-06-01 17:54 編輯

python的,純實現(xiàn),沒考慮其他的
  1. #! /usr/bin/env python

  2. import input
  3. a = input.a
  4. b = input.b

  5. l = len(a)

  6. ar = list()
  7. br = list()

  8. sl = sorted(a + b, reverse = True)

  9. diff = 0

  10. sign = True

  11. for i in xrange(0, l):
  12.     for j in range(2*l-1, i+1, -1):
  13.         d1 = sl[i] - sl[j-1]
  14.         d2 = sl[i] - sl[j]
  15.         if diff - d1 >= 0 and diff - d2 < 0:
  16.             r1, r2 = i, j
  17.             break
  18.     else:
  19.         r1, r2 = i, i+1

  20.     if sign:
  21.         ar.append(sl[r1])
  22.         br.append(sl[r2])
  23.     else:
  24.         ar.append(sl[r2])
  25.         br.append(sl[r1])
  26.     sign = not sign

  27. print ar, sum(ar)
  28. print br, sum(br)
復制代碼

作者: bskay    時間: 2012-08-29 11:35
本帖最后由 bskay 于 2012-08-29 15:42 編輯

偽動態(tài)規(guī)劃的,

#動態(tài)規(guī)劃問題
#從M個數(shù)里面找出N個,讓他們的和盡量接近 P
class NumList:
        def __init__(self):
                self.reset()
                pass
        def reset(self):
                self.vA = []
                self.vB = []
                self.nSumA = reduce(lambda x, y: x+y, self.vA, 0)
                self.nSumB = reduce(lambda x, y: x+y, self.vB, 0)
                pass
        #開始規(guī)劃
        def addonce(self,nA,nB):
                #
                if self.nSumA > self.nSumB:
                        self.vA.append(nA)
                        self.nSumA += nA
                        self.vB.append(nB)
                        self.nSumB += nB
                        pass
                else:
                        self.vA.append(nB)
                        self.nSumA += nB
                        self.vB.append(nA)
                        self.nSumB += nA
                        pass
                #try
                while self.ajduest():pass
                return
        def ajduest(self):
                if self.nSumA>self.nSumB:
                        nA,nB = self.findd(self.vA,self.vB,(self.nSumA-self.nSumB)/2)
                        if nA is None or nB is None:
                                return False
                        pass
                elif self.nSumA<self.nSumB:
                        nB,nA = self.findd(self.vB,self.vA,(self.nSumB-self.nSumA)/2)
                        if nA is None or nB is None:
                                return False
                        pass
                else:
                        return False
                self.nSumA += self.vB[nB] - self.vA[nA]
                self.nSumB += self.vA[nA] - self.vB[nB]
                print 'r1(vA,vB) =',self.vA,self.vB
                self.vA[nA],self.vB[nB] = self.vB[nB],self.vA[nA]
                self.vA.sort()
                self.vB.sort()
                print 'r2(vA,vB) =',self.vA,self.vB
                return True
        #
        '''
        輸入:
                I1. A中所有元素的和大于B中所有元素的和
                I2. A,B中的元素從小到大排列
                I3. 最大期望的調(diào)整值
        輸出:
                O1. 在A,B中分別找出一個位置(a,b)
                O2. 交換調(diào)整A,B中對應的元素后,依然滿足I1
                O3. 沒有找到滿足條件一個位置,返回None
        '''
        def findd(self,vA,vB,nDlt):
                print 'findd',vA,vB,nDlt
                nA,nB = None,None
                nXXX = nDlt
                for a in xrange(len(vA)-1,-1,-1):
                        for b in xrange(len(vB)):
                                if vB >= vA[a]:
                                        break
                                nDiff = vA[a]-vB #調(diào)整的差值
                                if nDiff > nDlt:
                                        continue
                                if nDlt-nDiff >= nXXX:
                                        continue
                                if nDiff == nDlt:
                                        print 'haha findd at ... ',a,b
                                        return a,b
                                #print '(vB,vA[a]) =',(vB,vA[a]),'(a,b)',(a,b), 'r =',nDiff
                                nXXX = nDlt-nDiff
                                nA,nB = a,b
                                continue
                        continue
                print 'findd at ... ',nA,nB
                return nA,nB
        def main(self,vA,vB):
                self.reset()
                vX = vA+vB
                vX.sort()
                while len(vX):
                        self.addonce(vX[0],vX[1])
                        del vX[:2]
                        continue
                print 'vA =>',self.vA
                print 'vB =>',self.vB
                return
        pass


self = NumList()
self.main([1,1,1,1],[2,2,2,2])
assert(self.vA == [1,1,2,2] and self.vA==self.vB)

self.main([1,1,1,1],[1,1,1,1])
assert(self.vA == [1,1,1,1] == self.vB)

self.main([1,1,2,3,5,10,], [20,30,30,50,50,100,])


作者: Hadron74    時間: 2012-08-29 16:38
本帖最后由 Hadron74 于 2012-08-29 20:00 編輯

看了前人的解法,怎么把問題搞得那么復雜。這個題目是十分鐘的題目,肯定沒有那么多代碼的。

我的思路是用窮舉法,把所有的a+b的total的序列的排列窮舉,得到所有可能的劃分,對其差值計算最小值。

下面是程序,
  1. def minus(total):
  2.         n = len(total)/2
  3.         a = total[:n]
  4.         b = total[n:]
  5.         return abs(sum(a)-sum(b)),a,b

  6. def func(total,k):
  7.         mi,am,bm = minus(total)
  8.         global minusN,an,bn
  9.         if mi < minusN:
  10.                 minusN = mi
  11.                 an,bn = am,bm

  12.         for i in range(k,len(total)):
  13.                 total[k],total[i] = total[i],total[k]
  14.                 func(total,k+1)
  15.                 total[k],total[i] = total[i],total[k]

  16. a=[1,2,3,4]
  17. b=[6,7,8,9]
  18. an,bn = a[:],b[:]
  19. total = a+b
  20. minusN,am,bm=minus(total)
  21. func(total,0)
  22. print "a:",an
  23. print "b:",bn
  24. print "minus:",minusN

復制代碼
這里的算法用到了窮舉一個序列的全排列的算法,見
http://www.cnblogs.com/height/archive/2012/08/14/2638802.html

這個算法的復雜性太過要O((2n)!),我的寫法中也有冗余的部分,有時間來改正。
這里拋磚引玉,也許有更短小的寫法?隙ㄓ懈斓乃惴,我正在尋找中。


作者: Hadron74    時間: 2012-09-12 19:03
本帖最后由 Hadron74 于 2012-09-12 19:13 編輯

回復 66# Hadron74


    現(xiàn)在我有了一個更好的方法,用0-1背包問題來解決這個問題。思路是,給一個總和長的select數(shù)組,記錄a/b的狀態(tài),True表示在a中,F(xiàn)alse表示在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. def func(sumN,k):
  7.     global select,number,halfnumber,minSN,an,bn
  8.     if k==number:
  9.         return
  10.     if sumN == halfnumber:
  11.         mi,am,bm = minus()
  12.         if mi< minSN:
  13.             minSN = mi
  14.             an,bn = am,bm
  15.         return
  16.     select[k] = True
  17.     func(sumN+1,k+1)
  18.     select[k] = False
  19.     func(sumN,k+1)
  20.    
  21. if __name__ == '__main__':
  22.     a = [1,2,3,4]
  23.     b = [6,7,8,9]
  24.     total = a + b
  25.     an, bn = a[:], b[:]
  26.     minSN = abs(sum(a)-sum(b))
  27.     number = len(total)
  28.     halfnumber = number/2

  29.     select = map(lambda x: False,total)

  30.     func(0,0)

  31.     print minSN
  32.     print an
  33.     print bn
復制代碼
結(jié)果:
  1. 0
  2. [1, 4, 7, 8]
  3. [2, 3, 6, 9]
復制代碼

作者: new_ray    時間: 2012-09-16 20:59
我覺得就是一個排序問題吧。
比如:序列a1,a2,a3,...an
         序列b1,b2,b3,...bn
         假設(shè)存在一個序列c,c的元素為a1,a2,a3...an,b1,b2,b3...bn.對序列c排序后得到新的順序,c1,c2,c3..c2n.則得到序列a結(jié)果為c1,c3,c5...c2n-1,序列b為c2,c4,c6...c2n.
而排序可以只比較就可以了。
作者: Hadron74    時間: 2012-09-17 00:21
回復 68# new_ray

這個問題沒有那么簡單,詳細請看我們最新的帖子。《編程之美》給出了正整數(shù)的動態(tài)規(guī)劃算法。我寫了代碼。

http://72891.cn/forum.p ... age%3D1#pid22286448

   
作者: new_ray    時間: 2012-09-22 07:09
呵呵,寫完后就發(fā)現(xiàn)自己寫錯了,后來又有了一種想法。仍然是先排序,得到c1,c2,c3..c2n。然后將cn+1,cn+2...c2n數(shù)據(jù)與前面的進行交換。每次選取的值都是要是差值最小(>0)的數(shù)對。
1.若使得cn+1,cn+2...c2n與c1,c2...cn的差值變大時就結(jié)束。
2.若cn+1,cn+2...c2n與c1,c2...cn的差值為負數(shù)時,如果負數(shù)的絕對值變小時仍然交換。
3.再將c1,c2...cn與與后面的進行交換。每次選取的值都是要是也差值最小(>0)的數(shù)對。
4.處理與1,2步驟類似。

呵呵,這樣應該是可以了。
作者: songjun54cm    時間: 2012-09-22 11:33
回復 3# broader


    +1
作者: http80    時間: 2012-09-22 22:09
感覺好難的樣子
作者: Hadron74    時間: 2012-09-23 18:04
回復 3# broader

這個算法有問題,每兩個絕對值最小,不一定是總和最小。正確解法見我從《編程之美》學的算法。見帖子:
    http://72891.cn/thread-3770708-1-1.html
作者: Hadron74    時間: 2012-09-23 18:10
本帖最后由 Hadron74 于 2012-09-23 18:40 編輯

回復 70# new_ray

如果不遍歷所有交換是不可能到最優(yōu)的。看我上一個帖子。

但是處理所有的交換,原則上解決了,問題是你如何遍歷所有的交換,其算法復雜程度如何?請給出程序。

這個一個典型的最優(yōu)化問題,必須遍歷所有解空間。
如果不考慮問題的整數(shù)性,其算法復雜度最好的可能是按我寫的0-1背包程序,請參考我的程序。
當然如果有更快的算法,我也希望向你學習。

如果是整數(shù),動態(tài)規(guī)劃算法的復雜性好得多。


   
作者: Hadron74    時間: 2012-09-23 18:45
本帖最后由 Hadron74 于 2012-09-23 18:56 編輯

回復 71# songjun54cm

那是錯誤的方法。
   
作者: webdna    時間: 2012-09-27 10:30
就華為兩個字,引無數(shù)人看這個帖
作者: kangxuechao    時間: 2012-10-09 23:48
本人新建了一個500 的python QQ 群, 群號:  248814126,  歡迎加入。!
作者: dylan_yiu    時間: 2012-10-10 10:04
本帖最后由 dylan_yiu 于 2015-04-27 18:03 編輯

xxxxxxxxxxxxx
作者: nheddd113    時間: 2012-10-10 20:51
def changelist(aList,bList):
        cList=[]
        cList=aList + bList
        del aList,bList
        aList=[]
        bList=[]
        cList.sort()
        count=0
        for i in cList:
                count+=1
                if count % 2 ==0:
                        bList.append(i)
                        count+=1
                        if len(bList)-len(aList)>=1:
                                count+=1
                else:
                        aList.append(i)
        return(aList,bList)

這樣不知道算不算是
作者: Hadron74    時間: 2012-10-11 08:45
回復 79# nheddd113

你這個程序的算法有問題。不能保證最優(yōu)化條件。詳細請看我以前的帖子。
   
作者: nheddd113    時間: 2012-10-11 10:17
回復 80# Hadron74

我看了一下. 好象是一樣.呵呵.看來不過關(guān)了

   
作者: xinxinhao    時間: 2013-03-01 11:59
本帖最后由 xinxinhao 于 2013-03-01 12:01 編輯

回復 1# 天魔封神霸


這個問題很簡單吧 ,技巧即可,求相差最小,先求最大,再反過來不就是最小咯 ?

最小的意思是 (所有最小的和) 減去 (所有最大的和)  === 相差結(jié)果 最小了

(最小 當然可是是負數(shù)。


a=[1,45435,54,67,545]
b=[54,656,76576,2,54]

c=a+b
c=c.sort()

a=c[0:len(a)]
b=c[len(a):]

此時 和相差最小

====完了,就這么簡單=====
作者: 523066680    時間: 2013-03-01 21:55
opengl用戶路過
作者: pitonas    時間: 2013-03-07 09:57
webdna 發(fā)表于 2012-09-27 03:30
就華為兩個字,引無數(shù)人看這個帖
不算廣告吧
作者: 酷了個cool    時間: 2013-03-22 15:35
a[1,5,3,9,2]
b[0,7,8,4,6]
c=[1,5,3,9,2,0,7,8,4,6]
c=[0123456789]
a   b
0   9
8   1
7   2
3   6
4   5
這樣?
作者: ArtsCrafts    時間: 2013-03-25 10:53
假設(shè)a=[5,4,8,6,10] b=[15,13,10,18,20]
(1)將兩個序列合并為一個序列,并且排序.得到序列[4,5,6,8,10,10,13,15,18,20]。
(2)在將該序列切分為((4,5),(6,,(10,10),(13,15),(18,20))。
(3)按照大小交替分配,假設(shè)A第一次去小的數(shù)也就是4,那么下一次它將取打的數(shù)也就是8.這樣依次交替著取。
(4)最后取得a,b序列a=[4,8,10,15,18], b=[5,6,10,13,20],最后兩序列之差為1。
不知這種想法對不對。

作者: ArtsCrafts    時間: 2013-03-25 19:42
代碼貼出來:
  1. def cross(a, b):
  2.         temp = a + b
  3.         temp.sort()
  4.         i = j = k = 0
  5.         for n in range(0, len(temp), 2):
  6.                 if k%2 == 0:
  7.                         a[i] = temp[n]
  8.                         b[j] = temp[n+1]
  9.                 else:
  10.                         a[i] = temp[n+1]
  11.                         b[j] = temp[n]
  12.                 i = i + 1
  13.                 j = j + 1
  14.                 k = k + 1
  15. def sum(a):
  16.         s = 0
  17.         for i in a:
  18.                 s = s + a
  19.         return s
  20. a = [5, 4, 8, 6, 10]
  21. b = [15, 13, 10, 18, 20]
  22. cross(a, b)
  23. print sum(a) - sum(b)
復制代碼

作者: 沒把兒菜刀    時間: 2013-11-07 20:35
回復 82# xinxinhao


    擦,我理解錯了,簡單問題復雜化。
我是把a和b兩個列表合二為一成c,sort,reverse,然后把a和b清零,從c里從大到小往a和b兩遍分配,每次用一個求和函數(shù)看那邊兒小就往那邊兒加,保證兩串和的差別最小。不過原題說的是“交換兩串元素”,也就是說兩串的長度都是不變的

那我倒敘了之后按照大小一邊兒一個就行了吧?
作者: 沒把兒菜刀    時間: 2013-11-07 20:38
回復 82# xinxinhao


    你這個結(jié)果不能保證是兩個串互相“交換”元素能得到的結(jié)果吧……
作者: 沒把兒菜刀    時間: 2013-11-07 20:49
回復 40# tangboyun


    我怎么覺得這個答案是錯的,37樓的那個才是對的呢?因為原題的前提是“交換兩個串里的元素”,而您這個算法其實把原來兩個列表里頭的元素徹底打亂了,得出來的不一定是能夠通過“交換元素”得到的結(jié)果
作者: 初識orcl    時間: 2013-11-08 13:53
頂起來,小伙伴們加油
作者: xiaot7151    時間: 2013-11-24 20:43
數(shù)學上的解法是 把兩個序列 合并到一起 ,然后任意取N個,這N個的和減去剩下N個和的絕對值存入一個數(shù)組。共有 C2N(N) 種取法,所以結(jié)果數(shù)組長度是 2N!/N!, 然后取這個數(shù)組里面最小的正整數(shù)··

Python代碼如何實現(xiàn)就不太清楚了··
作者: xiaot7151    時間: 2013-11-24 20:46
繼續(xù)補充 -每一次取都要把相應的取出N個數(shù)再次存入一個數(shù)組(這樣可以在再后計算出最小差值后能返回到對應的N個數(shù))。感覺這程序性能跑起來會比較有問題,如果N比較大的話。。回復 92# xiaot7151


   
作者: freeterman    時間: 2013-11-26 10:56
回復 1# 天魔封神霸


#!/usr/bin/env python
a = [3, 8, 11, 8, 234]
b = [1, 2, 7, -21, 567]
x = y = 0
minSum = abs(sum(a)) - abs(sum(b))
while x < len(a):
    while y < len(b):
        a[x], b[y] = b[y], a[x]
        temp = abs(abs(sum(a)) - abs(sum(b)))
        if minSum < temp:
            a[x], b[y] = b[y], a[x]
        else:
            minSum = temp
        y = y + 1
    x = x + 1
    y = 0
print minSum
作者: freeterman    時間: 2013-11-26 11:05
使[序列a元素的和]與[序列b元素的和]之間的差最小
回復 82# xinxinhao


   
作者: zengbo1019    時間: 2013-11-28 14:22
這樣可以么

def exchange(list1, list2):
   
    for i in range(len(list1)):
        for j in range(len(list2)):
            
            dvalue1=abs(sum(list1)-sum(list2))
            
            temp1 = list1[i]
            temp2 = list2[j]
            
            sum1 = sum(list1) + temp2 - temp1
            sum2 = sum(list2) + temp1 - temp2
            
            dvalue2=abs(sum1-sum2)
            if dvalue2 < dvalue1:
                list1[i] = temp2
                list2[j] = temp1

    print list1,sum(list1)
    print list2,sum(list2)
   
if __name__=="__main__":

    list1 = [10001,10000,100]
    list2 = [90,50,1]
    exchange(list1, list2)

[1, 10001, 100] 10102
[10000, 90, 50] 10140
作者: hejekele    時間: 2015-02-04 11:29
本帖最后由 hejekele 于 2015-02-04 11:30 編輯
  1. def change(alist=[], blist=[]):
  2.     asum = sum(alist)
  3.     bsum = sum(blist)

  4.     if asum == bsum:
  5.         return alist, blist

  6.     avg = (asum + bsum)/2

  7.     alist.sort()
  8.     alist.reverse()
  9.     blist.sort()


  10.     alen = len(alist)
  11.     blen = len(blist)

  12.     delta = abs(avg - asum)

  13.     for i in xrange(alen):
  14.         for j in xrange(blen):
  15.             tmp = alist[i] - blist[j]
  16.             if tmp <= 0:
  17.                 break
  18.             elif tmp <= delta:
  19.                 alist[i], blist[j] =  blist[j], alist[i]
  20.                 return change(alist, blist)
  21.     return alist, blist


  22. def call_change(alist=[], blist=[]):
  23.     asum = sum(alist)
  24.     bsum = sum(blist)
  25.     if asum < bsum:
  26.         a,b = change(blist, alist)
  27.         return b, a
  28.     else:
  29.         return change(alist, blist)
復制代碼

作者: inpool    時間: 2015-02-05 09:52
思路:
合并兩個列表,排序,然后按順序從后往前每次取兩個元素a, b,則a >= b
將取出來的數(shù)按a-b的值b進行分組
將分組按a-b的值排序然后合并,得到一個長為n的列表listab = [(a1,b1), (a2,b2), (a3,b3), ..., (an,bn)]
可證(listab[0] - listab[1]) >= (listab[i-1][0] - listab[i-1][1])  (0<= i < n)
定義兩個空序列l(wèi)ista, listb
然后按從后往前的順序取出listab的值并根據(jù)sum(lista)-sum(listb)的值,將ai,bi壓入數(shù)組lista或listb
壓入第一個時,abs(sum(lista) - sum(listb))最大,然后逐漸減小。
這個算法簡單,實現(xiàn)也簡單,思考5分鐘,代碼3-5分鐘。
  1. def min_sub_of_sum(lista, listb):
  2.     listab = lista + listb
  3.     listab.sort()
  4.     tmp = {}
  5.     while listab:
  6.         a = listab.pop()
  7.         b = listab.pop()
  8.         tmp.setdefault(a-b, []).append((a, b))
  9.     subs = tmp.keys()
  10.     subs.sort()
  11.     for sub in subs:
  12.         listab.extend(tmp[sub])
  13.     lista, listb = [], []
  14.     # sub == sum(lista) - sum(listb)
  15.     sub = 0
  16.     while listab:
  17.         if sub < 0:
  18.             a, b = listab.pop()
  19.         else:
  20.             b, a = listab.pop()

  21.         lista.append(a)
  22.         listb.append(b)
  23.         sub += (a - b)
  24.     return lista, listb


  25. if __name__ == '__main__':
  26.     lista = range(100)
  27.     listb = [i^11 for i in lista]
  28.     a, b = min_sub_of_sum(lista, listb)
  29.     print a
  30.     print b
  31.     print sum(a) - sum(b)
復制代碼

作者: turtle264    時間: 2015-04-07 23:39
1. 兩個列表合成一個大的,并且求所有數(shù)的和除以2,假定是M
2.經(jīng)過第一步,這個問題變成了0-1背包問題,背包容量是M
作者: vity    時間: 2015-04-13 11:08
bskay 發(fā)表于 2012-08-29 11:35
偽動態(tài)規(guī)劃的,

#動態(tài)規(guī)劃問題



問題就是在數(shù)組a[n]中查找m個數(shù)據(jù)數(shù)據(jù)之和為指定數(shù)據(jù)取整(sum / 2),如果能找到,就結(jié)束,如果不能就找  [sum / 2] - 1,逐漸找下去。
至于優(yōu)化的事情可以慢慢考慮。




歡迎光臨 Chinaunix (http://72891.cn/) Powered by Discuz! X3.2