Вы можете попробовать сделать это с помощью динамического программирования.
Пусть dp[k] будет равно списку элементов с суммой размеров, равной k. Изначально d[0] = [] и dp[k] = None для k > 0. Размер списка может быть ограничен суммой размеров всех элементов, назовем его S.
Что делает алгоритм, так это то, что для каждого item он переходит от i = S до i = 0 и проверяет, соответствует ли dp[i] != None, что означает, что мы знаем, что можем выбирать элементы с суммой размеров, равной i. Эти элементы находятся в списке dp[i]. Заметим, что мы можем добавить текущее item в этот список и получить набор элементов с суммой, равной i + item.size. Итак, мы назначаем dp[i + item.size] = dp[i] + [item]. Обработав все элементы, нам просто нужно начать с желаемой суммы размеров и двигаться в обоих направлениях, чтобы найти наиболее близкое соответствие.
Код:
items = [("ITEM01", 100, 10000), ("ITEM02", 24, 576), \
("ITEM03", 24, 576), ("ITEM04", 51, 2500), ("ITEM05", 155, 25)]
S = sum([item[1] for item in items])
dp = [None for i in xrange(S + 1)]
dp[0] = []
for item in items:
for i in xrange(S, -1, -1):
if dp[i] is not None and i + item[1] <= S:
dp[i + item[1]] = dp[i] + [item]
desired_sum = 150
i = j = desired_sum
while i >= 0 and j <= S:
if dp[i] is not None:
print dp[i]
break
elif dp[j] is not None:
print dp[j]
break
else:
i -= 1
j += 1
вывод:
[('ITEM01', 100, 10000), ('ITEM04', 51, 2500)]
Однако сложность этого решения составляет O(n*S), где n — количество элементов, а S — сумма размеров, поэтому для некоторых целей оно может быть слишком медленным. Что можно улучшить в этом решении, так это константу S. Например, вы можете установить S в 2 * desired_sum, потому что у нас есть гарантия, что мы можем взять набор элементов с суммой размеров в [0, 2 * desired_sum] (возможно, пустой набор с суммой 0). Если вы хотите взять хотя бы один предмет, вы можете взять S = max(min_item_size, 2 * desired_sum - min_item_size), где min_item_size — это минимальный размер всех предметов.
ИЗМЕНИТЬ:
О, вы также хотели получить максимальное значение, когда две комбинации одинаково близки к desired_size. Затем вам нужно немного чередовать код, чтобы сохранить лучшие комбинации для каждой суммы размеров.
А именно:
if dp[i] is not None and i + item[1] <= S:
должно быть:
if dp[i] is not None and i + item[1] <= S and \
(
dp[i + item[1]] is None
or
sum(set_item[2] for set_item in dp[i]) + item[2]
> sum(set_item[2] for set_item in dp[i + item[1]])
):
(немного некрасиво, но я не знаю, как разбить строки, чтобы это выглядело лучше)
Конечно, вы можете сохранить эти суммы, чтобы не вычислять их каждый раз.
20.03.2013
