Алгоритм утилизации равных выработок

Question

Я работаю над проблемой, аналогичной Bin packing problem.

Проблема

У меня есть несколько бункеров. В каждом бункере содержится несколько предметов с одинаковым весом (например, 1, 2, 5, 10 кг). Количество элементов в каждом бункере отличается. Я должен реализовать алгоритм, который вычисляет количество элементов, которые должны быть распределены, чтобы достичь определенного веса, чтобы в течение большего количества операций бункеры были пустыми примерно в одно и то же время.

Пример

1. В1 имеет 50 элементов с весом 1 кг
2. В2 имеет 90 элементов с весом 2 кг
3. В3 имеет 80 элементов с весом 5 кг
4. B4 имеет 50 элементов с весом 10 кг

алгоритм должен вычислить NU который должен располагать до 45 кг. Алгоритм должен возвращать результат, аналогичный: 10 * B1 + 3 * B3 + 1 * B4 = 45 кг.

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

Answer 1

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

Итак, используйте известный алгоритм упаковки бункеровки (wikipedia article) на вышеупомянутые уменьшенные комплекты ящиков.

Answer 2

Я не думаю, что алгоритм упаковки бункеров это лучшее решение для моей проблемы. Я реализовал алгоритм упаковки наилучшего соответствия. Сначала я сортирую данные по убыванию в зависимости от доступных элементов. Я повторяю все элементы до тех пор, пока не найду решение, или список элементов пуст (решение не найдено). Для следующего случае алгоритм не находит верное решение:

• B1 40 изделий с весом 100
• В2 30 предметов с весом 50
• В3 20 элементов с весом 20

Для веса 350 алгоритм не находит никакого действительного результата.

Result1 (340) 100 50 20 100 50 20 Результат2 (340) 100 50 20 100 50 20 .....