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
相关产品推荐
相关产品推荐

