algorithm - COLCOIN - 收集硬币

Question

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

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

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

这是我的想法:

尝试将较小面额的值(value)相加，看看它们是否可以加起来成为较大面额的值(value)，如果是，您将永远无法获得所有较小面额的值(value)。

例如:假设有 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，除了 26 之外只有 2 个面额会给出 4 个面额 19+4+2+1

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