2

我完成了一项作业，其规格要求：

  • 递归解决方案
  • 容量 <= 100
  • 值.长度 <= 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);
}
4

1 回答 1

3

装箱问题的关键启发式方法是始终首先包装最笨拙（最大）的物品。例如，如果您要打包一辆移动的卡车，您首先将钢琴放入，然后再考虑较小的东西。这个想法是最大限度地提高您的灵活性。

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

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

于 2013-02-26T22:45:16.500 回答