一、DFS

（1）背包问题（每物一件）

// 背包问题剪枝深搜
#include <cstdio>
const int maxn = 30;
int n, V, maxValue = 0; //物品件数n，背包容量v，最大价值maxValue
int w[maxn], c[maxn];   // w[i]为每件物品的重量，c[i]为每件物品的价值
// DFS   index为当前处理的编号
// sumW和sumC分别为当前总重量和总价值
void DFS (int index, int sumW, int sumC)
{
    if(index == n){
        return;
    }
    DFS(index + 1, sumW, sumC);
    if(sumW + w[index] <= V)
    {
        if(sumC + c[index] >= maxValue)
        {
            maxValue = sumC + c[index];     // 更新最大价值maxValue
        }
        DFS(index + 1, sumW + w[index], sumC + c[index]);
    }
}
int main()
{
    scanf("%d%d",&n,&V);
    for(int i = 0; i < n; ++i)
    {
        scanf("%d",&w[i]);
    }
    for(int i = 0; i < n; ++i)
    {
        scanf("%d",&c[i]);
    }
    DFS(0,0,0);
    printf("%d\n",maxValue);
    return 0;
}
//
输入：
5 8
3 5 1 2 2
4 5 2 1 3
输出：
10

这个是剪枝版本的，当然也可以像N皇后问题的全排列问题一样，把所有物品走一遍之后再看是否更新，但是这就意味着每个节点都考虑一遍，复杂度O(2**n**)，上面代码用的深搜的剪枝算法。
当然目前的我建议用动态规划~~

（2）满足条件子序列问题

例如，从4个整数{2，3，3，4}中选择两个数，使它们的和为6，并输出平方和最大的方案，即{2，4}，和之前的背包问题相比，背包问题没有要求选择物品的总数量。但是这个问题要求只能选择2个数，因此形参需要noeK来记录当前已经选择的个数。定义如下：

void DFS (int index, int nowK, int sum, int sumSqu)

// P273 条件下的子序列问题
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 100;
// 从n个数中选k个数，使之和为x，最大平方和为maxSumSqu
int n, k, x, maxSumSqu = -1, A[maxn];
//temp存放临时方案，ans存放平方和最大的方案，不断更新
vector<int> temp, ans;
// 当前处理index号位的整数，当前已选整数个数为nowK
// 当前已选整数之和为sum，当前已选整数平方和为sumSqu
void DFS (int index, int nowK, int sum, int sumSqu)
{
    if(nowK == k && sum == x)
    {
        if(sumSqu > maxSumSqu)
        {
            maxSumSqu = sumSqu;
            ans = temp;
        }
        return;
    }
    // 已经处理完n个数，或者超过k个数，或者和超过x，返回
    if (index == n || nowK > k || sum > x){
        return;
    }
    // 选index号位
    temp.push_back(A[index]);
    DFS(index + 1, nowK + 1, sum + A[index], sumSqu + A[index] * A[index]);
    temp.pop_back();
    // 不选index号位
    DFS(index + 1, nowK, sum , sumSqu);
}
int main()
{
    // 从N个数中选k个数，使之和为x
    scanf("%d%d%d",&n,&k,&x);
    for(int i = 0; i < n; ++i)
    {
        scanf("%d",&A[i]);
    }
    DFS(0,0,0,0);
    printf("%d\n",maxSumSqu);
    return 0;
}
//
输入：
4 2 6
2 4 3 3
//输出：    
20

注意：不选index号位是下面的调用方式，必须index+1，想一下就懂，不+1就会死循环，出不去了，导致最后没有输出。

    // 不选index号位
    DFS(index + 1, nowK, sum, sumSqu);

修改题目：假设N个整数中的每一个都可以被选择多次，那么选择K个数，使得K个数之和恰好为X。
相比于刚才的问题，唯一的区别就是选择index号位后，不应直接进入index+1号位，而是继续index递归。即只需要把选index号位这条分支的代码改为：

DFS(index, nowK + 1, sum + A[index], sumSqu + A[index] * A[index]);

（3）排列组合问题（8-1-B）

题目描述

排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r < ＝ n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。
现要求你不用递归的方法输出所有组合。
例如n ＝ 5 ，r ＝ 3 ，所有组合为：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

输入

一行两个自然数n、r ( 1 < n < 21，1 < ＝ r < ＝ n )。

输出

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，所有的组合也按字典顺序。

题解：

注意有两个return；把index的return去掉就会死循环。

代码：

#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 100000;
//从m个数中选n个数
int m, n;
vector<int> P;
bool hashTable[maxn] = {false};
//研究index号位，已选个数为nowK
void generateP (int index, int nowK)
{
    if(nowK == n)
    {
        for(int i = 0; i < n; ++i){
            printf("%d ",P[i]);
        }
        printf("\n");
        return;
    }
    if(index==m+1)
        return;
    P.push_back(index);
    generateP(index + 1, nowK + 1);
    P.pop_back();
    generateP(index + 1, nowK);
}
int main()
{
    scanf("%d%d",&m, &n);
    generateP(1,0);
    return 0;
}