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

Question

在我的任务中，我必须编写一个装箱算法，其中有N个具有不同卷的对象。它们都必须装进第五卷的盒子里。通过减少排序，我成功地写出了算法。但另一项任务包括在我以前发现的最有效的箱子数量中写出所有可能的垃圾桶包装的变化。例如：

有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，然后再试一次。

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

考虑在每个对象上添加一个标记，以决定它属于哪个bin。如果您有3个对象和2个回收箱，那么每个对象都可以得到标记0或1 (对于这两个回收箱中的任何一个)。这使得2^3 =8个组合：

000
001
010
...

现在，我们也清楚了如何创建所有的组合。您可以使用计数器并将其转换为回收箱数量(在本例中为2个)的底部，并将数字用作标记。还有其他选项，例如，您可以使用递归解决方案。我更喜欢那样。

当您有了解决方案时，只需检查每个bin的对象的体积和是否大于bin大小。

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

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
}