algorithm - 按订单算法组织存储

Question

假设我有很多产品的大存储空间，并且我存储空间中的每个架子都可以存储最多 k 个元素。我还有一个长长的订单清单（每个订单可以包括各种不同的产品）

现在我需要编写一个算法，获取订单列表详细信息作为输入，并返回组织存储的最佳方式。

该算法必须遵循以下条款：

1. 将我的产品分成货架（子组大小 k）
2. 通常放在同一个架子上的产品

我想到了双哈希图 <productName,<productName, counter>> 当每个产品都有一个不同的哈希图来保存它附带的所有产品并计算它附带的次数但我仍然发现很难将它拆分为子组大小 k。你怎么看？有没有更好的算法来组织它，或者可能是一个这样做的库？

标签： algorithmsortingdata-structuresknapsack-problem

Answer 1

这基本上是超图分区（具有连通性目标和对每个部分中节点数量的硬性限制，而不是对 k 个近似平衡部分的需求）。这将优化每个订单所需的平均货架数量。有各种各样的图书馆；KaHyPar可能是目前最好的。