基于动态规划的0/1背包问题代码遇无限循环及性能问题求助

问题描述 #

我尝试实现一个背包问题的动态规划解法，当输入egg_weights = (1,5,10,25)和n = 99时，程序陷入无限循环；较小的n值下代码能给出正确结果，但运行速度极慢。请问代码存在什么问题？

原实现代码 #

def dp_make_weight(egg_weights, target_weight, memo = {}):
    if target_weight < 0:
        return float('inf')
    elif target_weight == 0:
        return 0
    elif target_weight > 0:
        try:
            return memo[target_weight]
        except:
            memo[target_weight] = float('inf')
            for weight in egg_weights:
                result = dp_make_weight(egg_weights, target_weight - weight, memo = {})
                if result < memo[target_weight]:
                    memo[target_weight] = result + 1
        return result + 1

测试代码 #

if __name__ == '__main__':
    egg_weights = (1, 5, 10, 25)
    n = 99
    print("Egg weights = (1, 5, 10, 25)")
    print("n = 99")
    print("Expected output: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)")
    print("Actual output:", dp_make_weight(egg_weights, n))
    print()

问题分析 #

• 记忆化完全失效：递归调用时每次都传入memo = {}，相当于每个子问题都用全新的空字典，完全没用到缓存。本来记忆化是为了避免重复计算已经求过解的target_weight，现在反而变成每个子问题都要从头算一遍，计算量呈指数级增长，小n还能扛，n=99时直接陷入近乎无限的循环。
• 返回值逻辑错误：函数最后返回的result + 1是循环最后一次迭代的结果加1，不是我们计算出的最小鸡蛋数。比如循环到最后一个weight时的结果，不一定是所有子问题中的最优解，这会导致最终结果错误。
• 默认参数陷阱：Python里memo = {}这种默认参数只会在函数定义时初始化一次，后续调用如果不传memo会复用同一个字典，多次调用函数时会污染缓存，但这次的核心问题还是递归时传空字典。

修复后的代码 #

def dp_make_weight(egg_weights, target_weight, memo=None):
    # 每次调用初始化memo，避开默认参数陷阱
    if memo is None:
        memo = {}
    if target_weight < 0:
        return float('inf')
    elif target_weight == 0:
        return 0
    # 先查缓存，有结果直接返回
    if target_weight in memo:
        return memo[target_weight]
    
    min_eggs = float('inf')
    for weight in egg_weights:
        sub_result = dp_make_weight(egg_weights, target_weight - weight, memo)
        # 子问题有解的话，更新最小鸡蛋数
        if sub_result + 1 < min_eggs:
            min_eggs = sub_result + 1
    
    # 把当前结果存入缓存
    memo[target_weight] = min_eggs
    return min_eggs

运行修复后的测试代码，会输出正确的结果9，而且n=99时能快速计算完成。

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