博客

算法与数据结构的python语言描述这本书在介绍栈的一章，讲到任何一个递归函数都可以引入一个栈保存中间结果来改为非递归函数。从而讲到简单的背包问题的递归实现。任何具有递归性质的问题通过函数递归调用会变得很简单。一个很复杂的问题，几行代码就能搞定。

背包问题：

问题描述:一个背包里放入重量为bagWeight的物品，现有n件物品的集合S，其中物品的重量itemWeight为 w0，w1，…w(n-1)。问题是能否选出若干件物品，其重量之和正好等于bagWeight。

递归树分析：

每次分为两种情况，一共

种情况，看似十分复杂。

但是从最后结果的角度，一共两种情况：

• 到Wn-1已经够bagWeight

• 加上Wn刚好够bagWeight

上面两种情况一个有解，那问题就有解，于是我们可以把Wn从背包去掉倒退回去看weight的值。

经过一系列倒推，bagWeight的值有下面三种情况：

1. bagWeight刚刚等于0  （正好凑出weight的重量）
   
   说明有解
   

2. bagWeight<0
   
   不可能，所以无解
   

3. bagWeight>0 and 没有itemWeight 了  （所有的物品都减完了还没有达到重量）
   
   也不可能，无解
   

   以上三种即为递归中止条件

 """使用1到n的物品去填充 bagWeight 容量的包
 返回能否填充"""

def knap(bagWeight, itemWeight, n):

    # bagWeight为包的容量，itemWeight是一个物品重量表，n为物品编号
    if bagWeight == 0: #递归中止条件
        return True

    if bagWeight < 0 or (n == 0 and bagWeight > 0): #递归中止条件
        return False

    if knap(bagWeight - itemWeight[n - 1], itemWeight, n - 1): # 情况1：装了物品
        print(itemWeight[n - 1])
        return True

    if knap(bagWeight, itemWeight, n - 1):  # 情况2：没装物品
        return True
    else:
        return False