剪枝CSP-S

💡 核心思想

剪枝是在搜索过程中，通过某些条件判断提前排除不可能产生最优解的子树，从而减少搜索量。常见策略：可行性剪枝、最优性剪枝（上下界剪枝）、冗余剪枝。

🎯 直觉理解

想象你在找东西，从一楼找到三楼都没找到。剪枝就是："如果二楼没声音，三楼肯定没有，不用上去了"。但前提是你确定判断条件是对的——万一三楼很安静但东西就在那呢？

📝 算法流程

1. 可行性剪枝：当前状态已经不满足约束，直接回溯
2. 最优性剪枝：当前代价已经超过已知最优解，不用继续
3. 排序优化：按某种顺序搜索，更早找到优解
4. 记忆化：相同状态不重复搜索

$$\text{剪枝后的搜索量} \ll \text{朴素搜索量，但最坏情况不变}$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
// 剪枝示例：子集和问题
int n, target, a[25];
bool dfs(int i, int sum) {
    if (sum > target) return false;      // 可行性剪枝
    if (i == n) return sum == target;
    // 最优性剪枝：即使全选也不够
    if (sum + /* remaining sum */ 0 < target) return false;
    if (dfs(i+1, sum + a[i])) return true;  // 选
    if (dfs(i+1, sum)) return true;          // 不选
    return false;
}
int main() {
    cin >> n >> target;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a+n, greater<int>()); // 大的先试，更早触发剪枝
    cout << (dfs(0, 0) ? "Yes" : "No") << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目