algorithm - 将元素放入多个容量袋中的最佳解决方案

Question

我一直在研究这个问题 ( https://github.com/alexpchung/File-Distribution-Planning/blob/master/README.pdf )，我需要找到一个最佳解决方案来将文件放在节点中。

这是我目前使用的算法

• 设节点数为N。

• 跟踪每个节点迭代的可用文件大小每个文件，它都有 N 个选择(假设文件适合等)

• 对每个递归求值

我想到的另一个解决方案是遍历每个节点并执行背包 0/1。不幸的是，我感到震惊，因为节点大小不固定，这将是一个不正确的解决方案。

如果您有任何指点，那就太好了。

谢谢。

Answer 1

也许您可以对此进行基准测试:

• 对两个列表进行排序。(容量，大小，全部递增)

• 从最大的文件开始。

• 同样从最大的节点开始。
• 检查是否合适
  • true: 放入
  • false:将其放入“失败”列表，因为不存在更大的节点。
• 如果选择的(最大)节点已满，则迭代下一个较小的节点
• 迭代到下一个较小的文件。
• 返回检查步骤直到任一条件为真
  • 已分配所有文件，存在空节点
  • 所有节点已满，存在未放置的文件
• (*) 仅对空白处的节点进行排序(空节点存在=真或两者都为真)
  • 以相反顺序复制节点列表
    • 检查至少“空白空间”d 上的“最新添加的文件”是否适合最大的“空白空间”d 节点，以及转换是否在两个节点上产生相等/平衡的空白空间
      • true: 发送文件到那个节点
      • false:迭代下一个“最少空白空间”节点，因为该文件不能更晚地容纳其他节点
    • 迭代两个列表(并从列表中删除精炼对)
• 如果至少有 1 个文件可以优化，转到 (*)