告
专 业 姓 名 实验名称 实验目的 实验内容 班 级 学 号 实验二：动态规划算法设计 1.掌握动态规划解决问题的一般过程。 2.通过使用动态规划算法求解给定问题，学会使用动态规划解决实际问题。 1、天平平衡问题：已知一个天平左右两端共有n个挂钩，且有m个不同质量的钩码，求将钩码全部挂到钩子上使天平平衡的方法的总数。试设计求解该问题的动态规划算法。 2、数塔问题 ：对于诸如下图的数塔，若从顶层走到底层，每一步只能走到相邻的结点，求经过的结点的数字之和最大的路径。试设计求解该问题的动态规划算法。 1. 天平平衡问题的解题思路或算法思想： m个钩码要么挂在左边，要么挂在右边，使得左右平衡，也就是说使得左右两边的钩码重量之和相等；很自然的就能知道，左边或者右边的钩码重量之和是全部钩码重量之后的二分之一。此时，问题就转换成：数组组合问题m个数字，数字即钩码的重量 2. 数塔问题的解题思路或算法思想： 自顶向下进行分析，自底向上执行计算 从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只有左右两道路径上的最大值求出来了才能作出决策。同样的道理下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。 所以第一步对第五层的5个数据，做如下四次决策： 如果经过第四层2，则在第五层的19和7中肯定是19； 如果经过第四层18，则在第五层的7和10中肯定是10； 如果经过第四层9，则在第五层的10和4中肯定是10； 如果经过第四层5，则在第五层的4和16中肯定是16； 经过一次决策，问题降了一阶。5层数塔问题转换成4层数塔问题，如此循环决策…… 最后得到1阶的数塔问题。 算法描述 1. 天平平衡问题的程序： package com.t7; public class Tianping{ public static void main(String[] args) { int m = 27; //全部钩码的重量之和的二分之一，问题中的n int n = 9; //钩码的数量，即题目中的m（个钩码） int a[] = {10,9,8,7,6,5,4,3,2}; int h[] =new int[1001]; h[0]=1; for (int i = 1; i <=n; i++) { for (int j = m; j >=1; j--) { if(j>=a[i-1]){ h[j]=h[j]+h[j-a[i-1]]; } } } for (int j = 0; j <=m; j++) System.out.print(h[j]+\" \"); } } 程序及运行结果 实例： 2. 数塔问题的程序： package com.t4; import java.util.Scanner; public class Main { public static void main(String [] args){ System.out.print(\"输入数组的层数: \"); Scanner scan=new Scanner(System.in); int n=scan.nextInt();//定义数塔层数n; int d[][]=new int[n][n]; System.out.print(\"输入数组元素：\"); for(int i=0;i 实验成绩： 指导教师： 年 月 日 因篇幅问题不能全部显示，请点此查看更多更全内容