В итоге я сделал полный перебор с исключением заведомо неоптимальных решений. Судя по википедии, это "Метод ветвей и границ". По моим наблюдениям, в зависимости от исходных данных, обсчёт набора из 25 чисел может занять от всего ~20 и вплоть до 3.5М циклов. На Python 2.7:
# -*- coding: utf-8 -*-
from random import randint
from itertools import combinations
#data = [53, 50, 74, 4, 11, 68, 65, 50, 25, 84, 65, 63, 14, 54, 49, 17, 65, 48, 74, 66]
data = [randint(1,100) for i in xrange(25)]
#data = [990,1,2,3,1000]
data.sort(reverse=True)
limit = float(sum(data))/2
# Pre-calculate min and max possible number of elements in a group
bounds = [0, 0]
for i in (0,1):
maxsum = 0
for n, item in enumerate(data[::(1,-1)[i]], 1):
cursum = maxsum + item
if cursum <= limit:
maxsum = cursum
else:
bounds[i] = n - int(n > 1)
break
nmin, nmax = bounds
# Main calculations
maxsum, cycles = 0, 0
for n in xrange(nmin, nmax+1):
# The following check could be efficient with integer numbers, not float
if maxsum == limit:
# One of exact solutions has been found
break
else:
# Iterate through all possible combinations:
# combinations('ABCD', 2) --> AB AC AD BC BD CD
for vector in combinations(data, n):
cycles += 1
cursum = sum(vector)
if maxsum < cursum <= limit:
maxsum = cursum
solution = vector
# The following check could be efficient with integer numbers, not float
if maxsum == limit:
# One of exact solutions has been found
break
elif cursum <= maxsum:
# No reason to continue because data is sorted in descending order
# and all of the following sums in this loop will be even smaller
break
# Print result
print 'data =', data
print 'nmin =', nmin
print 'nmax =', nmax
print 'solution =', solution
print 'cycles =', cycles
print 'limit =', limit
print 'sum =', maxsum
Средний
