选择零钱最少或没有变化的硬币

我正在制作一个游戏，由10美元，5美元，3美元和1美元的硬币组成。玩家的物品栏中可能拥有0种或更多种货币，总共最多15个硬币。我试图弄清楚如何正确选择硬币，以便给予最少的零钱作为回报。起初我以为这很容易解决，但现在我很难解决这个问题。

以下是进一步解释这种情况的两个示例：

示例 1：

用户携带这些硬币：$ 5，$ 3，$ 3，$ 3，$ 1，$ 1，$ 1，$ 1，并且想要以$ 12的价格购买物品。解决方案是用5美元，3美元，3美元，1美元支付，并且不给零钱。

示例 2：

用户没有任何1美元的硬币，并且携带5美元，3美元，3美元，3美元，3美元。一件物品以12美元的价格购买，因此他们以5美元，3美元，3美元和3美元支付，并退还2美元的零钱。

由于我们首先选择较大的硬币，我无法弄清楚的是，如何知道玩家的库存中是否有足够的低价值硬币（在本例中为1美元）来容纳示例1，以及是否没有足够的硬币来使用更多价值较高的硬币，如示例2所示。

在下面的示例中可以看到另一个问题，尽管我很高兴上述两个示例正常工作：

示例 3：用户携带这些硬币：$ 5，$ 3，$ 3，$ 3。玩家以6美元的价格购买东西。最好使用 $3 和 $3 并且不返回任何零钱，而不是使用 $5 和 $3 并给予 $2 的零钱。

我相信前两个例子可以使用递归和贪婪算法的变体来解决。

对于赏金奖励：

我在下面添加了我自己的答案，作为现在的临时解决方案。但是，我喜欢Llama先生下面的方法（请参阅他引用的链接），并希望找到一个PHP示例来满足这一点。我相信这种方法不需要递归，而是使用记忆。

如果对最少的零钱有多种选择，那么我希望将领带给予以最少的硬币支付的货币。