Блог

У меня есть n весов, которые весят {A1, A2, …, An}, и я должен разделить их на сегменты таким образом, чтобы требовалось минимальное количество сегментов, и каждый сегмент имеет максимальную емкость Cmax и Aiимейте вес {1,2,3,4,5} и Cmax = 5 Итак, результат должен быть ({1,4},{2,3},{5})

 {2,3,4,5} and Cmax=10
 So, result should be {{5,3,2},{4}} . 
  

другим возможным решением является {5,4}, {3,2 }, но это неприемлемо как.
каждый начальный набор должен быть как можно ближе к Cmax

К сожалению, это NP-сложная задача, поэтому точное решение гарантируется только методом перебора — проверкой всех возможных вариантов. Это возможно для довольно небольшого размера задачи ( n, buckets < 10..15 ) — есть N^Buckets варианты.

В противном случае (обычно в случае n < 100 ) вы можете попробовать некоторые методы дискретной оптимизации, такие как алгоритм ветвления и привязки (прекратить поиск, когда текущее решение становится хуже, чем лучшее, уже найденное)