На самом деле, у меня уже есть частичный ответ на этот вопрос, но мне интересно, можно ли обобщить этот маленький кусочек жадного кода до чего-то более близкого к оптимальному решению.
как я встретилэта проблема (не относится к самой проблеме, но может быть интересна):
Я получаю большую коллекцию объектов (это набор профилей дамб, и каждая дайка сохраняет более или менее одинаковую форму по всей своей длине)Я могу сгруппировать их по свойству (название дамбы).выходные данные моей программы поступают во внешнюю программу, которую мы должны вызвать вручную (не спрашивайте меня, почему), и которая не может восстановиться после сбоев (одна ошибка останавливает весь пакет).
вВ приложении, где я использую это, нет жестких требований ни к количеству бинов, ни к максимальному размеру бинов, я пытаюсь сделать так, чтобы
- сохранял количество групп на низком уровне (вызывайтепрограмма несколько раз.)
- сохраняйте наборы маленькими (уменьшите урон при сбое пакета)
- держите похожие вещи вместе (сбой в группе, вероятно, сбой во всей группе).
У меня не было много времени, поэтому я написал небольшую жадную функцию, которая группирует группы.
один из коллег предложил мне добавить немного шума в данныеисследовать окрестности приближенного решения, которое я нахожу, и нам было интересно, насколько далеки от оптимальных найденные решения.
не то, чтобы это относилось к исходной задаче, которая не нуждается в истинно оптимальном решении, но я подумал, что поделюсь этим вопросом с сообществом и посмотрим, какие комментарии из него получатся.
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