这个问题专门针对硬币找零问题。 我知道找到最佳硬币数量的算法,可以找到任何数量的零钱,我也理解它,但我不明白的是,如果你愿意找到这样的解决方案,我怎么能“标记”。我曾尝试使用父指针,我确信这是这样做的方法,但我只是不知道如何实现它。这是一个例子。 例子: 给定硬币面额:1、10、25 变化:30 最优解需要:3个硬币 使用的硬币:10, 10, 10
我不太擅长解决动态规划问题。
最佳答案
你知道 T[30] = 3。你必须找到一个 T[30-c] = 2,尝试 {1, 10, 25} 中的所有 c。由于 T[30-10] = 2,您知道您将使用 10 美分硬币,现在必须解决 T[20] 的问题。
重复此操作直到 T[0] = 0。
关于algorithm - 使用动态规划输出解决方案的好方法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16451839/