TB椰程 TypeBuddy 打字搭子

搜索剪枝

CSP-J · 编程模板 · 片段 · cpp · 难度 3/5 · 共 510 字

用可行性/最优性提前终止无效分支

  • 搜索
  • 搜索剪枝

前置内容

正文

// 搜索剪枝：提前终止无效分支
// 用可行性 / 最优性剪枝
// 大幅减少搜索空间
// 例：部分和，超过上限即停
#include <cstdio>
int n, m, a[25], ans = 0;
// 当前选到第 i 个，已累加 s
void dfs(int i, int s) {
    // 超过目标 m 不再递归
    if (s > m) return;
    // 全选完且恰好等于 m
    if (i > n) {
        if (s == m) ans++;
        return;
    }
    // 分支一：选当前数
    dfs(i + 1, s + a[i]);
    // 分支二：不选当前数
    dfs(i + 1, s);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    dfs(1, 0);
    printf("%d", ans);
    return 0;
}

CSP-J · 编程模板的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK