实验内容与实验步骤1、数字三角形问题 对于给定的由n行数字组成的数字三角形，计算从三角形的底至顶的路径经过的 数字和的最大值。如： 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 3、求子集问题 给定一个正整数集合X={x1,x2,…, xn}和一个正整数y，设计回溯算法求集合X 的一个子集Y，使得Y中元素之和等于y。

1、数字三角形问题

步骤：

1.读入数字三角形的行数n和具体数字三角形。

2.从第n-1行开始向上逐行计算，对于每个数字，将其与下面一行相邻的两个数比较取最大值，然后加上该数字，更新该位置的数值。

3.最终得到的数字三角形的顶部数字即为所求的最大值。

示例代码：

n = int(input())  #读入行数
triangle = []
for i in range(n):
    row = list(map(int, input().split()))
    triangle.append(row)

for i in range(n-2, -1, -1):  # 从倒数第二行开始向上逐行计算
    for j in range(i+1):
        triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1])

print(triangle[0][0])  #输出最大值

2、求子集问题

步骤：

1.读入正整数集合X和目标和y。

2.定义一个回溯函数backtrack，它的参数是当前考虑到的元素下标i和已选中的元素之和sum。

3.在回溯函数中，当sum等于目标和y时，将已选中的元素加入结果集合res。当i等于n时，返回。

4.对于当前考虑的元素xi，有选或不选两种可能性。如果选，将xi加入已选中的元素集合，并将i+1作为新的参数递归调用backtrack。如果不选，直接将i+1作为新的参数递归调用backtrack。

示例代码：

n, y = map(int, input().split())  #读入集合X和目标和y
X = list(map(int, input().split()))
res = []

def backtrack(i, sum, path):
    if sum == y:
        res.append(path[:])
        return
    if i == n:
        return
    #选当前元素
    path.append(X[i])
    backtrack(i+1, sum+X[i], path)
    path.pop()
    #不选当前元素
    backtrack(i+1, sum, path)

backtrack(0, 0, [])
print(res)  #输出符合条件的子集