使用动态规划解决最少硬币找零问题的C++实现

"该资源是使用C++编程语言实现的动态规划算法，旨在解决最少硬币找零问题。代码展示了如何通过动态规划方法求解给定面额的硬币找到指定金额所需的最少硬币数量。" 在这个问题中，动态规划是一种有效的方法，它通过将大问题分解为更小的子问题来解决。这里的目标是最小化用不同面额硬币找零所需硬币的数量。函数`Coins`接收四个参数：`n`表示硬币种类数，`T`是一个整数数组，存储每种硬币的面额，`coins`是另一个整数数组，表示每种硬币的数量，`m`是要找零的总金额。 首先，创建一个长度为`n+1`的数组`sum`，用于存储到当前硬币种类为止的总金额。初始化`sum[0] = 0`，表示没有使用任何硬币时的总金额为0。 接着，创建一个二维数组`z`，同样大小为`n+1`，用于存储到达每个金额`j`所需的最小硬币数。`z[i][j]`表示使用前`i`种硬币找零`j`所需的最小硬币数。 在双重循环中，外层循环遍历所有硬币种类，内层循环遍历所有可能的金额。对于每个金额`j`，如果`j`等于0，那么所需的硬币数自然为0；如果`sum[i]`小于`j`，表示当前硬币种类无法凑出`j`，所以设置`z[i][j]`为无穷大（在这里表示为`BT20001`）。 对于特殊情况，当只有一个硬币种类时，如果`j`能被硬币面额整除且硬币数量足够，`z[1][j]`就是`j`除以硬币面额的结果；否则，返回无穷大。 在一般情况下，使用一个三重循环来找出最小硬币数。遍历0到当前硬币数量，并计算使用`k`个当前硬币加上之前硬币种类找零`j-k*T[i]`的最小硬币数`x`。如果`x`比当前已知的最小值`min`还要小，就更新`min`。最后，`z[i][j]`就设置为`min`。 在主函数`main`中，程序从文件`input.txt`读取数据（包括硬币种类数`n`，每种硬币的面额`T`，每种硬币的数量`coins`以及找零的总金额`m`），然后调用`Coins`函数计算结果，并将结果写入`output.txt`。 这个动态规划解决方案的时间复杂度是O(n*m)，空间复杂度也是O(n*m)，其中n是硬币种类数，m是找零的总金额。这是因为我们需要一个二维数组来存储所有状态。尽管空间需求较高，但相比其他非动态规划的解决方案，这种方法可以有效地避免了重复计算，提高了效率。