深度优先搜索

深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法。

使用递归可以很好地实现深度优先搜索。

例题1

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

#include <cstdio>

const int maxn = 30;
int n, V, maxValue = 0;
int w[maxn], c[maxn];

//index为当前处理的物品编号
void dfs(int index, int sumW, int sumC) {
    if (index == n) {//已完成对n件物品的选择
        if (sumW <= V && sumC > maxValue) {
            maxValue = sumC;
        }
        return;
    }
    dfs(index + 1, sumW, sumC);//不选第index件物品
    dfs(index + 1, sumW + w[index], sumC + c[index]);//选第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;
}

剪枝后的代码：

#include <cstdio>

const int maxn = 30;
int n, V, maxValue = 0;
int w[maxn], c[maxn];

void dfs(int index, int sumW, int sumC) {
    if (index == n) {//已完成对n件物品的选择
        return;
    }
    dfs(index + 1, sumW, sumC);//不选第index件物品
    if (sumW + w[index] <= V) {
        if (sumC + c[index] > maxValue) {
            maxValue = sumC + c[index];
        }
        dfs(index + 1, sumW + w[index], sumC + c[index]);//选第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;
}

例题2

给定n个整数（可能有负数），从中选择k个数， 使得k个数之和恰好等于一个给定的整数x，如果有多种方案，选择平方和最大的一个。

#include <cstdio>
#include <vector>

using namespace std;

const int maxn = 30;
int n, k, x, maxSumSqu = -1;
int a[maxn];
vector<int> temp, res;

void dfs(int index, int nowK, int sum, int sumSqu) {
    if (nowK == k && sum == x) {
        if (sumSqu > maxSumSqu) {
            maxSumSqu = sumSqu;
            res = temp;
        }
        return;
    }
    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() {
    scanf("%d%d%d", &n, &k, &x);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    dfs(0, 0, 0, 0);
    for (int i = 0; i < res.size(); i++) {
        printf("%d ", res[i]);
    }
    return 0;
}

如果每一个数都可以选择多次，只需把选index号数分支改为以下即可。

  dfs(index, nowK + 1, sum + a[index], sumSqu + a[index] * a[index]);

1103 Integer Factorization