【西南科技大学】算法报告3

【西南科技大学】的《算法设计与分析》课程中，学生们研究了一个名为“Coin-row problem”的算法问题。这个问题的核心在于如何在一系列硬币中选择出总价值最大的一组，但有一个关键约束：所选硬币必须互不相邻。这个问题在实际应用中可能涉及到资源分配、优化策略等场景。 一、问题描述 Coin-row problem 是一个经典的动态规划问题。给定一排 n 个硬币，每个硬币具有不同的正整数值 c₁, c₂, ..., cn。目标是在不违反相邻硬币不可同时选取的规则下，找到一种选取方法，使得选取的硬币总价值达到最大。 二、解题方案 1. 实验环境：实验在 Windows 10 操作系统上，使用 Visual Studio 2019 开发环境进行。 2. 解题思路：采用自底向上的动态规划方法解决。设 F(i) 表示前 i 个硬币中能获得的最大价值，对于每个硬币 i，有两种决策： - 选择硬币 i，则 F(i) = F(i - 2) + Ci。 - 不选择硬币 i，则 F(i) = F(i - 1)。 由此，得到递推公式：F(n) = max{F(n - 2) + Ci, F(n - 1)}。 3. 特殊情况处理： - 当 n = 0 时，没有硬币可选，F(0) = 0。 - 当 n = 1 时，只有一枚硬币，F(1) = C1。 4. 伪代码实现： 初始化 F(0) = 0 和 F(1) = C1，然后通过循环计算从第二个硬币到第 n 个硬币的最大价值，每次计算 F[i] 时，取 F[i - 2] + Ci 和 F[i - 1] 中的较大值。 三、实验结果与分析 实验以硬币序列 5, 1, 2, 10, 6, 2 为例，逐步计算 F[i] 的值，最终得出 F[6] = 17 为最大总价值。通过流程图和执行截图，可以观察到算法的执行过程和结果。 四、问题总结 实验过程中，由于没有有效避免回溯过程中的重复计算，导致了结果的不准确。此外，初期思路不够清晰，忽视了回溯可能导致的效率问题。 五、参考资源 学习算法分析与设计的相关书籍以及网络博主“浅夏淡香”的分享，提供了重要的理论支持和实践指导。 通过这个实验，学生不仅掌握了动态规划的基本思想，还对算法优化有了更深入的理解，尤其是在处理复杂问题时，如何有效地避免重复计算以提高算法效率。这对于未来解决类似的实际问题有着重要的理论与实践意义。