.net - 一种对加权对象列表进行排序和分组的算法

Question

我有很多数据 block 。

为了论证我们假设它们是

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

对于传输，我可以将它们打包成最大 300Kb 的有效负载。

如果您只是按顺序遍历它们

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 中对此进行编码，但如果您可以提供另一种语言或伪代码实现/描述的示例，那也很棒。

谢谢， 伊因C

Answer 1

您的问题正是 Bin packing不幸的是 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]);