8

最小硬币找零问题是一个 NP 完全问题，但对于某些硬币集合，贪心算法（首先选择最大面额）有效。给定一组表示硬币值的整数，确定贪心算法是否足够的最快算法是什么？一种明显的方法是将您的动态编程解决方案构建到最大面额，并查看每个解决方案是否比贪婪方式产生更好的解决方案。但是是否有更快的“数学方法”来检测它？

4

4 回答 4

1

我最近提出了 1 个解决方案，似乎表明如果满足给定的 2 个条件，贪心算法将产生最佳解决方案。

a) GCD（除 1 以外的所有面额）= 第二小面额。

b) 任意 2 个连续面额的总和必须小于第 3 个连续面额。

例如。c2 + c3 < c4。

（其中 c1 = 1；c2、c3、c4 是按升序排列的硬币面额）。

我知道这不是一个完整的解决方案。但是，我相信如果满足这两个条件，贪心算法将产生最优解。

于 2013-03-06T06:23:48.880 回答
1

Pearson 的论文A polynomial-time algorithm for the change-making problem Operation Research Letters 33:3（2005 年 5 月），第 231-234 页给出了一个多项式时间算法来找到贪心算法的最小反例（如果存在） . 不需要详尽的搜索，他的主要定理大大缩小了候选人的范围。

于 2021-01-19T15:54:07.690 回答
0

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

让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

哦，还有一个小例子，target = 0，需要检查它是否允许。

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

编辑：分支和绑定

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

请注意，这可能会在某些问题上失败，而在其他问题上却可以很好地工作（我认为这在很大程度上取决于我们多早找到合适的解决方案）。为避免永远占用，您可以在最佳解决方案中存储尽可能少的硬币数量（通过查看第一个元素直到我们到达目标，类似于上面），并切断远离此的路径。

如果做得对，你应该可以运行它很短的时间，如果它运行完成并且我们有一个解决方案，我们就有了最优解决方案，如果没有，我们不会浪费太多时间，可以运行另一个算法像DP。

于 2013-01-04T18:02:16.270 回答
-4

贪婪的解决方案仅适用于某些面额，相对于要进行更改的一定数量。

添加回溯步骤后，它就不再是贪心了，这最终会考虑找到所有可能的解决方案，因此它既不是动态规划问题。

示例：考虑硬币 = [2, 5]，要找零的数量是 16。贪婪优先的解决方案自然是先寻找最大面额，[5,5,5]，然后停留在 1。回溯step 产生另一个解决方案 [5, 5, 2, 2, 2]。

于 2011-07-01T03:55:33.040 回答