原帖由 天魔封神霸 于 2009-6-26 14:13 发表
有两个序列a,b，大小都为n,序列元素的值任意整形数，无序；
要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。
http://wiki.services.openoffice.org/w/images/7/7e/Python_po ...
| def look(a, max = 0): a.sort() while 1: if len(a) == 0:return None val = a.pop() if val <= max:return val def ab(a , b): a.extend(b) sum = reduce(lambda x,y:x+y, a) arvg = sum / 2.0 rs1 = [] def qq(arvg, pick = None): if pick is None: pick = a.pop() else: a.remove(pick) rs1.append(pick) arvg -= pick pick = look(a[:], max = arvg) if pick is not None:qq(arvg, pick) qq(arvg) print rs1, a ab([1,2,5,3],[6,7,8,9,10]) |
原帖由 天魔封神霸 于 2009-6-26 14:13 发表
有两个序列a,b，大小都为n,序列元素的值任意整形数，无序；
要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。
http://wiki.services.openoffice.org/w/images/7/7e/Python_po ...
| ruiqingzheng | 发表于 2009-6-28 17:20
|
| #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为优 r = r[:-1] + [i] print r |
| #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] |
原帖由 wudi626 于 2009-7-7 00:07 发表
# coding=gb2312
# 有两个序列a,b，大小都为n,序列元素的值任意整形数，无序；
# 要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。
def FindTargetItem(diff,lst):
for ...
#!/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()
webdna 发表于 2012-09-27 03:30
就华为两个字，引无数人看这个帖
,(10,10),(13,15),(18,20))。
bskay 发表于 2012-08-29 11:35
伪动态规划的，
#动态规划问题
| 欢迎光临 Chinaunix (http://bbs.chinaunix.net/) | Powered by Discuz! X3.2 |
