Python递归树实现背包问题：补全bmax_val与bfast_max函数空缺

以下是补全后的完整代码，包含bmax_val()和bfast_max()函数内的5处空缺修正，同时修复了create_item_list()的逻辑错误：

def comp_result(sub_lst, avail, count, level):
    nextitem = sub_lst[0]
    if nextitem[2] <= avail:
        chosen1, val1, count = bmax_val(sub_lst[1:],
                                        avail - nextitem[2], count, level)
        chosen1 = chosen1 + (nextitem,)
        val1 += nextitem[1]
        chosen2, val2, count = bmax_val(sub_lst[1:], avail, count, level)
        if val1 > val2:
            result = chosen1, val1, count
        else:
            result = chosen2, val2, count
    else:
        print("    " * (level + 1), "No left node")
        result = bmax_val(sub_lst[1:], avail, count, level)
    return result

def display(list_of_items, weight, level, flag = False):
    nlist = []
    for item in list_of_items:
        nlist.append(item[0])
    if flag:
        print("    " * level, nlist, weight, "Already solved")
    else:
        print("    " * level, nlist, weight)

def bmax_val(sub_lst, avail, count=0, level=-1):
    # 空缺1：层级递增，控制缩进
    level += 1
    # 空缺2：显示当前递归节点状态
    display(sub_lst, avail, level)
    if sub_lst == [] or avail == 0:
        result = (), 0, count
        display([], avail, level, True)
        return result
    count += 1
    result = comp_result(sub_lst, avail, count, level)
    return result

def fast_result (sub_lst, avail, memo, count, level):
    nextitem = sub_lst[0]
    if nextitem[2] <= avail:
        chosen1, val1, count = bfast_max(sub_lst[1:],
                                         avail - nextitem[2], memo, count, level)
        chosen1 = chosen1 + (nextitem,)
        val1 += nextitem[1]
        chosen2, val2, count = bfast_max(sub_lst[1:],avail, memo, count, level)
        if val1 > val2:
            result = chosen1, val1, count
        else:
            result = chosen2, val2, count
    else:
        print("    " * (level + 1), "No left node")
        result = bfast_max(sub_lst[1:], avail, memo, count, level)
    return result

def bfast_max(sub_lst, avail, memo={}, count=0, level=-1):
    # 空缺3：层级递增，控制缩进
    level += 1
    if (len(sub_lst), avail) in memo:
        # 空缺4：显示已缓存的节点状态
        display(sub_lst, avail, level, True)
        return memo[(len(sub_lst), avail)] + (count,)
    # 空缺5：显示当前递归节点状态
    display(sub_lst, avail, level)
    if sub_lst == [] or avail == 0:
        return (), 0, count
    count += 1
    result = fast_result(sub_lst, avail, memo, count, level)
    memo[(len(sub_lst), avail)] = result[0:2]
    return result

def create_item_list():
    names = ["a", "b", "c", "d"]
    vals = [6, 7, 8, 9]
    weights = [3, 3, 2, 5]
    list_of_items = []
    # 修复原逻辑错误：嵌套循环会重复添加元素，改为单循环
    for i in range(len(names)):
        list_of_items.append((names[i], vals[i], weights[i]))
    return list_of_items

def main():
    items = create_item_list()
    taken, val, count = bmax_val(items, 5)
    print("\n")
    for item in taken:
        print(item)
    print("Total value of items taken =", val, "count =", count)

    print("\n")
    taken, val, count = bfast_max(items, 5)
    print("\n")
    for item in taken:
        print(item)
    print("Total value of items taken =", val, "count =", count)
main()

空缺填充说明： #

1. bmax_val()内空缺1：level += 1——每次进入递归层级，将层级数加1，确保后续display函数的缩进正确对应递归树的深度。
2. bmax_val()内空缺2：display(sub_lst, avail, level)——在处理当前递归节点前，先打印节点的剩余物品列表和可用重量，绘制递归树的节点。
3. bfast_max()内空缺3：level += 1——同bmax_val的层级递增逻辑，控制带备忘录的递归树缩进。
4. bfast_max()内空缺4：display(sub_lst, avail, level, True)——当命中备忘录（已计算过的子问题）时，打印标记为"Already solved"的节点状态，体现剪枝效果。
5. bfast_max()内空缺5：display(sub_lst, avail, level)——处理未缓存的子问题前，打印当前节点状态，完成递归树的绘制。

另外修复了create_item_list()的嵌套循环错误，确保生成的物品列表是正确的4个唯一物品，而非重复元素。

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