曾彪彪的个人博客 -- 回溯算法

# P1036 [NOIP 2002 普及组] 选数

## 题目描述

已知 $n$ 个整数 $x_1,x_2,\cdots,x_n$，以及 $1$ 个整数 $k$（$k<n$）。从 $n$ 个整数中任选 $k$ 个整数相加，可分别得到一系列的和。例如当 $n=4$，$k=3$，$4$ 个整数分别为 $3,7,12,19$ 时，可得全部的组合与它们的和为：

$3+7+12=22$

$3+7+19=29$

$7+12+19=38$

$3+12+19=34$

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：$3+7+19=29$。

## 输入格式

第一行两个空格隔开的整数 $n,k$（$1 \le n \le 20$，$k<n$）。

第二行 $n$ 个整数，分别为 $x_1,x_2,\cdots,x_n$（$1 \le x_i \le 5\times 10^6$）。

## 输出格式

输出一个整数，表示种类数。

## 输入输出样例 #1

### 输入 #1

```
4 3
3 7 12 19
```

### 输出 #1

```
1
```

## 说明/提示

**【题目来源】**

NOIP 2002 普及组第二题

这道题虽然也勉强做出来了，但是其实学会了很多知识。
本周虽然是在学习暴搜，但是更多的是在了解dfs，以及回溯。
回溯算法，在排列和组合中比较常见。
我们先来输出全排列，可以使用stl模板，代码如下：

```c++
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> nums;
    for (int i = 1; i <= n; i++)
    {
        nums.push_back(i);
    }
    do
    {
        for (auto e : nums)
        {
            cout << e;
        }
        cout << endl;
    } while (next_permutation(nums.begin(), nums.end()));

return 0;
}
```

每次调用next_permutation方法，改方法会根据全排列规则，修改nums中的元素，我们只需输出即可。

如果手动实现，则使用dfs进行回溯，代码如下：
```c++
#include <bits/stdc++.h>
using namespace std;

vector<bool> used(100); //标记当前数字是否被使用过，用于剪枝
vector<int> path; //存储已经使用过的数字

int n;

void dfs(int step)
{
    if (step == n)
    {
        for (auto e : path)
        {
            cout << e;
        }
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!used[i])
        {
            used[i] = true;
            path.push_back(i);
            dfs(step + 1);
            used[i] = false;
            path.pop_back();
        }
    }
}

int main()
{
    cin >> n;

dfs(0);

return 0;
}
```
这段代码其实不好理解，我们假设用户输入了3，来推演一下。

dfs(0): path=[], used=[F,F,F]
|
+-- i=0 (选1) → dfs(1): path=[1], used=[T,F,F]
|    |
|    +-- i=1 (选2) → dfs(2): path=[1,2], used=[T,T,F]
|    |    |
|    |    +-- i=2 (选3) → dfs(3): path=[1,2,3], used=[T,T,T] → 输出 [1,2,3]
|    |    回溯 → path=[1,2], used=[T,T,F]
|    |
|    +-- i=2 (选3) → dfs(2): path=[1,3], used=[T,F,T]
|         |
|         +-- i=1 (选2) → dfs(3): path=[1,3,2], used=[T,T,T] → 输出 [1,3,2]
|         回溯 → path=[1,3], used=[T,F,T]
|    回溯 → path=[1], used=[T,F,F]
回溯 → path=[], used=[F,F,F]
|
+-- i=1 (选2) → dfs(1): path=[2], used=[F,T,F]
|    |
|    +-- i=0 (选1) → dfs(2): path=[2,1], used=[T,T,F]
|    |    +-- i=2 (选3) → dfs(3): path=[2,1,3], used=[T,T,T] → 输出 [2,1,3]
|    |    回溯 → path=[2,1], used=[T,T,F]
|    |
|    +-- i=2 (选3) → dfs(2): path=[2,3], used=[F,T,T]
|         +-- i=0 (选1) → dfs(3): path=[2,3,1], used=[T,T,T] → 输出 [2,3,1]
|         回溯 → path=[2,3], used=[F,T,T]
|    回溯 → path=[2], used=[F,T,F]
回溯 → path=[], used=[F,F,F]
|
+-- i=2 (选3) → dfs(1): path=[3], used=[F,F,T]
     |
     +-- i=0 (选1) → dfs(2): path=[3,1], used=[T,F,T]
     |    +-- i=1 (选2) → dfs(3): path=[3,1,2], used=[T,T,T] → 输出 [3,1,2]
     |    回溯 → path=[3,1], used=[T,F,T]
     |
     +-- i=1 (选2) → dfs(2): path=[3,2], used=[F,T,T]
          +-- i=0 (选1) → dfs(3): path=[3,2,1], used=[T,T,T] → 输出 [3,2,1]
          回溯 → path=[3,2], used=[F,T,T]
     回溯 → path=[3], used=[F,F,T]
回溯 → path=[], used=[F,F,F]

为什么使用dfs进行回溯，是因为可以把全排列看作是对一颗n叉树进行遍历。

有了全排列，再来看组合，组合是与顺序无关的子集合。将上面回溯算法做些变化，就可以得到组合算法。代码如下：

```c++
#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> path;

void dfs(int step, int from)
{
    if (step == k)
    {
        for (auto e : path)
        {
            cout << e;
        }
        cout << endl;
        return;
    }
    for (int i = from; i <= n; i++)
    {
        path.push_back(i);
        dfs(step + 1, i + 1);
        path.pop_back();
    }
}

int main()
{
    cin >> n >> k;

dfs(0, 1);

return 0;
}
```

排列是无须的，我们在输出组合数字时，按照数字升序排列即可。

有了上面的基础，做这道题就有思路了。先求出c(n,k)的组合，然后根据这个数字下标进行求和，最后判断是否为素数。直接上代码：
```c++
#include <bits/stdc++.h>
using namespace std;

int n, k, ans = 0;
vector<int> nums = {0};

bool isPrime(long num)
{
    if (num < 2)
    {
        return false;
    }
    if (num <= 3)
    {
        return true;
    }
    if (num % 2 == 0 | num % 3 == 0)
    {
        return false;
    }
    for (int i = 5; i * i <= num; i++)
    {
        if (num % i == 0 || num % i + 2 == 0)
        {
            return false;
        }
    }
    return true;
}

void dfs(int step, int from, long sum)
{
    if (step == k)
    {
        if (isPrime(sum))
        {
            ans++;
        }
        return;
    }
    for (int i = from; i <= n; i++)
    {
        dfs(step + 1, i + 1, sum + nums[i]);
    }
}

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        int v;
        cin >> v;
        nums.push_back(v);
    }

dfs(0, 1, 0);
    cout << ans << endl;

return 0;
}
```

回溯算法

评论(0)