分治与动态规划算法实验

实验结果与分析：

1. 整数划分问题：

• 输入：n=7
• 输出：p(7)=15
  • 划分方式为：7, 6+1, 5+2, 5+1+1, 4+3, 4+2+1, 4+1+1+1, 3+3+1, 3+2+2, 3+2+1+1, 3+1+1+1+1, 2+2+2+1, 2+2+1+1+1, 2+1+1+1+1+1, 1+1+1+1+1+1+1

2. 连续子段和的最大值和区间：

• 输入：序列a = [1, -2, 4, 5, -2, 8, 3, -2, 6, 3, 7, -1]
• 输出：最大值为32，区间为[3, 11]

3. 选取硬币面值总和最大：

• 输入：硬币面值数组coins[]={5,1,2,10,6,2}
• 输出：最大累加值为17，选取的硬币序号为[1, 4, 6]

4. 工件的最优加工顺序：

• 输入：工件在第一台机器上的处理时间数组t1=[3,8,10,12,6,9,15]，工件在第二台机器上的处理时间数组t2=[7,2,6,18,3,10,4]
• 输出：最优加工顺序为[1, 6, 4, 3, 7, 5, 2]

分析：

• 实验一是要求统计一个正整数的划分数，通过分治或动态规划算法可以得到结果。
• 实验二是要求找出一个序列中连续子段和的最大值和区间，同样可以通过分治或动态规划算法解决。
• 实验三是要求选取硬币面值总和最大，可以使用动态规划算法来解决。
• 实验四是要求找出工件的最优加工顺序，同样可以使用动态规划算法来解决。