实验目的

1.掌握动态规划解决问题的一般过程。
2.通过使用动态规划算法求解给定问题，学会使用动态规划解决实际问题。

实验内容

1.天平平衡问题：已知一个天平左右两端共有n个挂钩，且有m个不同质量的钩码，求将钩码全部挂到钩子上使天平平衡的方法的总数。试设计求解该问题的动态规划算法。
2.数塔问题 ：对于诸如下图的数塔，若从顶层走到底层，每一步只能走到相邻的结点，求经过的结点的数字之和最大的路径。试设计求解该问题的动态规划算法。

算法描述

1天平平衡问题：
要求的是，m个砝码全部挂在钩子上使得天平平衡，所以这m个钩码，只可以分配到天平的左右两边，以来使得左右平衡，即使得左右两边的钩码重量之和相等；所以分析得，左边或者右边的钩码重量之和是全部钩码重量之后的二分之一，再次分析原问题就变成了，通过数组组合，使m个数字分成两组，并这两组数字和相等，数字即来表示钩码的重量
2数塔问题
算法思想：自顶向下进行分析，自底向上执行计算
从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只有左右两道路径上的最大值求出来了才能作出决策。同样的道理下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。
所以第一步对第五层的8个数据，做如下四次决策：
如果经过第四层2，则在第五层的19和7中肯定是19；
如果经过第四层18，则在第五层的7和10中肯定是10；
如果经过第四层9，则在第五层的10和4中肯定是10；
如果经过第四层5，则在第五层的4和16中肯定是16；
经过一次决策，问题降了一阶。5层数塔问题转换成4层数塔问题，如此循环决策…… 最后得到1阶的数塔问题。
算法实现：
输入：二维数组number数塔的原始数据，二维数组dp决策的结果；
1.初始化dp， dpn = datan (j = 1, 2, …, n) ；

1. 在动态规划过程汇总，dpi = max(dpi+1, dpi+1) + datai，最后的结果保存在dp0中。

程序及运行结果

1. 天平平衡问题：
   实例：

def tianping(m, n, a):
    h = [0] * 100
    h[0] = 1
    for i in range(1, n + 1):
        for j in range(m, 0, -1):
            if j >= a[i - 1]:
                h[j] = h[j] + h[j - a[i - 1]]

    for j in range(0, m + 1):
        print(h[j], end=' ')
    return h


if __name__ == '__main__':
    m1 = 27  # 全部钩码的重量之和的二分之一，问题中的n
    n1 = 9  # 钩码的数量，即题目中的m（个钩码）
    a1 = [10, 9, 8, 7, 6, 5, 4, 3, 2]
    print('m1=', m1)
    print('n1=', n1)
    print('a1=', a1)
    print('运行结果为：')
    tianping(m1, n1, a1)
    print()
    m2 = 10
    n2 = 4
    a2 = [7, 6, 4, 3]
    print('m2=', m2)
    print('n2=', n2)
    print('a2=', a2)
    print('运行结果为：')
tianping(m2, n2, a2)

结果：

2.数塔问题：
实例：

def tower(n, data):
    dp = data
    for i in range(n - 2, -1, -1):
        for j in range(i, -1, -1):
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + data[i][j]
    print('经过的结点的数字之和最大的路径为')
    print(dp[0][0])
    print('决策的结果为')
    for i in range(0, n):
        for j in range(0, i + 1):
            print(dp[i][j], end=' ')
        print()
    return dp


if __name__ == '__main__':
    n1 = 5
    a1 = [[9, 0, 0, 0, 0],
          [12, 15, 0, 0, 0],
          [10, 6, 8, 0, 0],
          [2, 18, 9, 5, 0],
          [19, 7, 10, 4, 16]]
    print('数塔的原始数据为')
    for i in range(0, n1):
        for j in range(0, i + 1):
            print(a1[i][j], end=' ')
        print()
    tower(n1, a1)

结果：

总结

实验心得体会：

通过本次实验，我掌握了动态规划解决问题的一般过程。并通过使用动态规划算法求解给定问题，学会了使用动态规划解决实际问题。

改进意见：

在数塔问题中，Python的N维数组的新建遇到了困难，在使用a=[[0]n]n时发现产生了浅拷贝问题，最终改用传统办法[[],[],[]]。

实验成绩： 指导教师： 年 月 日