回溯法解组合优化问题：0-1背包与n后问题

"搜索子树-算法中的回溯法" 回溯法是一种在搜索解空间树时用于求解问题的算法，它通过尝试逐步构造可能的解决方案，并在遇到不符合条件的情况时撤销最近的选择，继续探索其他分支，直到找到可行解或证明所有分支都无法满足条件为止。这种算法尤其适用于解决那些具有大量可能解的组合优化问题。 在给定的代码中，我们可以看到一个典型的回溯法框架。这个框架是针对一个特定的问题，可能是0-1背包问题或者类似的装载问题。代码中使用了一个循环结构来表示回溯的过程： 1. 主循环 (`while( true )`) 代表了整个回溯过程，直到找到最佳解或者搜索完所有可能的分支。 2. 第一个内部循环 (`while( i <= n && cw + w[i] <= c)`) 表示进入左子树，即当前选择的物品不会超出背包容量。在这里，`cw` 是当前背包的总重量，`w[i]` 是第 `i` 个物品的重量，`c` 是背包的最大容量，`x[i]` 是物品是否被选中的标记（1代表选中，0代表未选中），`r` 是剩余的容量。 3. 当 `i > n` 时，意味着到达了叶节点，即所有可能的物品都已考虑过，此时会将当前解 `x[]` 复制到 `bestx[]`，并更新最优解的总价值 `bestw`。 4. 另一个内部循环 (`while( cw + r <= bestw)`) 表示剪枝回溯，如果当前分支无法得到比已知最优解更好的结果，就回溯到上一层，即取消前一个物品的选择。 5. 在剪枝回溯过程中，`i--` 用来退回上一个物品，然后检查右子树，即不选择当前物品的情况。 6. 如果所有可能的分支都已尝试，通过 `delete [] x` 清理内存，并返回最佳解的总价值 `bestw`。 回溯法的优势在于它可以有效地避免无效的搜索，通过剪枝技术减少计算量。在这个问题中，当发现当前分支无法达到最优解时，算法会立即回溯到上一状态，尝试其他分支，而不是继续沿着错误的路径深入。 此外，回溯法可以应用在很多领域，如n后问题、0-1背包问题、图的着色问题、旅行售货员问题等。这些问题通常都有一个共同特点，即存在大量的潜在解，并且可以通过检查局部条件来排除一些不可能的解。通过深度优先搜索的方式，回溯法能够以有限的计算资源找到问题的解或最优解。