分治策略与动态规划算法实验

实验目的

实验内容

整数划分问题 将一个正整数n拆成一组数连加并等于n的形式，且这组数中的最大加数不大于n。即：n=n1+n2+…+nk，n1>=n2>=n3…>=nk。正整数的不同划分个数称为正整数n的划分数，记为p(n)。例如：p(6)=11。如整数的6划分为：

6 5 + 1 4 + 2, 4 + 1 + 1 3 + 3, 3 + 2 + 1, 3 + 1 + 1 + 1 2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1 + 1共11种。

统计7的整数划分数，并将结果进行输出。

输入：1 -2 4 5 -2 8 3 -2 6 3 7 -1 输出：32 , [3 , 11]

用简单算法、分治、动态规划算法分别编写程序。

硬币选择问题 现有n个硬币按顺序依次排列在你面前，它们的面值可以看作一个数组coins[]={5,1,2,10,6,2}，请在此中选取若干个硬币，使得所取硬币面值总和最大，捡取个数不限，但相邻的硬币不能捡取，请设计动态规划算法，要求能够输出累加值和选取的硬币序号（硬币面值为正数）。
最优加工顺序问题 有7个工件,它们在第一台机器和第二台机器上的处理时间分别为: [t11,t12,t13,t14,t15,t16,t17]=[3,8,10,12,6,9,15]，[t21,t22,t23,t24,t25,t26,t27]=[7,2,6,18,3,10,4],这7个工件的最优加工顺序为[1,6,4,3,7,5,2]。用动态规划算法编写程序。

实验总结

通过这个实验，我们主要学习了分治策略和动态规划的基本方法。

在整数划分问题中，我们掌握了将一个正整数拆分成一组数连加并等于原数的方法，并统计了不同划分个数。通过这个问题的实践，我们对分治策略有了更深入的理解。

在连续子段和最大值问题中，我们通过简单算法、分治和动态规划三种算法分别解决了问题，并且比较了它们之间的差异。通过这个问题的实践，我们进一步掌握了动态规划方法的基本思想和应用。

在硬币选择问题中，我们设计了一个动态规划算法来选择硬币，使得取出的硬币面值总和最大。通过这个问题的实践，我们进一步巩固了动态规划方法的应用。

在最优加工顺序问题中，我们使用了动态规划算法来确定工件的最优加工顺序。通过这个问题的实践，我们进一步熟悉了动态规划算法的具体步骤和应用。

总的来说，通过这个实验，我们对分治策略和动态规划的基本方法有了更深入的理解，并且通过实践掌握了它们在不同问题中的应用。这些方法在解决实际问题中具有很大的实用性和效果。