综合题
1. 贪心法（设计+证明）
贪心算法的设计思想：
- 贪心算法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。贪心算法对于大部分的优化问题都能产生最优解，但不能总获得整体最优解，通常可以获得近似最优解。
贪心算法的证明：
2.0/1背包问题（证明+动态规划法计算过程）
- 证明（反证法）
- 动态规划法计算过程
3.货币兑付问题（证明+动态规划法计算过程）
- 题目： 在面值为(v1, v2, …, vn)n种货币中，需要支付y值的货款，应如何支付才能使货币支付的张数最少。设计动态规划算法求解该问题。
- 证明
暂无 - 解决
示例：面值(1, 2, 5, 10)，支付8
示例：面值(2, 5, 10)，支付8
4.多段图最短路径问题（证明+动态规划法计算过程）
-
问题
-
证明
-
动态规划法计算过程
5.多机调度或批处理调度（限界函数设计+搜索过程）
-
问题描述
-
限界函数设计
-
搜索过程
（1)在根结点，将sum1和sum2分别初始化为0,估算目标函数的上界为41,将根结点加入待处理结点表PT.
6.TSP问题（搜索空间树及算法）
- 问题描述 假设有一个旅行商要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。旅行商有一个要访问城市的列表和每两个城市之间旅行的开销。需要求出开销最短的一种走法。
- 搜索空间树
- 算法
