搜索——深度优先搜索（DFS）

设想我们现在身处一个巨大的迷宫中，我们只能自己想办法走出去，下面是一种看上去很盲目但实际上会很有效的方法。

以当前所在位置为起点，沿着一条路向前走，当碰到岔道口时，选择其中一个岔路前进。如果选择的这个岔路前方是一条死路，就退回到这个岔道口，选择另一个岔路前进。如果岔路口存在新的岔道口，那么仍然按上面的方法枚举新岔道口的每一条岔道。这样，只要迷宫存在出口，那么这个方法一定能够找到它。

也就是说，当碰到岔道口时，总是以“深度”作为前进的关键词，不碰到死胡同就不回头，因此这种搜索的方式称为深度优先搜索（DFS）。

接下来讲解一个例子。

有 n件物品，每件物品的重量为 w[i]，价值为 c[i]。现在需要选出若干件物品放入一个容量为 V的背包中，使得在选入背包的物品重量和不超过容量 V的前提下，让背包中物品的价值之和最大，求最大价值。(1≤n≤20)

在这个问题中，对每件物品都有选或者不选两种选择，而这就是所谓的“岔道口”。那么什么是“死胡同”呢？题目要求选择的物品重量总和不能超过 V，因此一旦选择的物品重量总和超过 V，就会到达“死胡同”，需要返回最近的“岔道口”。

DFS函数的参数中必须记录当前处理的物品编号 index，和在处理当前物品之前，已选物品的总重量 sumW与总价值sumC。于是 DFS函数如下：

void DFS(int index, int sumW, int sumC) {...}

思路：

• 如果选择不放入 index号物品，那么 sumW与 sumC就将不变，接下来处理 index+1号物品，即前往 DFS(index+1, sumW, sumC) 这条分支；
• 如果选择放入 index号物品，那么 sumW=sumW+w[index], sumC=sumC+c[index]，接着处理index+1号物品，即前往 DFS(index+1, sumW+w[index], sumC+c[index]) 这条分支；
• 一旦 index增长到了 n，则说明已经把 n件物品处理完毕。此时记录的 sumW和 sumC就是所选物品的总重量和总价值。如果 sumW不超过V且 sumC大于记录的最大总价值 maxValue，就说明当前的这种选择方案可以得到更大的价值，于是用 sumC更新 maxValue。

代码如下：

1 /*
 2     搜索_DFS 
 3     有 n 件物品，每件物品的重量为 w[i]，价值为 c[i]。现在需要选出若干件物品
 4         放入一个容量为 V 的背包中，使得在选入背包的物品重量和不超过容量 V 的前提下，
 5         让背包中物品的价值之和最大，求最大价值。(1≤n≤20)
 6 */
 7 
 8 #include <stdio.h>
 9 #include <string.h>
10 #include <math.h>
11 #include <stdlib.h>
12 #include <time.h>
13 #include <stdbool.h>
14 
15 #define maxn 30
16 int n, V, maxValue;    // 物品减数，背包容量，最大价值
17 int w[maxn], c[maxn];    // 每件物品的重量，价值 
18 
19 // index 当前处理的物品编号，sumW 和 sumC 为当前总重量和总价值 
20 void DFS(int index, int sumW, int sumC) {
21     if(index == n) {    // 已经把 n 件物品处理完毕(死胡同） 
22         if(sumW <= V && sumC > maxValue) {
23             maxValue = sumC;    // 有更好的选择 
24         }
25         return; 
26     }
27     // 岔道口
28     DFS(index+1, sumW, sumC);    // 不选 Index 号物品
29     DFS(index+1, sumW+w[index], sumC+c[index]);    // 选 index 号物品 
30 }
31 
32 int main() {
33     scanf("%d %d", &n, &V);
34     int i;
35     for(i=0; i<n; ++i) {
36         scanf("%d", &w[i]);        // 每件物品的重量 
37     } 
38     for(i=0; i<n; ++i) {
39         scanf("%d", &c[i]);        // 每件物品的价值 
40     }
41     DFS(0, 0, 0);
42     printf("%d\n", maxValue); 
43 
44     return 0;
45 }

