java - 递归装箱算法无法扩展

Question

我完成了一项作业，其规范要求:

• 递归解决方案
• 容量 <= 100
• values.length <= 25
• 参数只有容量和索引
• 允许重复值

我花了几个小时研究垃圾箱包装和背包问题。

以下方法可以工作，但效率很低。我得到了一个带有十几个值的堆栈溢出。效率非常低，无法扩展，而且我不知道从哪里开始。

如有建议，我们将不胜感激。是的，这是一项学术作业，但我宁愿解决问题，也不愿放弃并获得 B。

public void calculateCombinations(int capacity, int index) {
    count++;
    if(index < values.length) {
        if(values[index] <= capacity) {
            currentSolution.addLast(index);
            if(values[index] == capacity)
                flushSolution();
            else
                capacity -= values[index];
        }
        calculateCombinations(capacity, index + 1);
    } else
        if(currentSolution.peekLast() != null)
            calculateCombinations(capacity + values[currentSolution.peekLast()], currentSolution.removeLast() + 1);
}

Answer 1

解决装箱问题的关键启发是始终首先包装最尴尬(最大)的元素。例如，如果您要包装一辆搬家卡车，您会先把钢琴放进去，然后再担心较小的东西。我们的想法是最大限度地提高您的灵活性。

另一种技术就是我所说的“包围”。假设您正在查找总和为 50 的两个数字，并且您有一个类似 { 2, 3, 9, 18, 24, 29, 37, 45 } 的列表。您不必检查每个组合，因为您不能有两个大于 25 或小于 25 的值。您只需检查列表每一侧的数字，即 45+2、45+3、45+9、STOP、下一个数字、37+2、37+3 等。这就是包围。通过创建一组规则并将平均值括起来，您只需检查可能组合的一小部分。

装箱是一个搜索问题，因为在很多情况下你无法枚举所有可能的组合。这就像国际象棋；你无法计算出每一种可能的走法，你只是想找到一个好的走法。