子集和问题 #

1. 子集和问题的介绍
2. 子集和问题的算法分析
3. 子集和问题代码实现

子集和问题的介绍 #

给定n个正整数W=(w1, w2, …, wn)和正整数M，要从集合W中选取一个子集，使得子集的和为M。例如集合W={1,2,3,4,5,6,9,11},M=10则满足条件的子集有{4, 6},{2, 3, 5},{1, 9},{1, 4, 5},{1, 3, 6},{1, 2, 3, 4}

子集和问题的算法分析 #

在回溯算法2中，我们已经详细讲解了如何使用回溯算法求解一个集合的子集，因此我们可以求出集合w的所有子集，然后判断子集的和是否为10，从而寻找符合条件的子集

子集和问题的代码实现 #

w=[1,2,3,4,5,6,9,11]#集合w
path=[0]*8#定义path[0]表示w[0]的集合是否被选中，以此类推
def dfs(step):#定义回溯函数dfs(step),step代表了每一步，也是递归的深度
    if step>8: 
        subset=[w[i] for i in range(8) if path[i]]##已经完成了8步，生成了w的一个子集
        if(sum(subset)==10):#判断子集的和是否为10
            print(set(subset),end=",")
        return
    path[step-1]=0#当前路径选择0
    dfs(step+1)
    path[step-1]=1#当前路径选择1
    dfs(step+1)
dfs(1)

小结 #

• 根据子集和问题，理解回溯算法在子集问题中的应用
• 掌握子集和问题求解的回溯算法

习题 #

1. 上述问题中集合w中的元素11其实是多余的，基于此请对上述算法做优化
2. 上述求解子集和问题中，如果我们当前的子集和已经超过了10是没必要递归到第八步，基于此请对上述算法做优化