У меня есть K количество ведер.Каждое ведро содержит некоторое количество шаров, B, где каждый шар имеет некоторый вес.
Мне интересно, есть ли там алгоритмы, которые выполняют следующее:
Я хотел бы сделать один ход за раз и переместить некоторый вес из одного ведра в другое ведро таким образом,это минимизирует максимальный вес, содержащийся во всех ведрах.Я хотел бы повторять этот процесс до тех пор, пока не достигну максимально сбалансированной конфигурации весов в ведрах, приняв наименьшее количество шагов.
Существуют ли алгоритмы, на которые было бы полезно взглянуть при решении этой проблемы?
Вот некоторые подходы, о которых я подумал:
Наивный:Пройдите все комбинации шаров в ведрах и возьмите вариант, который имеет min (max (вес для всех ведер). Это моя оптимальная конфигурация. Теперь перемещайте один шарик за раз, пока вы не достигнете этой конфигурации. Это будет работать, нобыло бы невозможно программировать, потому что у нас есть сложность num_buckets ^ num_balls, которая была бы неэффективной по количеству шаров, были велики.
Жадное дерево: начинайте с нуля и жадно распределяйте шары по лоткам вкруговой режим. На каждой итерации - помещайте мяч в корзину с наименьшим максимумом. Это не даст оптимального баланса, но даст лучший баланс, и тогда я могу сделать один шаг за раз, чтобы достичь этой конфигурации.
Это похоже на проблему, когда у меня есть функция стоимости, и у меня есть BxK nuМотор движется на моем первом шаге.
Существуют ли известные алгоритмы, которые могут вдохновить на лучшее решение?(Упаковка бункеров не будет работать здесь, потому что у меня есть фиксированное количество бинов.) Я не ищу решение, а скорее алгоритмы, которые решают проблемы балансировки, которые похожи на эту, даже если не совсем одинаковы.