找出装箱问题的所有可能变化

Question

为了我的任务，我必须编写一个装箱算法，其中有 N 个不同体积的对象。它们都必须装在 V 卷的盒子里。使用降序排序，我成功地编写了算法。但另一项任务包括写出我之前发现最有效的一定数量的箱子包装的所有可能变化。例如：

有 4 个物体的体积：4、6、3、2。盒子的体积是 10。使用装箱算法我发现我需要 2 个盒子。

所有可能的变化是：

4,6 and 3,2
4,3 and 6,2
4,2 and 6,3
6   and 4,3,2

我无法为这个问题想出合适的算法，我应该从哪里开始？任何帮助将不胜感激。

Answer 1

解决这个问题的一般算法是这样的：

通过将所有可能的拆分配置创建到 n 组中，尝试将所有对象放入 n 容器中，并测试是否有任何此类配置适合垃圾箱。

如果不行，增加n再试一次。

现在，你如何找到所有可能的拆分配置？

考虑在每个对象上贴上标签，以决定它属于哪个垃圾箱。如果您有 3 个对象和 2 个箱子，那么每个对象都可以获得标签 0 或 1（对于两个箱子中的任何一个）。这使得 2^3 = 8 组合：

现在也清楚了如何创建所有组合。您可以使用计数器并将其转换为箱数的基数（在本例中为 2），并将数字用作标签。还有其他选择，例如。 G。您可以使用递归解决方案。我更喜欢那个。

当你有一个解决方案时，你只需要检查每个箱子的这个标签对象的体积总和不大于箱子大小。

这里是一些伪代码，用于递归创建所有组合的列表：

combinations(object_counter, bin_counter) {
    if (object_counter == 0) {
        return [[]]  // a list of one empty list
    }
    result = []  // empty list
    for i in 0 .. bin_counter-1 {
        sub_results = combinations(object_counter-1, bin_counter)
        for sub_result in sub_results {
            result.append([i] + sub_result)
        }
    }
    return result
}

找出装箱问题的所有可能变化

Finding all possible variations in a Bin-Packing Problem

c++

algorithm

bin-packing