группировка списка предметов по кумулятивному размеру с ограничением по размеру групп

Question

Я пытаюсь найти способ сгруппировать список из [name, size] пар. Идея состоит в том, чтобы группировать их вместе, чтобы каждая группа была как можно ближе к maximum_group_size, но не нарушая обрезание maximum_group_length.

Например, если maximum_group_size = 10 и maximum_group_length = 3, то следующий простой набор данных можно сгруппировать так:

data = [['A', 3], ['B', 6], ['C', 7], ['D', 1]] 
grouped: [[['A', 3], ['B', 6]], [['C', 7], ['D', 1]]] 

Но этот набор данных будет в конечном итоге, как:

data = [['A', 1], ['B', 1], ['C', 1], ['D', 1]] 
grouped: [[['A', 1], ['B', 1], ['C', 1]], ['D', 1]]] 

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

Как я могу (красиво) сделать это? Моя текущая реализация не очень элегантна:

def group_references(sam_handle, num_bases=10 ** 7, max_seqs=100): 
    """ 
    Group up references by num_bases, unless that exceeds max_seqs. 
    """ 
    name_iter = itertools.izip(*[sam_handle.references, sam_handle.lengths]) 
    name, size = name_iter.next() 
    this_bin = [[name, size]] 
    bin_base_count = size 
    num_seqs = 1 
    for name, size in name_iter: 
     bin_base_count += size 
     num_seqs += 1 
     if bin_base_count >= num_bases or num_seqs > max_seqs: 
      yield this_bin 
      this_bin = [[name, size]] 
      bin_base_count = size 
      num_seqs = 1 
     else: 
      this_bin.append([name, size]) 

Answer 1

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

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

Answer 2

Ваша проблема Bin packing problem или Packing problem.

Посмотрите на similar question, где вы можете найти кусочек кода в python.