我有嵌套长度的问题，请建议我解决这个问题的最佳方法。我的问题如下。
我有一些标准长度可以说总长度（这是我们需要用一些特定长度块填充的总长度）
输入是长度块的列表，例如：5000、4000、3000
每个块之间的间隙是一个范围，例如：200到500（这个间隙可以在范围内调整）
现在我们必须用上述可用长度块填充总长度，每个块之间有间隙，并且该间隙应该在上面给出的间隙范围内。
请给我一些解决这个问题的方法。
预先感谢...
问候， 阿尼尔
问问题
555 次
1 回答
0
这个问题本质上是带有小转折的子集和问题。您可以使用与子集和相同的伪多项式时间解决方案：创建一个长度为“总长度”的数组（我们从现在开始称为n），并且对于每个长度k，将其添加到数组中的每个现有长度（所以如果元素m已填充，则在m + k处创建一个新条目（如果m + k ≤ n），但将现有条目也保留在m处），以及在位置k处创建一个新数组条目，表示创建一个新套装。您可以在数组元素i处建立一组条目，以表示总计i的长度块列表集. 每个集合条目都应该链接回它来自的数组条目，它可以通过简单地存储让你到达那里的最后一个长度来做到这一点。这类似于我最近在这里回答的一个问题，您可以调整它以允许您认为合适的重复。
但是，您需要修改上述方法以弥补差距。让我们称每个元素x之间的最小间隙和最大间隙y。添加长度为k的条目时，我们在将其添加到另一个条目时包含最小间隙（因此，如果填充了m，我们实际上在m + k + x处创建条目）。我们继续在k处创建初始条目，因为我们包括元素之间的间隙。当我们创建一个条目时，我们还可以确定它是否填满了空间。假设新条目包含t个元素并且总共有m个。然后它填充空间当且仅当m ≥ n - t ( y - x）。如果它填满了空间，我们应该将它添加到解决方案列表中。根据您想要多少解决方案，您可以在找到足够的解决方案后立即终止算法，或者让它找到所有解决方案。最后，只需遍历解决方案列表。
范围内的任何内容都可以通过多种不同方式中的任何一种来表示其差距，但一种有效的方法是贪婪地分配“slack” - 例如，如果您使用上面的示例距离新的总长度 1000，您可以将前三个间隙选择为 500（每个间隙增加 300，总共额外增加 900），然后将第四个间隙选择为 300（对于额外的 100 间隙，总计 1000），并且每个额外间隙应该是最小值（200）。
于 2012-05-30T07:25:19.387 回答