0-1 背包问题深度优先搜索算法详解

本篇文章将详细解释以下代码，该代码使用深度优先搜索 (DFS) 算法解决经典的 0-1 背包问题。

void dfs(int i, int cw, int cv) {
    if (i == n) {
        if (cv > maxV) {
            maxV = cv;
        }
        return;
    }
    dfs(i + 1, cw, cv); // 不选择第 i 个物品
    if (cw + w[i] <= W) {
        dfs(i + 1, cw + w[i], cv + v[i]); // 选择第 i 个物品
    }
}

代码解析

函数参数:

i: 当前考虑到的物品编号
cw: 当前背包中物品的总重量
cv: 当前背包中物品的总价值

代码逻辑:

判断是否已经考虑完了所有的物品:
- if (i == n) 判断是否已经遍历完所有物品 (n 为物品总数)。
- 如果 i 等于 n，说明已经遍历完所有物品，此时判断当前的总价值 cv 是否大于之前的最大价值 maxV，如果大于则更新 maxV，然后返回。
尝试不选择当前物品:
- dfs(i + 1, cw, cv) 递归调用自身，考虑下一个物品，不选择当前物品，因此 cw 和 cv 不变。
尝试选择当前物品:
- if (cw + w[i] <= W) 判断当前物品的重量 w[i] 加上当前背包中物品的总重量 cw 是否小于等于背包容量 W。
- 如果满足条件，说明当前物品可以放入背包，递归调用自身，考虑下一个物品，将当前物品的重量 w[i] 加到 cw 中，将当前物品的价值 v[i] 加到 cv 中。

总结:

通过递归遍历所有可能的方案，分别尝试选择和不选择每个物品，最终找到总价值最大的方案，并存储在 maxV 中。DFS 算法通过逐层深入地探索所有可能的组合，最终找到最优解。