на самом деле, у меня уже есть частичный ответ на этот вопрос, но мне интересно, можно ли этот небольшой фрагмент жадного кода обобщить до чего-то более близкого к оптимальному решению.
как я столкнулся с этой проблемой (не относится к самой проблеме, но может быть интересно):
Я получаю большую коллекцию объектов (это набор профилей дамб, причем каждая дамба сохраняет более-менее одинаковую форму по своей длине), могу сгруппировать их по признаку (название дамбы). вывод моей программы передается внешней программе, которую мы должны вызывать вручную (не спрашивайте меня, почему) и которая не может восстановиться после сбоев (одна ошибка останавливает всю партию).
в приложении, где я это использую, нет жестких требований ни к количеству корзин, ни к максимальному размеру корзин, что я пытаюсь сделать, так это
- держите количество групп низким (вызовите программу несколько раз).
- сохраняйте наборы небольшими (уменьшайте ущерб, если партия выходит из строя)
- держите похожие вещи вместе (неудача в группе, вероятно, является неудачей во всей группе).
У меня было не так много времени, поэтому я написал небольшую жадную функцию, которая группирует наборы вместе.
коллега предложил мне добавить немного шума к данным, чтобы исследовать окрестности найденного мной приближенного решения, и нам было интересно, насколько далеки найденные решения от оптимальных.
не то, чтобы это имело отношение к исходной задаче, которая не нуждается в действительно оптимальном решении, но я подумал, что поделюсь вопросом с сообществом и посмотрю, какие комментарии появятся.
def group_to_similar_sizes(orig, max_size=None, max_factor=None):
"""group orig list in sections that to not overflow max(orig) (or given max_size).
return list of grouped indices, plus max effective length.
>>> group_to_similar_sizes([1, 3, 7, 13])
([[2, 1, 0], [3]], 13)
>>> group_to_similar_sizes([2, 9, 9, 11, 12, 19, 19, 22, 22, ])
([[3, 1], [4, 2], [5], [6, 0], [7], [8]], 22)
result is independent of original ordering
>>> group_to_similar_sizes([9, 19, 22, 12, 19, 9, 2, 22, 11, ])
([[3, 1], [4, 2], [5], [6, 0], [7], [8]], 22)
you can specify a desired max size
>>> group_to_similar_sizes([2, 9, 9, 11, 12, 19, 19, 22, 22, ], 50)
([[3, 2, 1], [6, 5, 4], [8, 7, 0]], 50)
if the desired max size is too small, it still influences the way we make groups.
>>> group_to_similar_sizes([1, 3, 7, 13], 8)
([[1], [2, 0], [3]], 13)
>>> group_to_similar_sizes([2, 9, 9, 11, 12, 19, 19, 22, 22, ], 20)
([[1], [3, 2], [4, 0], [5], [6], [7], [8]], 22)
max size can be adjusted by a multiplication factor
>>> group_to_similar_sizes([9, 19, 22, 12, 5, 9, 2, 22, 11, ], max_factor=0.75)
([[2], [3], [4, 1], [5, 0], [6], [7], [8]], 22)
>>> group_to_similar_sizes([9, 19, 22, 12, 5, 9, 2, 22, 11, ], max_factor=1.5)
([[2, 1], [6, 5], [7, 3, 0], [8, 4]], 33)
"""
ordered = sorted(orig)
max_size = max_size or ordered[-1]
if max_factor is not None:
max_size = int(max_size * max_factor)
orig_ordered = list(ordered)
todo = set(range(len(orig)))
effective_max = 0
result = []
## while we still have unassigned items
while ordered:
## choose the largest item
## make it member of a group
## check which we can still put in its bin
candidate_i = len(ordered) - 1
candidate = ordered.pop()
if candidate_i not in todo:
continue
todo.remove(candidate_i)
group = [candidate_i]
group_size = candidate
for j in sorted(todo, reverse=True):
if orig_ordered[j] + group_size <= max_size:
group.append(j)
group_size += orig_ordered[j]
todo.remove(j)
result.insert(0, group)
effective_max = max(group_size, effective_max)
return result, effective_max
