0

uva 166 - dp 问题在这里

因此,如果我们需要支付 55c,而我们没有持有 50c 的硬币,我们可以按 2*20c + 10c + 5c 支付,总共 4 个硬币。如果我们出价 1 美元,我们将收到 45c 的找零,这也涉及 4 个硬币,但如果我们出价 1.05 美元(1 美元 + 5c),我们会得到 50c 的找零,而易手的硬币总数只有 3 个。

我不是在寻求解决方案,我不明白这个例子在说什么:

所以,我们需要支付 55c ,硬币 = {5,10,20} ,55c = 2*2 + 1*10 + 1*5 - 4 个硬币。

但下一步是什么?“如果我们投标 1$,我们将收到 45c?这是什么意思?1 - 45 = 55?是的,这很明显,但问题只是问如何更改 55C?

最后一个是1.05?但是对于 1.05 案例 - 他们不知道有哪些硬币可用!完全混乱

有人可以提供更多细节吗?我不明白这个问题和例子!

4

1 回答 1

0

它不是在问如何兑换 55c,而是在问如何将 55c 给其他人,以使易手的硬币数量最小化。

即尽量减少你给他们的硬币数量,加上他们必须给你的硬币数量作为找零。

于 2015-01-21T20:37:57.993 回答