COLCOIN-收集硬币

Question

我正在解决这个问题-COLCOIN-在spoj上收集硬币。链接-https://www.spoj.com/problems/COLCOIN/

对于给定的一组面额和你想要的货币，银行会给你最高面额的硬币，直到它不能再给你了，然后转移到下一个最高面额。例如：如果面额为[1,2,3,4,8]，如果您要求23卢比，它会先给您两个8卢比的硬币，因为它不能再给任何8卢比的硬币，所以会移动到下一个面额，给您一个4卢比和一个3卢比。

问题是找到最大数量的不同面额，你可以得到一个输入的面额。你从银行要求的钱是一个变量，它实际上不应该出现在图片中，如果我是正确的。

这是我的想法：

试着把低面额的面额加起来，看看它们是否能加起来成为大面额，如果它们是大面额，你就永远不会得到所有的小面额。

假设有1，2和5。1 2

另一个：假设有面额3,4和5。所以3 4

另一个明显错误的想法是从第二高面额开始，找到我们将添加到第二高面额的硬币，然后返回解决方案1（最高面额）。这是不正确的，因为，例如，[1,2,4,17,19]，如果我们计算19，试图将其他的18加起来，我们得到17，只有2个面值，而as 26会给出4个面值1942 1

Answer 1

我认为您可以使用以下方法：

1. 从最低面额开始

示例：1 3 6 8 15 20

1. 不同面额d=1，和=1
2. 1 3

=

实施：

js lang-js prettyprint-override">// expects the denominations to be ordered from smallest to largest
// and also expects them to be unique
function findMaxDenominationsInSingleWithdrawal(denominations) {
    if (denominations.length <= 2)
        return denominations.length
    let sum = denominations[0], d = 1
    for (let index = 1; index + 1 < denominations.length; index++) {
        if (sum + denominations[index] < denominations[index + 1]) {
            d++
            sum += denominations[index]
        }
    }
    return d + 1
}

console.log(findMaxDenominationsInSingleWithdrawal([1, 3, 6, 8, 15, 20]))