Алгоритм сортировки и группировки списка взвешенных объектов

Question

У меня есть несколько порций данных.

В качестве аргумента мы скажем, что они

File 1 - 150Kb
File 2 -  50Kb
File 3 -  70Kb
File 4 -  60Kb
File 5 -  70Kb
File 6 - 100Kb
File 7 -  90Kb

Для передачи я могу упаковать их в максимальную полезную нагрузку 300 КБ.

Если вы просто выполните итерацию по ним, чтобы получить

TRANS1: 150Kb + 50Kb + 70Kb = 270Kb - the next file puts you over the limit of 300Kb
TRANS2: 60Kb + 70Kb + 100Kb = 230Kb - the next file puts you over the limit of 300Kb
TRANS3: 90Kb

Итак, три отдельные передачи.

Но если вы реорганизуете их, вы можете отправить

Files 1,2,6 together = 300Kb
Files 3,4,5,7 together = 290Kb

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

Есть ли какой-нибудь алгоритм сортировки вокруг этого вида оптимизации, который возьмет список взвешенных объектов и отсортирует / сгруппирует их так, чтобы вы закончили с наименьшим количеством групп

Для справки, я бы кодировал это в .NET, но если бы вы могли предоставить и пример на другом языке или реализацию / описание псевдо-кода, это было бы также здорово.

Спасибо, Эоин С

Answer 1

Ваша проблема в точности Бункерная упаковка , которая, к сожалению, NP-Complete :( Если количество пакетов довольно мало, вы можете использовать любую возможную комбинацию.

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

const int INF = 1000000;
const int MAXSIZE = 300;
int DP[NumberOfPackets][MaxPayload];

int solve(int packetNum, int sizeUsed)
{
   if (packetNum == NumberOfPackets)
      return 0;

   if (DP[packetNum][sizeUsed] != -1)
      return DP[packetNum][sizeUsed];

   int res = INF;

   //Try to put the packet in the current group
   if (sizeUsed + size[packetNum] <= MAXSIZE) 
      res = min(res, solve(packetNum + 1, sizeUsed + size[packetNum]));

   //Try to start another group with the current packet
   res = min(res, solve(packetNum + 1, size[packetNum]) + 1);

   return DP[packetNum][sizeUsed] = res;
}

int answer = solve(1, size[0]);

Answer 2

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

Вы можете использовать этот поиск Google для реализации.

Answer 3

Это напоминает мне о проблеме Рюкзак . Я не следил за этим, но я помню, что это NP-полная проблема: читать «трудно». В основном вам нужно найти компромисс между «правильным» и «быстрым».

Это не значит невозможное, но это, безусловно, область, где совершенство - враг добра.

Я бы начал с подхода "Big Rocks First", запустил пару симуляций. Держите лучшее решение. Используйте ограниченное время, чтобы прервать поиск и используйте лучший из найденных на данный момент.