硬币变化问题是一个NP完全问题，但对于某些硬币集，贪婪算法（首先选择最大面额）有效。给定一组表示硬币价值的整数，确定贪婪算法是否足够的最快算法是什么？一种明显的方法是建立你的动态编程解决方案，直到最大的面额，看看每个解决方案是否比贪婪的方式产生更好的解决方案。但是有没有更快的"数学方法"来检测它呢？
我最近提出了 1 个解决方案，似乎表明如果满足给定的 2 个条件，贪婪算法将产生最佳解决方案。
a） G.C.D（除1外的所有面额）=第二小面额。
b） 任何连续2个面额的总和必须小于连续第3个面额。
例如 c2 + c3 <c4。>
（其中c1 = 1;c2，c3，c4是按升序排列的硬币面额）。
我知道这不是一个完整的解决方案。但是，我相信如果满足这两个条件，贪婪算法将产生最优解。
皮尔逊的论文 变革问题的多项式时间算法 运筹学快报 33：3（2005 年 5 月），第 231-234 页给出了一个多项式时间算法来找到贪婪算法（如果存在）的最小反例。不需要详尽的搜索，他的主要定理大大缩小了候选集的范围。
如果以下选择产生目标金额，贪婪算法将起作用：（可能有更复杂的格式可以工作，但这检查起来很简单且线性）
让1表示选定项。该集合来自最大面额，如下所示：
11...1100...00100...00
也就是说，从最大元素中选择零个或多个元素，并选择单个其他元素。
为什么这是最佳的很容易证明。设 C = 从最大元素中选择的 s 元素，那么我们知道 C 为任何 s 或更少的元素产生最大可能的总和，因为如果要替换 C 中的任何元素，则必须使用较低值的元素，因为 s 最大的元素已经被选中（删除也会明显降低成本）。由于 C 产生的值小于目标（因为需要另一个元素），我们至少需要一个其他元素才能到达目标，因此到达目标所需的最小元素数量为 s+1，这结束了证明。
你需要 O（n） 来评估这一点，这可以按如下方式完成：（在 Java 中）
int[] sortedCoins = ...;
int sum = 0, selectionCount = 0, i = 0;
for (; i < sortedCoins.length; i++)
{
sum += sortedCoins[i];
if (sum >= target) break;
selectionCount++;
}
sum -= sortedCoins[i]; // we added the element to push us over, so remove it again
for (; i < sortedCoins.length; i++)
{
if (sum + sortedCoins[i] == target)
return selectionCount+1;
}
return -1; // not found
哦，还有一个微不足道的情况，目标 = 0，需要检查它是否被允许。
上面需要一个目标金额，如果你想检查很多目标金额，你可能可以用上面的方法在 O（n^2） 中生成所有可能的总和，并有一个总和到计数的映射，只需进行查找即可获取值（如果存在）。
编辑：分支和绑定
作为上述内容的扩展和 DP 的替代方案，我建议用分支和绑定贪婪地处理蛮力。使用与上面类似的参数，您知道如果 bestCoins具有值并且(currentSum + (bestCoins - currentCoins) * currentItem.value) < target，则可以跳过当前路径。
请注意，这可能会在某些问题上惨遭失败，但在其他问题上效果很好（我认为这在很大程度上取决于我们找到一个像样的解决方案的早期程度）。为了避免永远花费，您可以将尽可能少的硬币存储在最佳解决方案中（从查看第一个元素得出，直到我们到达目标，类似于上面），并切断远离此的路径。
如果做得好，你应该能够运行它一小段时间，如果它运行完成并且我们有一个解决方案，我们有最优解决方案，如果没有，我们没有浪费太多时间，可以运行另一个算法，如 DP。
贪婪的解决方案仅适用于某些面额，相对于要进行更改的特定金额。
添加回溯步骤后，它就不再贪婪了，这最终考虑了找到所有可能的解决方案，因此它既不是动态编程问题。
示例：考虑铸币 = [2， 5]，要更改的金额为 16。贪婪的第一个解决方案自然是先寻找最大的面额，[5,5,5]，然后停留在1。回溯步骤产生另一种解决方案[5， 5， 2， 2， 2]。