Максимизировать сумму нескольких ведер?

Question

Имейте 180 шаров.

Имеют 70 ковшей.

значение каждого шара зависит от того, ведра это в:

ball1 = { 1, 14, 2, 3, 4 ... } //70 values in total for each bucket 
ball2 = { 24, 2, 23, 2, 5 ... } 
... 

Каждый ковш имеет максимальное количество шаров она может нести, но общее количество шаров 70 ведер могут нести 180, то есть все 180 шаров точно подойдет. (каждое ведро должно нести не менее 1 шара)

{bucket1, 3} {bucket2, 1} { bucket3, 2} {bucket4, 1} ... 

Как вы максимально можете разместить мяч на этом?

Я попытался выполнить команду bruteforce и быстро пожалел об этом после подсчета количества перестановок.

Answer 1

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

Чтобы сделать эту проблему проще, скажем, у нас есть 3 шаров и 2 ведра:

Ball 1: {1, 10}, 
Ball 2: {9, 20}, 
Ball 3: {7, 9}; 

Bucket 1: 2 
Bucket 2: 1 

, и я хотел бы построить график вроде следующего:

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

Answer 2

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

Мой первый подход был бы вдоль линий моделируемых отжига:

1) Поместите шары в произвольном порядке (в зависимости от вашей, по крайней мере один мяч в каждой из ведра ограничения)

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

3) Рассмотрите операции, такие как случайное перемещение двух шаров, перемещение одного шара в другое ведро (если допускает ограничение).

4) пересчитывать целевую функцию

5) Всегда принять изменения, если целевая функция лучше, но и (и это важно), принять изменения также, если целевая функция хуже с вероятность, что затухает exp (-констант * время). (Это называется температурной функцией).

6) Идите снова.

Этот подход позволит хорошим ведрам склеиваться и на ранних этапах позволяет государству отскакивать от локального максимума. Наука здесь должна найти хорошее значение для «постоянного».

http://en.wikipedia.org/wiki/Simulated_annealing См