КОЛКОИН - Коллекционирование монет - PullRequest
Новая
       9

КОЛКОИН - Коллекционирование монет

1 голос
/ 30 мая 2019

Я решаю эту проблему - КОЛКОЙН - Сбор монет на спой. ссылка- 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 </p>

другое: допустим, есть деноминации 3,4 и 5. Итак, 3 + 4> 5, поэтому мы никогда не сможем получить все деноминации. потому что деньги будут выдаваться номиналом 5, пока деньги, которые нужно отдать, не станут меньше 5. и, очевидно, вы не можете получить 3 + 4 = 7 рупий за что-то менее 5

Еще одна идея, которая явно неверна, - начать со 2-й наивысшей купюры и найти монеты, которые мы добавим к этому, и вернуть это решение + 1 (наивысшая номинал). это неверно, потому что, например, [1,2,4,17,19], если мы считаем уже 19, пытаясь суммировать другие за 18, мы получаем 1 + 17, только 2 номинала, кроме, где как 26 дал бы 4 купюры 19 + 4 + 2 + 1

1 Ответ

0 голосов
/ 30 мая 2019

Я думаю, что вы можете использовать следующий подход:

  1. Начните с наименьшего номинала
  2. Проверьте, превышает ли добавление следующего наименьшего номинала номинал после этого
    1. Если сумма меньше, добавьте деноминацию к сумме
    2. , в противном случае продолжайте и проверьте, не превышает ли деноминация еще один шаг после деноминации.

Пример: 1 3 6 8 15 20

  1. разные номиналы d = 1, сумма = 1
  2. 1 + 3 <6: d = 2, сумма = 4 </li>
  3. 4 + 6> = 8: d = 2, сумма = 4
  4. 4 + 8 <15: d = 3, сумма = 12 </li>
  5. 12 + 15> = 20: d= 3, сумма = 12
  6. 12 + 20 <бесконечность: d = 4, сумма = 32 </li>

=> ответ равен 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]))
...