砝码称重问题的动态规划解法

"这篇实验报告主要探讨了使用动态规划解决砝码称重问题，旨在计算用给定的砝码组合可以称出多少种不同的重量。报告由海南师范大学计算机科学与技术专业的学生李建峰和陈玉健完成。实验中，算法设计的核心是通过递推公式动态地更新可以称出的重量计数，避免重复计数，并利用一个布尔型数组记录不同重量是否已出现。" 在砝码称重问题中，给定不同种类和数量的砝码，目标是找出所有可能组合成的重量。本实验报告关注的是如何设计一个算法来有效地解决这一问题。实验的具体内容是，首先读取数据文件，文件包含砝码的种类数（n）、每种砝码的重量以及每种砝码的数量。然后，通过动态规划方法求解问题。 动态规划在这里的应用是基于这样的思路：假设前i个砝码可以称出的重量集合为Q[i]，那么Q[i]可以通过在Q[i-1]的基础上，对每个重量添加0到c[i]个砝码i来计算，同时排除重复的重量。这里的c[i]表示第i种砝码的数量，w[i]表示第i种砝码的重量。动态规划的状态转移方程可以表示为：Q[i] = (Q[i-1] + k * w[i]) - 重复的个数，其中0 <= k <= c[i]。 为了跟踪不同重量是否已经被计算过，报告中定义了一个布尔型数组cm[1001]，cm[c]为1表示重量c的情况已经出现，0则表示未出现。数组的初始状态全部为0，cm[0]作为临时变量使用。最后，通过遍历cm数组，统计值为1的元素个数，即可得到不同重量的种类数。 在程序实现部分，报告提供了C语言的基本框架，包括输入函数input()用于读取砝码数据，exeDP()函数执行动态规划算法，以及output()函数输出结果。程序中，sum存储所有砝码的总质量，n表示砝码种类数，amount[]和weight[]分别存储砝码的数量和重量，而cm[]数组则是动态规划的关键数据结构。 总结来说，这个实验报告通过动态规划算法解决了砝码称重问题，展现了如何利用递推关系和辅助数据结构来高效地计算可能的重量组合，对于理解动态规划及其在实际问题中的应用具有很好的示例作用。