- 论坛徽章:
- 11
|
这个问题完全可以转化为这个问题
从M个数里面找出N个,让他们的和尽量接近 P
M=2N
P=sum(M2n)/2N
用动态规划来解
class nlist:
"""从M个数里面找出N个,让他们的和尽量接近 P
"""
def __init__(self):
self.nums_m = [] # M个数的数组
self.value_n= 0 # N的值
self.value_p= 0 # P的值
self.nums_n = [] #被选定的N个数
self.sum_n = 0 #N个数的和的快照
self.nums_l = [] #剩下的M-N个数
return
#
def main(self,mlist,N,P):
"""计算入口
从M个数里面找出N个,让他们的和尽量接近 P
1. 对M个数排序,从小到大
2. 取前N个作为和 的初始值
3. 考虑替换 其中一个数,导致和增加最小的,此时交换两个数
4. 重复子问题 当 和<P
"""
self.nums_m[:] = mlist
self.value_n,self.value_p = N,P
self.nums_m.sort()
self.nums_n[:] = self.nums_m[:N]
self.nums_l[:] = self.nums_m[N:]
self.sum_n = sum(self.nums_n)
while self.sum_n < P:
a,b = self.find_min()
if a is None:
break
#预测交换a,b后,后的和是否更接近P
d1 = P-self.sum_n
d2 = d1 - (b-a)
if d2 < 0 and d1<=-d2:
break
self.change(a,b)
continue
return self.nums_n,self.sum_n
#
def find_min(self):
"""
从self.NumN中找出a,self.NumL中找出b
使得交换a,b后导致self.sum是增加的,并且增加的量是最小
"""
a,b = None,None
for i in self.nums_n:
for j in self.nums_l:
if i < j and (not a or j-i<b-a):
a,b = i,j
return a,b
def change(self,a,b):
self.sum_n += b-a
self.nums_n.remove(a)
self.nums_n.append(b)
self.nums_l.remove(b)
self.nums_l.append(a)
return
for n in range(100+1):
nlist().main([1,1,2,3,5,10,20,30,30,50,50,100,],5,n)
|
|