algorithm - 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< 5。所以你可以得到所有面额。8 = 5+2+1

另一个：假设有面额 3,4 和 5。所以 3+4>5 所以，我们永远无法得到所有面额。因为钱将以 5 的面额给出，直到应该给出的钱小于 5。显然你不能用小于 5 的东西得到 3+4=7 卢比

另一个显然是错误的想法是从第二大面额开始，找到我们将添加到其中的硬币并返回该解决方案+1（最高面额）。这是不正确的，因为例如 [1,2,4,17,19]，如果我们已经数 19 并试图将其他人加起来为 18，我们得到 1+17，除此之外只有 2 个面额，其中 26会给出 4 个面额 19+4+2+1

标签： algorithmgreedy

Answer 1

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

1. 从最低面额开始
2. 检查添加下一个最低面额是否超过其后的面额
   1. 如果总和较小，则将面额添加到总和中
   2. 否则继续并检查面额是否进一步不超过之后的面额。

示例：1 3 6 8 15 20

1. 不同面额 d = 1, sum = 1
2. 1 + 3 < 6：d = 2，总和 = 4
3. 4 + 6 >= 8：d = 2，总和 = 4
4. 4 + 8 < 15：d = 3，总和 = 12
5. 12 + 15 >= 20：d = 3，总和 = 12
6. 12 + 20 < 无穷大：d = 4，总和 = 32

=> 答案为 4（提款金额为 32）。

执行：

// 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]))