算法设计与分析实验六：使用动态规划算法解决存钱问题（java实现、hdu1114）（csdn）————程序.pdf

在这个实验中，主要的目标是通过动态规划算法来解决一个实际问题——如何在不打破存钱罐的情况下，找到装满存钱罐所需的最小金额。实验使用Java语言进行实现，并且是针对HDU 1114题目的解决方案。 动态规划是一种有效的解决优化问题的方法，它通过将大问题分解为小问题，然后逐个解决这些小问题，最终得到原问题的解。在这个存钱罐问题中，动态规划的核心思想是状态转移方程。具体来说，我们可以定义一个二维数组`dp`，其中`dp[i]`表示装满重量为`i`克的存钱罐所需的最小金额。初始状态`dp[0]=0`，表示空存钱罐不需要任何金额就能装满。 输入部分包括测试用例的数量`T`，以及每个测试用例的空存钱罐和装满存钱罐的重量`empty`和`full`，还有硬币的种类数量`n`，以及每种硬币的面值和重量。程序通过`Scanner`类从标准输入读取这些数据。 在初始化阶段，`dpInit()`函数将`dp`数组的所有元素初始化为一个较大的数值（这里设置为500000001），除了`dp[0]`，这样在之后的状态转移过程中，如果找不到更优解，就会保留当前的最小值。 动态规划的核心在于`dpSolve()`函数，该函数通过两层循环遍历所有硬币和可能的重量。外层循环遍历每种硬币`i`，内层循环从硬币的重量`weights[i]`到存钱罐的容量`volume`，在每个位置`j`上，尝试使用当前硬币，如果添加硬币后得到的金额`dp[j-weights[i]] + values[i]`小于当前的`dp[j]`，就更新`dp[j]`。这个过程反映了动态规划的状态转移，即在已知装满重量`j-weights[i]`的最小金额的基础上，加上第`i`种硬币的面值，来寻找装满`j`重量的最小金额。 输出部分检查`dp[volume]`的值，如果等于初始化的大数500000001，说明无法找到装满存钱罐的方案，输出"这是不可能的"；否则，输出"存钱罐内的最小金额是"加`dp[volume]`的值。 程序运行的结果会展示每个测试用例的输出，根据样例输入，程序应该能够正确地计算出每个存钱罐的最小金额，或者在无法装满时给出相应的提示。这个实验不仅锻炼了对动态规划的理解，还涉及了Java编程技巧和输入输出处理。