如何判断贪婪算法是否足以找到最小的硬币变化？

Question

在最小硬币找零问题是一个NP完全问题,但对于某些套币的贪婪算法(选择最大面额第一)的作品.给定一组表示硬币值的整数,确定贪心算法是否足够的最快算法是什么？一个显而易见的方法是建立你的动态编程解决方案,直到最大面额,并看看它是否产生比贪婪方式更好的解决方案.但有没有更快的"数学方式"检测它？

Answer 1

如果以下选择产生目标金额，则贪婪算法将起作用：（可能有更复杂的格式可以起作用，但这很简单且易于检查）

让1代表选择。该套装以最大面额计算，如下所示：

11...1100...00100...00

也就是说，从最大的元素中选择零个或多个，并选择一个其他元素。

为什么这是最佳的很容易证明。设 C = 从最大的元素中选择的 s 个元素，那么我们知道 C 对任何 s 个或更少的元素产生最大可能的总和，因为，如果要替换 C 中的任何元素，则必须使用较低的元素来执行此操作值元素，因为已经选择了最大的元素（并且删除也会明显降低成本）。由于 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

哦，还有一个简单的情况，即 target = 0，需要检查是否允许。

上面需要一个目标金额，如果您想检查许多目标金额，您可以使用上述方法在 O(n^2) 中生成所有可能的总和，并获得总和到计数的映射，然后查找获取该值（如果存在）。

编辑：分支定界

作为上述内容的扩展和 DP 的替代方案，我建议使用分支定界进行贪婪的暴力处理。使用与上面类似的参数，您知道如果 bestCoins 具有值 和 ，则可以跳过当前路径(currentSum + (bestCoins - currentCoins) * currentItem.value) < target。

请注意，这在某些问题上可能会惨败，但在其他问题上却能发挥出色（我认为这很大程度上取决于我们多久找到一个合适的解决方案）。为了避免永远花费时间，您可以在最佳解决方案中存储尽可能少的硬币数量（通过查看第一个元素直到我们到达目标，类似于上面），并切断远离此的路径。

如果做得好，你应该能够运行它很短的时间，如果它运行完成并且我们有一个解决方案，我们就有了最佳解决方案，如果没有，我们没有损失太多时间并且可以运行另一个算法像DP。