登录以参加训练计划

课件

剪枝技巧概述

剪枝是在搜索过程中提前终止不可能产生解的分支，减少计算量，提高搜索效率。

常见剪枝方法

剪枝方法	说明	示例
可行性剪枝	当前分支不可能产生解	sum > r 时停止
最优性剪枝	当前分支不可能优于已知最优解	cost >= ans 时停止
顺序剪枝	通过搜索顺序避免重复	从小到大枚举，保证不下降
记忆化搜索	记录已计算的状态，避免重复	用数组记录状态结果

可行性剪枝

void dfs(int x, int s) {
    if (s > r) return;          // 可行性剪枝：超出上限
    if (x > n) {
        if (s >= l) ans++;
        return;
    }
    dfs(x + 1, s);              // 不选
    dfs(x + 1, s + w[x]);       // 选
}

最优性剪枝

int ans = 2e9;

void dfs(int x, int cost) {
    if (cost >= ans) return;    // 最优性剪枝
    if (x > n) {
        ans = min(ans, cost);
        return;
    }
    // 递归尝试
}

数的划分（顺序剪枝）

将n分成k个正整数的和，保证划分时每份不小于前一份：

void dfs(int x, int last, int sum) {
    if (x == k) { ans++; return; }
    for (int i = last; i <= sum / 2; i++) {
        dfs(x + 1, i, sum - i);
    }
}

自然数拆分

void dfs(int p, int sum) {
    if (sum == 0) { /* 输出 ans[1..p-1] */ return; }
    for (int i = ans[p-1]; i <= sum; i++) {
        ans[p] = i;
        dfs(p + 1, sum - i);
    }
}

木棒拼正方形（综合剪枝）

sort(a + 1, a + n + 1, greater<int>());  // 从大到小排序
if (sum % 4 != 0) { /* 不可行 */ }
if (a1 + a[p] <= sum / 4) dfs(p + 1, a1 + a[p], a2, a3, a4);

注意事项

1. 剪枝条件要尽量紧，但不能剪掉正确答案
2. 合理的排序顺序能大幅提高剪枝效率
3. 剪枝和回溯是配合使用的关系