减小访问状态空间 – 如何更优化搜索

DFS剪枝

PAT-A1103 枚举指数型加数

对状态空间的搜索即采用DFS枚举所有情况
因可包含相同状态，因此 DFS走两个分支：下个相同状态、不同状态

题目条件：
①非增序列且字典序最大：决定了枚举顺序递减顺序
②和最小序列：搜索至解时进行比较

递归边界和剪枝：
①rest < 0 对应枚举数和超过已知和
②restN < 0 对应枚举数字数量超过要求数量还未找到解
③rest == 0 && restN == 0 对应找到正确解，rest == 0 && restN > 0 不满足数量，将被下轮rest < 0剪枝
④id > 0 对应递归边界，最小数只能取1

优化：
①打表
②存储和

---

Q：进入DFS前怎么没用for

Q：为什么没有用pow？

A：①pow会向上转型为double降低速度②double转int取决于编译器版本，可能会产生精度问题，如(int)100.0=99，使100=100^1这样的样例出错

Q：怎么记录解结果？

A：仅有进入选该数的分支才入栈，不选的分支不包括该数

Q：如何判断有解？

A：直观的想法是在递归有解处设定特殊返回值。更好的办法是设定并检验指标，在探索完毕后判断最大和>0或者解向量长度>0

---

#include <iostream>
#include <vector>
using namespace std;

vector<int> fac, num, tmp;
int maxSum = 0;

void DFS(int rest, int restN, int id, int sum) {
    if (rest < 0 || restN < 0)
        return;
    if (rest == 0 && restN == 0) {
        if (maxSum < sum) {
            tmp = num;
            maxSum = sum;
        }
        return;
    }
    if (id > 0) {
        num.push_back(id);
        DFS(rest - fac[id], restN - 1, id, sum + id);
        num.pop_back();
        DFS(rest, restN, id - 1, sum);
    }
}

int main() {
    int N, K, P;
    scanf("%d %d %d", &N, &K, &P);
    fac.push_back(0);

    int p, f = 1, i = 2;
    for(; f <= N; i++) {
        fac.push_back(f);
        f = 1; p = P;
        while (p--) f *= i;
    }

    DFS(N, K, fac.size() - 1, 0);

    if (tmp.size()) {
        printf("%d = ", N);
        for (int i = 0; i < tmp.size() - 1; i++)
            printf("%d^%d + ", tmp[i], P);
        printf("%d^%d", tmp[tmp.size() - 1], P);
    }
    else printf("Impossible\n");

    return 0;
}