背包问题BFS与DFS算法：时间空间性能对比及内存测量问询

我是Python新手，目前需要完成背包问题中BFS和DFS算法的时间消耗及内存占用对比任务。已实现两种算法，通过start_time = time.time()和end = time.time()测出时间数据：

BFS algorithm
0.0060007572174072266s
DFS algorithm
0.005002260208129883s

但不知道如何基于自己的代码测量内存占用，同时不确定任务要求是对比通用BFS/DFS思想还是我自己实现的代码。附上算法代码及后续测试结果，求解答如何基于代码计算内存占用。

算法代码 #

BFS 实现 #

def knapsack_bfs(items, max_weight):
    queue = deque()
    root = Node(-1, 0, 0, [])
    queue.append(root)

    max_benefit = 0
    best_combination = []

    while queue:
        current = queue.popleft()

        if current.level == len(items) - 1:
            if current.benefit > max_benefit:
                max_benefit = current.benefit
                best_combination = current.items
        else:
            next_level = current.level + 1
            next_item = items[next_level]

            include_benefit = current.benefit + next_item.benefit
            include_weight = current.weight + next_item.weight

            if include_weight <= max_weight:
                include_node = Node(next_level, include_benefit,
                                    include_weight, current.items + [next_item.id])
                if include_benefit > max_benefit:
                    max_benefit = include_benefit
                    best_combination = include_node.items
                queue.append(include_node)

            exclude_node = Node(next_level, current.benefit,
                                current.weight, current.items)
            queue.append(exclude_node)

    return max_benefit, best_combination

DFS 实现 #

def knapsack_dfs(items, max_weight):
    queue = []
    root = Node(-1, 0, 0, [])
    queue.append(root)

    max_benefit = 0
    best_combination = []

    while queue:
        current = queue.pop()

        if current.level == len(items) - 1:
            if current.benefit > max_benefit:
                max_benefit = current.benefit
                best_combination = current.items
        else:
            next_level = current.level + 1
            next_item = items[next_level]

            include_benefit = current.benefit + next_item.benefit
            include_weight = current.weight + next_item.weight

            if include_weight <= max_weight:
                include_node = Node(next_level, include_benefit,
                                    include_weight, current.items + [next_item.id])
                if include_benefit > max_benefit:
                    max_benefit = include_benefit
                    best_combination = include_node.items
                queue.append(include_node)

            exclude_node = Node(next_level, current.benefit,
                                current.weight, current.items)
            
            queue.append(exclude_node)

    return max_benefit, best_combination

后续测试结果 #

根据下方解答得到的测试结果：

program.py:42: size=4432 B (+840 B), count=79 (+15), average=56 B
program.py:116: size=0 B (-768 B), count=0 (-1)
program.py:79: size=0 B (-744 B), count=0 (-13)
program.py.py:85: size=0 B (-72 B), count=0 (-1)
program.py:57: size=0 B (-56 B), count=0 (-1)
program.py:56: size=0 B (-56 B), count=0 (-1)
program.py:74: size=0 B (-32 B), count=0 (-1)
program.py:37: size=32 B (+0 B), count=1 (+0), average=32 B

解答 #

1. 任务范围说明 #

任务要求的对比对象是你自己实现的BFS和DFS代码。通用BFS/DFS只是算法思想，不同实现的性能差异极大，只有基于你编写的代码做对比，结果才符合任务要求。

2. 内存占用测量方法 #

Python标准库中的tracemalloc模块可以精准追踪代码运行时的内存分配，是测量内存占用的首选工具，具体用法如下：

方法一：统计内存分配明细

可以追踪代码中每行的内存分配情况，步骤如下：

import tracemalloc

# 初始化内存追踪
tracemalloc.start()

# 运行BFS算法
knapsack_bfs(your_items_list, your_max_weight)
# 获取内存快照并按代码行统计
bfs_snapshot = tracemalloc.take_snapshot()
bfs_stats = bfs_snapshot.statistics('lineno')

print("=== BFS 内存分配统计 ===")
# 打印前5条最占内存的记录
for stat in bfs_stats[:5]:
    print(stat)

# 清除之前的追踪数据，准备测试DFS
tracemalloc.clear_traces()

# 运行DFS算法
knapsack_dfs(your_items_list, your_max_weight)
dfs_snapshot = tracemalloc.take_snapshot()
dfs_stats = dfs_snapshot.statistics('lineno')

print("\n=== DFS 内存分配统计 ===")
for stat in dfs_stats[:5]:
    print(stat)

# 停止追踪
tracemalloc.stop()

方法二：测量峰值内存

如果需要对比两种算法运行过程中的最大内存占用，用get_traced_memory()方法更直接：

import tracemalloc

# 测试BFS峰值内存
tracemalloc.start()
knapsack_bfs(your_items_list, your_max_weight)
current_mem, peak_mem = tracemalloc.get_traced_memory()
print(f"BFS 当前内存: {current_mem/1024:.2f} KB，峰值内存: {peak_mem/1024:.2f} KB")
tracemalloc.stop()

# 测试DFS峰值内存
tracemalloc.start()
knapsack_dfs(your_items_list, your_max_weight)
current_mem, peak_mem = tracemalloc.get_traced_memory()
print(f"DFS 当前内存: {current_mem/1024:.2f} KB，峰值内存: {peak_mem/1024:.2f} KB")
tracemalloc.stop()

结果解读

• size：对应代码行分配的内存总大小（单位字节）
• count：对应代码行分配的内存块数量
• peak_mem：算法运行过程中达到的最大内存占用（转换为KB后更易读）

你贴出的测试结果正是tracemalloc生成的行统计数据，对比BFS和DFS的总内存分配量或峰值内存，就能明确哪种算法的内存开销更高。

内容的提问来源于stack exchange，提问作者zellez11