一种用于排序和排序的算法对加权对象列表进行分组

Question

我有很多数据块。

为了论证起见，我们会说它们是

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]);

Answer 2

您正在寻找的是背包算法或对其的修改。
问题无法有效解决，但您可以接近完美的解决方案。

您可以使用此 Google 搜索来实现。

Answer 3

这让我想起了背包问题。我没有跟进它，但我记得这是一个 NP 完全问题：读“难”。您基本上需要在“正确”和“快速”之间找到折衷方案。

这并不意味着不可能，但这显然是完美与优秀的敌人的领域。

我将从“大石头优先”方法开始，运行几次模拟。保留最佳方案。使用有限的时间来中断搜索并使用迄今为止找到的最好的搜索。