相关疑难解决方法(0)

我理解硬币改变问题的贪婪算法(用尽可能少的硬币支付特定金额)是如何工作的 - 它总是选择具有最大面额但不超过剩余总和的硬币 - 并且它总能找到正确的解决方案特定的硬币套装.

但是对于一些硬币集,有贪婪算法失败的总和.例如,对于集合{1, 15, 25}和总和30,贪婪算法首先选择25,剩余5,然后五个1,总共六个硬币.但硬币数量最少的解决方案是选择15两次.

一组硬币必须满足哪些条件才能使贪心算法找到所有金额的最小解？