жадный множественный рюкзак (минимизировать/уменьшить количество ящиков)

Question

Фактически, у меня уже есть частичный ответ на этот вопрос, но мне интересно, можно ли обобщить этот маленький кусочек жадного кода на что-то более близкое к оптимальному решению.

, как я встретил эту проблему (не соответствующее для самой проблемы, но может быть интересна):

Я получаю большую коллекцию объектов (это набор профилей дамб, и каждую дамба сохраняет более или менее одна и та же форма вдоль его длины), я могу группировать их в соответствии с свойством (название дайки). вывод моей программы идет на внешнюю программу, которую мы должны вызывать вручную (не спрашивайте меня почему) и которая не может восстановиться после сбоев (одна ошибка останавливает всю партию).

в приложении, в котором я использую это, нет жесткого требования по количеству контейнеров, ни максимального размера бункеров, что я пытаюсь сделать, это

• держать количество групп низкий (вызывают программу несколько раз.)
• сохраняйте наборы маленькими (уменьшите повреждение, если пакет не сработает)
• сохраняйте похожие вещи вместе (сбой в группе, вероятно, является провалом во всей группе).

У меня не было много времени, так что я написал небольшую жадную функцию, что группы устанавливают вместе.

коллега предложил мне добавить некоторый шум к данным, чтобы исследовать окрестности приближенного решения, которое я нахожу, и нам было интересно, насколько далеки от оптимальных решений.

не то, что это относится к исходной задаче, которая не нуждается в истинном оптимальном решении, но я думал, что поделился бы вопросом с сообществом и посмотрю, какие комментарии выходят из него.

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 

Answer 1

Мне нравится идея вашего коллеги, чтобы добавить некоторые данные шума, но может быть лучше сделать несколько свопов ordered после вызова ordered = sorted(orig)?