algorithm - 减少易手的硬币数量

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center。
你有一套硬币5美分，10美分，20美分，50美分，1美元，2美元和每个面额的有限数量。当你付了一些钱时，有两种可能：你付了正确的钱，或者你付了比需要的多的钱，然后从职员那里得到了正确的零钱。你怎样才能把换手的硬币数量降到最低（即，把你给的硬币数量加上你收到的硬币数量降到最低）假设总要付这笔钱，而职员有无限多的硬币，再加上他总是选择最有效的方式来回馈零钱。
我想，为了减少换手硬币的数量，你必须同时减少你给的硬币和你收到的硬币的数量。使用通常的硬币更换算法可以将收到的硬币数量最小化，但是我不知道如何在给定一组固定硬币的情况下最小化一组更改。
完整的问题描述：UVA Online Judge

最佳答案

将硬币总数减至一定数量是Knapsack Problem的一个版本。
您的问题是尽量减少coins(S1) + coins(S2)（您对文员+文员对您）其中S1 - S2 = S（您应该支付的金额）。因此，您希望解决背包问题，即S和Smax之间的所有变化值（知道coins(x)的所有值），然后解决：

min coins(S1) + coins(S2)
under constraints
  S1 - S2 = S
  S1 in [S, Smax]

这可以通过简单的枚举（测试s1的每个可能值）来解决。
现在的问题是确定 Smax的值。
我不确定这个，但我想，因为你最大的硬币是2美元，如果你给店员大于S+2美元的东西，你不会有任何更少的硬币转移。所以我的猜测是，但是我请你多考虑一下。

关于algorithm - 减少易手的硬币数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15252358/

上一篇：java - 改进循环赛以在不同的 table 上进行比赛

下一篇：algorithm - 根 n^3 函数之和的 Θ 复杂度是多少？

Answer 1

将硬币总数减至一定数量是Knapsack Problem的一个版本。
您的问题是尽量减少coins(S1) + coins(S2)（您对文员+文员对您）其中S1 - S2 = S（您应该支付的金额）。因此，您希望解决背包问题，即S和Smax之间的所有变化值（知道coins(x)的所有值），然后解决：

min coins(S1) + coins(S2)
under constraints
  S1 - S2 = S
  S1 in [S, Smax]

这可以通过简单的枚举（测试s1的每个可能值）来解决。
现在的问题是确定 Smax的值。
我不确定这个，但我想，因为你最大的硬币是2美元，如果你给店员大于S+2美元的东西，你不会有任何更少的硬币转移。所以我的猜测是，但是我请你多考虑一下。