You need to enable JavaScript to run this app. Python中如何将迭代版简化背包求解函数转递归实现及代码纠错
优惠活动
大模型
产品
解决方案
定价
更多

Python中如何将迭代版简化背包求解函数转递归实现及代码纠错

简化背包问题的等价递归实现修正

原迭代实现核心逻辑

该迭代函数的计算流程为:

  • 初始状态:未处理任何商品时,仅存在持有初始金额money这一种可能,对应剩余金额集合为{money}
  • 逐件遍历仓库内的商品,对集合中每一个可能的剩余金额,计算购买当前商品0件、1件……直到达到最大可买数量(可买数量受持有金额、限量商品的库存上限约束)后对应的新剩余金额
  • 合并所有生成的新剩余金额形成新的集合,在所有商品处理完毕后,返回集合中的最小值
def so_rich(self, money):
        """ Find the minimum amount left from the given 'money' after buying s series of products """

        # suppose you haven't seen any product yet
        # the only possible amount of money left is "money"
        # this is a set to record the possible money left
        left = set([money])
        # get products
        lst = list(self.warehouse.inventory.values())
        for product in lst:
            
            # a temporary set to save the updates of "left"
            # you don't want to modify the set you're iterating through
            tmp_left = set()
            # update tmp_left
            for m in left:
                
                if type(product) != Limited_Product:
                    new_left = m
                    while new_left >= product.price:
                        new_left = new_left - product.price
                        tmp_left.add(new_left)
                else:
                    # handle limited product
                    new_left = m
                    product_count = product.amount
                    while new_left >= product.price and product_count > 0:
                        new_left = new_left - product.price
                        tmp_left.add(new_left)
                        product_count -= 1
                        
            left.update(tmp_left)
        return min(left)

现有递归代码的问题定位

  • 原迭代的核心是维护全量的可能剩余金额集合,但现有递归代码仅追踪单一的剩余金额值,相当于每次强制将当前商品的最大可买数量全部买完,丢失了“不买、买部分数量”的其他购买分支,和原迭代的集合遍历逻辑完全不匹配
  • 递归传递的参数仅为单一的最小值,没有保留不同购买选择下的多分支状态,无法覆盖所有可能的剩余金额场景
  • 递归过程中直接对传入的商品列表执行pop(0)原地修改,容易产生副作用,和原迭代无状态的逐商品处理逻辑不匹配

修正后的等价递归实现

以下实现完全对齐原迭代的计算逻辑,不存在功能差异:

def so_rich_recursive(self, money):
        """ recursively find the minimum amount left from the given 'money' after buying s series of products """
        product_list = list(self.warehouse.inventory.values())
        
        def helper(unprocessed_products, possible_left_set):
            # 递归终止:所有商品处理完成,返回所有可能剩余值的最小值
            if not unprocessed_products:
                return min(possible_left_set)

            current_product = unprocessed_products[0]
            tmp_left = set()

            # 基于当前所有可能的剩余金额,计算购买当前商品后的新剩余集合
            for current_m in possible_left_set:
                if type(current_product) != Limited_Product:
                    new_left = current_m
                    while new_left >= current_product.price:
                        new_left -= current_product.price
                        tmp_left.add(new_left)
                else:
                    new_left = current_m
                    remain_count = current_product.amount
                    while new_left >= current_product.price and remain_count > 0:
                        new_left -= current_product.price
                        tmp_left.add(new_left)
                        remain_count -= 1
            
            # 递归处理剩余商品,传入生成的新剩余金额集合
            return helper(unprocessed_products[1:], tmp_left)

        # 初始状态:未处理任何商品时,仅存在持有初始金额的可能
        return helper(product_list, set([money]))

实现对齐说明:

  • 递归的遍历顺序、每个商品的可买数量约束、集合合并逻辑与原迭代完全一致
  • 没有对传入的商品列表做原地修改,全程保留所有可能的购买分支
  • 终止条件匹配原循环结束后的最小值计算逻辑

内容的提问来源于stack exchange,提问作者Isuru Madhushanka Samaranayake

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.30 21:45:04