与BFS不同,DFS(广度优先搜索)是一条路走到黑,撞了南墙再回头换条路继续撞南墙,BFS适合寻找最短路径

深度优先搜索（DFS）通常用于解决具有单一方案的谜题、检测图中的周期以及查找连通图组件。
再次附上freeCodeCamp链接,这的确是一个伟大的项目:

https://www.freecodecamp.org/chinese/learn/python-v9/lecture-understanding-graphs-and-trees/how-do-depth-first-and-breadth-first-search-work

DFS的基本流程是:

  • 确定起点,标记为已访问
  • 起点出栈接受”特定处理”,所有未访问相邻节点入栈
  • 最晚入栈的节点出栈,循环往复
  • 达成特定条件/所有节点已访问,DFS结束

理论多说无益,直接上实战

原题复现

难度:普及-
https://www.luogu.com.cn/problem/P1049

题目描述

有一个箱子容量为 VV，同时有 nn 个物品，每个物品有一个体积。

现在从 nn 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

输入格式

第一行共一个整数 VV，表示箱子容量。

第二行共一个整数 nn，表示物品总数。

接下来 nn 行，每行有一个正整数，表示第 ii 个物品的体积。

输出格式

  • 共一行一个整数，表示箱子最小剩余空间。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
24
6
8
3
12
7
9
7

输出 #1

1
2
0

说明/提示

对于 100%100\% 数据，满足 0<n≤300<n \le 30，1≤V≤200001 \le V \le 20000。

解题思路

dfs(当前节点,当前体积):

  • 选择下一个节点:
    • dfs(下一个节点,更新当前体积)
  • 不选下一个节点:
    • dfs(下一个节点,当前体积)

完整代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import sys

v = int(sys.stdin.readline())
n = int(sys.stdin.readline())
items = [int(sys.stdin.readline()) for _ in range(n)]

max_v = 0

def dfs(idx, cur_v):
    global max_v
    if cur_v > max_v:
        max_v = cur_v
    if idx == n or max_v == v:
        return
    if cur_v + items[idx] <= v:
        dfs(idx + 1, cur_v + items[idx])
    dfs(idx + 1, cur_v)

dfs(0, 0)
print(v - max_v)

这道题其实还有很多优化空间,但这里只介绍简单暴力DFS解法