在上述代码中，总是把 n件物品的选择全部确定之后才去更新最大价值，但是事实上忽视了背包容量不超过 V这个特点。也就是说，完全可以把对 sumW的判断加入“岔道口”中，只有当 sumW≤ V时才进入岔道，这样效率会高很多。代码如下：

1 // index 当前处理的物品编号，sumW 和 sumC 为当前总重量和总价值 
 2 void DFS1(int index, int sumW, int sumC) {
 3     if(index == n) {    // 已经把 n 件物品处理完毕(死胡同） 
 4         return; 
 5     }
 6     // 岔道口
 7     DFS(index+1, sumW, sumC);    // 不选 Index 号物品
 8     // 只有加入 index 物品后总重量小于 V 才可以继续 
 9     if(sumW + w[index] <= V) {
10         if(sumC + c[index] > maxValue) {
11             maxValue = sumC + c[index];
12         }
13         DFS(index+1, sumW+w[index], sumC+c[index]);    // 选 Index 号物品
14     }
15 }

再来看另外一个问题。

给定 N个整数（可能有负数），从中选择K个数，使得这 K个数之和恰好等于一个给定的整数 X；如果有多种方案，选择它们中元素平方和最大的一个。

与之前的问题类似，此处仍然需要记录当前处理的整数编号 index；由于要求恰好选择 K个数，因此需要一个参数 nowK来记录当前已经选择的数的个数；另外，还需要参数 sum和 sumSqu分别记录当前已选整数之和与平方和。于是 DFS函数如下：

void DFS(int index, int nowK, int sum, int sumSqu) {...}

思路：

• 需要一个数组 temp，用以存放当前选择的整数。
• 当试图进入“选 index号数”这条分支时，就把 A[index]加入 temp中；
• 当这条分支结束时，就还原 temp数组，使他不影响“不选 index号数”这条分支。
• 如果当前已选择了 K个数，且这 K个数之和恰为 x时，就将平方和与已有的最大平方和 maxValue作比较，如果更大，更新 maxValue和数组 ans。

代码如下：

1 /*
 2     DFS_N个整数选K个 
 3     给定 N 个整数（可能有负数），从中选择 K 个数，使得这 K 个数之和
 4     恰好等于一个给定的整数 X；如果有多种方案，选择它们中元素平方和最大的一个。
 5 */
 6 
 7 #include <stdio.h>
 8 #include <string.h>
 9 #include <math.h>
10 #include <stdlib.h>
11 #include <time.h>
12 #include <stdbool.h>
13 
14 #define maxn 30
15 // 序列A中n个数选k个数使得和为x，最大平方和为maxSumSqu 
16 int n, k, x, maxSumSqu=-1, A[maxn]; 
17 int temp[maxn]={0}, ans[maxn]={0};    // 临时方案，平方和最大的方案
18 
19 void DFS(int index, int nowK, int sum, int sumSqu) {
20     if(nowK == k && sum == x) {        // 找到K个数和为x 
21         if(sumSqu > maxSumSqu) {    // 更优方案 
22             maxSumSqu = sumSqu;        // 更新 maxValue 和数组 ans
23             int i;
24             for(i=0; i<k; ++i) {
25                 ans[i] = temp[i];
26             }
27         }
28     }
29     // 已经处理完n个数，选择超过k个数，和大于x 
30     if(index==n || nowK>k || sum>x)    return; 
31     // 选 index 号数
32     temp[nowK] = A[index]; 
33     DFS(index+1, nowK+1, sum+A[index], sumSqu+A[index]*A[index]);
34     temp[nowK] = 0; 
35     // 不选 index 号数
36     DFS(index+1, nowK, sum, sumSqu); 
37 } 
38 
39 int main() {
40     scanf("%d %d %d", &n, &k, &x);
41     int i;
42     for(i=0; i<n; ++i) {
43         scanf("%d", &A[i]);    // n个数 
44     }
45     DFS(0, 0, 0, 0);
46     for(i=0; i<k; ++i) {    // 最优方案 
47         printf("%d ", ans[i]);
48     }
49     printf("%d\n", maxSumSqu);    // 最优方案的平方和 
50 
51     return 0;
52 }