performance - Найдите наименьшее количество монет, которые могут внести любое изменение от 1 до 99 центов




algorithm (18)

Недавно я бросил вызов своему коллеге, чтобы написать алгоритм для решения этой проблемы:

Найдите наименьшее количество монет, которые могут внести любое изменение от 1 до 99 центов. Монеты могут быть только монеты (1), никели (5), десятины (10) и четверти (25), и вы должны иметь возможность делать каждое значение от 1 до 99 (с шагом в 1 цент) с использованием этих монет.

Однако я понял, что на самом деле я не знаю, как это сделать, не изучая всевозможные комбинации монет. Должен быть лучший способ решить эту проблему, но я не знаю, как будет вызываться общее название для этого типа алгоритма, и я не могу найти способ упростить его, не смотря на каждое решение.

Мне было интересно, может ли кто-нибудь указать мне в правильном направлении или предложить алгоритм, который более эффективен.


В общем, если у вас есть ваши монеты COIN [] и ваш «диапазон изменения» 1..MAX, следующее должно найти максимальное количество монет.

Initialise array CHANGEVAL[MAX] to -1

For each element coin in COIN:
  set CHANGEVAL[coin] to 1
Until there are no more -1 in CHANGEVAL:
  For each index I over CHANGEVAL:
    if CHANGEVAL[I] != -1:
      let coincount = CHANGEVAL[I]
      For each element coin in COIN:
        let sum = coin + I
        if (COINS[sum]=-1) OR ((coincount+1)<COINS[sum]):
          COINS[sum]=coincount+1

Я не знаю, требуется ли, строго говоря, проверка на минимальную монету во внутреннем условном выражении. Я бы подумал, что минимальная цепочка монетных дополнений окажется правильной, но лучше безопасной, чем жаль.


Вам нужно как минимум 4 пенни, так как вы хотите получить 4 как изменение, и вы можете сделать это только с грошами.

Не оптимально иметь более 4 пенни. Вместо 4 + x пенни вы можете иметь 4 пенни и x никеля - они охватывают по крайней мере один и тот же диапазон.

Итак, у вас ровно 4 пенни.

Вам нужно как минимум 1 никель, так как вы хотите получить 5 в качестве изменения.

Не оптимально иметь более 1 никеля. Вместо 1 + x никеля вы можете иметь 1 никель и x десятину - они занимают по крайней мере один и тот же диапазон.

Таким образом, у вас ровно 1 никель.

Вам нужно как минимум 2 дня, так как вы хотите получить 20.

Это означает, что у вас есть 4 пенни, 1 никель и не менее 2-х центов.

Если бы у вас было менее 10 монет, у вас было бы менее 3 кварталов. Но тогда максимальное возможное изменение, которое вы могли бы получить, используя все монеты, составляет 4 + 5 + 20 + 50 = 79, недостаточно.

Это означает, что у вас есть как минимум 10 монет. Ответ Томаса показывает, что на самом деле, если у вас есть 4 пенни, 1 никель, 2 кубика и 3 четверти, все хорошо.


Вот мое занятие. Интересно то, что нам нужно проверить мин монеты, необходимые для формирования до coin_with_max_value (25 в нашем случае) - только 1. После этого просто вычислите сумму этих минимальных монет. С этого момента нам просто нужно добавить определенное количество coin_with_max_value, чтобы сформировать любое число до общей стоимости, в зависимости от разницы общей стоимости и найденной суммы. Вот и все.

Таким образом, для значений, которые мы принимаем, разыгрываются миллионы монет для 24: [1, 2, 2, 5, 10, 10]. Нам просто нужно продолжать добавлять 25 монет за каждые 25 значений, превышающих 30 (сумма мин. Монет). Итоговый ответ за 99:
[1, 2, 2, 5, 10, 10, 25, 25, 25]
9

import itertools
import math


def ByCurrentCoins(val, coins):
  for i in range(1, len(coins) + 1):
    combinations = itertools.combinations(coins, i)
    for combination in combinations:
      if sum(combination) == val:
        return True

  return False

def ExtraCoin(val, all_coins, curr_coins):
  for c in all_coins:
    if ByCurrentCoins(val, curr_coins + [c]):
      return c

def main():
  cost = 99
  coins = sorted([1, 2, 5, 10, 25], reverse=True)
  max_coin = coins[0]

  curr_coins = []
  for c in range(1, min(max_coin, cost+1)):
    if ByCurrentCoins(c, curr_coins):
      continue

    extra_coin = ExtraCoin(c, coins, curr_coins)
    if not extra_coin:
      print -1
      return

    curr_coins.append(extra_coin)

  curr_sum = sum(curr_coins)
  if cost > curr_sum:
    extra_max_coins = int(math.ceil((cost - curr_sum)/float(max_coin)))
    curr_coins.extend([max_coin for _ in range(extra_max_coins)])

  print curr_coins
  print len(curr_coins)

Вот простая версия в Python.

#!/usr/bin/env python

required = []
coins = [25, 10, 5, 1]

t = []
for i in range(1, 100):
    while sum(t) != i:
        for c in coins:
            if sum(t) + c <= i:
                t.append(c)
                break
    for c in coins:
        while t.count(c) > required.count(c):
            required.append(c)
    del t[:]

print required

При запуске он выводит следующее на стандартный вывод.

[1, 1, 1, 1, 5, 10, 10, 25, 25, 25]

Код довольно понятен (спасибо Python!), Но в основном алгоритм состоит в том, чтобы добавить самую крупную монету, которая не помещает вас в текущую сумму, которую вы снимаете, в свой временный список монет (t в этом случае ). Как только вы найдете наиболее эффективный набор монет для определенной суммы, убедитесь, что в требуемом списке есть по крайней мере одна часть каждой монеты. Сделайте это за каждый итог от 1 до 99 центов, и все готово.


Вы можете очень быстро найти верхнюю границу.

Скажем, вы берете три четверти. Тогда вам нужно будет заполнить «пробелы» 1-24, 26-49, 51-74, 76-99 другими монетами.

Тривиально, что будет работать с 2 копейками, 1 никелем и 4 пенни.

Таким образом, 3 + 4 + 2 + 1 должна быть верхней границей для вашего количества монет. Всякий раз, когда ваш алгоритм грубой силы выходит выше thta, вы можете мгновенно прекратить поиск в любом углублении.

Остальная часть поиска должна выполняться достаточно быстро для любых целей с динамическим программированием.

(править: фиксированный ответ согласно наблюдению Гейба)


Для этой проблемы жадный подход дает лучшее решение, чем DP или другие. Жадный подход: найдите наибольшее деноминацию, которое меньше требуемого значения, и добавьте его в набор монет, которые будут доставлены. Опустите требуемые центы только что добавленным номиналом и повторите, пока требуемые центы не станут равными нулю.

Мое решение (жадный подход) в Java-решении:

public class MinimumCoinDenomination {

    private static final int[] coinsDenominations = {1, 5, 10, 25, 50, 100};

    public static Map<Integer, Integer> giveCoins(int requiredCents) {
        if(requiredCents <= 0) {
            return null;
        }
        Map<Integer, Integer> denominations = new HashMap<Integer, Integer>();

        int dollar = requiredCents/100;
        if(dollar>0) {
            denominations.put(100, dollar);
        }
        requiredCents = requiredCents - (dollar * 100);

        //int sum = 0;
        while(requiredCents > 0) {
            for(int i = 1; i<coinsDenominations.length; i++) {
                if(requiredCents < coinsDenominations[i]) {
                    //sum = sum +coinsDenominations[i-1];
                    if(denominations.containsKey(coinsDenominations[i-1])) {
                        int c = denominations.get(coinsDenominations[i-1]);
                        denominations.put(coinsDenominations[i-1], c+1);
                    } else {
                        denominations.put(coinsDenominations[i-1], 1);
                    }
                    requiredCents = requiredCents - coinsDenominations[i-1];
                    break;
                }
            }
        }
        return denominations;
    }

    public static void main(String[] args) {
        System.out.println(giveCoins(199));
    }

}

Здесь идет мое решение, снова в Python и с использованием динамического программирования. Сначала я генерирую минимальную последовательность монет, необходимых для внесения изменений для каждой суммы в диапазоне 1.99, и из этого результата я нахожу максимальное количество монет, необходимых от каждого наименования:

def min_any_change():
    V, C = [1, 5, 10, 25], 99
    mxP, mxN, mxD, mxQ = 0, 0, 0, 0
    solution = min_change_table(V, C)
    for i in xrange(1, C+1):
        cP, cN, cD, cQ = 0, 0, 0, 0
        while i:
            coin = V[solution[i]]
            if coin == 1:
                cP += 1
            elif coin == 5:
                cN += 1
            elif coin == 10:
                cD += 1
            else:
                cQ += 1
            i -= coin
        if cP > mxP:
            mxP = cP
        if cN > mxN:
            mxN = cN
        if cD > mxD:
            mxD = cD
        if cQ > mxQ:
            mxQ = cQ
    return {'pennies':mxP, 'nickels':mxN, 'dimes':mxD, 'quarters':mxQ}

def min_change_table(V, C):
    m, n, minIdx = C+1, len(V), 0
    table, solution = [0] * m, [0] * m
    for i in xrange(1, m):
        minNum = float('inf')
        for j in xrange(n):
            if V[j] <= i and 1 + table[i - V[j]] < minNum:
                minNum = 1 + table[i - V[j]]
                minIdx = j
        table[i] = minNum
        solution[i] = minIdx
    return solution

Выполнение min_any_change() дает ответ, который мы искали: {'pennies': 4, 'nickels': 1, 'dimes': 2, 'quarters': 3} . В качестве теста мы можем попытаться удалить монету любого наименования и проверить, возможно ли еще внести изменения для любой суммы в диапазоне 1.99:

from itertools import combinations

def test(lst):
    sums = all_sums(lst)
    return all(i in sums for i in xrange(1, 100))

def all_sums(lst):
    combs = []
    for i in xrange(len(lst)+1):
        combs += combinations(lst, i)
    return set(sum(s) for s in combs)

Если мы проверим результат, полученный выше, получим True :

test([1, 1, 1, 1, 5, 10, 10, 25, 25, 25])

Но если мы удалим одну монету, независимо от того, какую деноминацию, мы получим False :

test([1, 1, 1, 5, 10, 10, 25, 25, 25])

Как я понял, если вы используете стандартные значения валютной системы, то его очень легко подсчитать минимальное количество монет только одним циклом. Просто всегда используйте максимальное значение монеты, и если это невозможно, проверьте следующую опцию. Но если у вас есть такая система, как у вас есть монеты, такие как 1,2,3,4, то она не работает. Я думаю, что вся идея иметь монеты как 1,2,5,10,25 - сделать вычисления легкими для людей.


Не сумев найти хорошее решение этой проблемы в PHP, я разработал эту функцию.

Он берет любую сумму денег (до $ 999,99) и возвращает массив минимального количества каждого купюры / монеты, необходимого для получения этого значения.

Сначала он преобразует значение в int в гроши (по какой-то причине я получаю ошибки в самом конце при использовании стандартных значений float).

Возвращенные наименования также находятся в грошах (т. Е. 5000 = 50, 100 = $ 1 и т. Д.).

function makeChange($val)
{
    $amountOfMoney = intval($val*100);
    $cashInPennies = array(10000,5000,2000,1000,500,100,25,10,5,1);
    $outputArray = array();
    $currentSum = 0;
    $currentDenom = 0;

    while ($currentSum < $amountOfMoney) {
        if( ( $currentSum + $cashInPennies[$currentDenom] ) <= $amountOfMoney  ) {
            $currentSum = $currentSum + $cashInPennies[$currentDenom];
            $outputArray[$cashInPennies[$currentDenom]]++;
        } else {
            $currentDenom++;
        }
    }

    return $outputArray;

}

$change = 56.93;
$output = makeChange($change);

print_r($output);
echo "<br>Total number of bills & coins: ".array_sum($output);

=== OUTPUT ===

Array ( [5000] => 1 [500] => 1 [100] => 1 [25] => 3 [10] => 1 [5] => 1 [1] => 3 ) 
Total number of bills & coins: 11

Предполагая, что вы говорите об американской валюте, вам нужен алгоритм Greedy: http://en.wikipedia.org/wiki/Greedy_algorithm

По сути, вы пробуйте все наименования от наивысшего до самого низкого, беря столько монет, сколько возможно от каждого, пока у вас ничего не останется.

В общем случае см. http://en.wikipedia.org/wiki/Change-making_problem , потому что вы хотели бы использовать динамическое программирование или линейное программирование, чтобы найти ответ для произвольных деноминаций, где жадный алгоритм не работал.


Сегодня я изучаю динамическое программирование , и вот результат:

coins = [1,5,10,25]
d = {} # stores tuples of the form (# of coins, [coin list])

# finds the minimum # of coins needed to
# make change for some number of cents
def m(cents):
    if cents in d.keys():
        return d[cents]
    elif cents > 0:
        choices = [(m(cents - x)[0] + 1, m(cents - x)[1] + [x]) for x in coins if cents >= x]

        # given a list of tuples, python's min function
        # uses the first element of each tuple for comparison
        d[cents] = min(choices)
        return d[cents]
    else:
        d[0] = (0, [])
        return d[0]

for x in range(1, 100):
    val = m(x)
    print x, "cents requires", val[0], "coins:", val[1]

Динамическое программирование действительно волшебное.


Хороший вопрос. Это логика, с которой я столкнулся. Протестировано с несколькими сценариями, включая 25.

class Program
{

    //Allowable denominations
    const int penny = 1;
    const int nickel = 5;
    const int dime = 10;
    const int quarter = 25;

    const int maxCurrencyLevelForTest =55; //1-n where n<=99

    static void Main(string[] args)
    {         
        int minPenniesNeeded = 0;
        int minNickelsNeeded = 0; 
        int minDimesNeeded = 0; 
        int minQuartersNeeded = 0;


        if (maxCurrencyLevelForTest == penny)
        {
            minPenniesNeeded = 1;
        }
        else if (maxCurrencyLevelForTest < nickel)
        {
            minPenniesNeeded = MinCountNeeded(penny, maxCurrencyLevelForTest);                
        }
        else if (maxCurrencyLevelForTest < dime)
        {
            minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
            minNickelsNeeded = MinCountNeeded(nickel, maxCurrencyLevelForTest);                
        }
        else if (maxCurrencyLevelForTest < quarter)
        {
            minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
            minNickelsNeeded = MinCountNeeded(nickel, dime - 1);
            minDimesNeeded = MinCountNeeded(dime, maxCurrencyLevelForTest);
        }
        else
        {
            minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
            minNickelsNeeded = MinCountNeeded(nickel, dime - 1);
            minDimesNeeded = MinCountNeeded(dime, quarter - 1);

            var maxPossilbleValueWithoutQuarters = (minPenniesNeeded * penny + minNickelsNeeded * nickel + minDimesNeeded * dime);
            if (maxCurrencyLevelForTest > maxPossilbleValueWithoutQuarters)
            {               
                minQuartersNeeded = (((maxCurrencyLevelForTest - maxPossilbleValueWithoutQuarters)-1) / quarter) + 1;
            }
        }


        var minCoinsNeeded = minPenniesNeeded + minNickelsNeeded+minDimesNeeded+minQuartersNeeded;

        Console.WriteLine(String.Format("Min Number of coins needed: {0}", minCoinsNeeded));
        Console.WriteLine(String.Format("Penny: {0} needed", minPenniesNeeded));
        Console.WriteLine(String.Format("Nickels: {0} needed", minNickelsNeeded));
        Console.WriteLine(String.Format("Dimes: {0} needed", minDimesNeeded));
        Console.WriteLine(String.Format("Quarters: {0} needed", minQuartersNeeded));
        Console.ReadLine();
    }

    private static int MinCountNeeded(int denomination, int upperRange)
    {
        int remainder;
        return System.Math.DivRem(upperRange, denomination,out remainder);
    }
}

Некоторые результаты: когда maxCurrencyLevelForTest = 25

Min Number of coins needed: 7
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 0 needed

Когда maxCurrencyLevelForTest = 99

Min Number of coins needed: 10
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 3 needed

maxCurrencyLevelForTest: 54

Min Number of coins needed: 8
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 1 needed

maxCurrencyLevelForTest: 55

Min Number of coins needed: 9
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 2 needed

maxCurrencyLevelForTest: 79

Min Number of coins needed: 9
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 2 needed

maxCurrencyLevelForTest: 85

Min Number of coins needed: 10
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 3 needed

Думаю, код может быть реорганизован.


Я написал этот алгоритм для аналогичной проблемы с DP, может ли это помочь

public class MinimumCoinProblem {

    private static void calculateMinumCoins(int[] array_Coins, int sum) {

        int[] array_best = new int[sum];

        for (int i = 0; i < sum; i++) {
            for (int j = 0; j < array_Coins.length; j++) {
                    if (array_Coins[j] <= i  && (array_best[i] == 0 || (array_best[i - array_Coins[j]] + 1) <= array_best[i])) {
                        array_best[i] = array_best[i - array_Coins[j]] + 1;
                    }
            }
        }
        System.err.println("The Value is" + array_best[14]);

    }


    public static void main(String[] args) {
        int[] sequence1 = {11, 9,1, 3, 5,2 ,20};
        int sum = 30;
        calculateMinumCoins(sequence1, sum);
    }

}

Изменить: как отмечали комментаторы, я неправильно истолковал вопрос. (Вопрос очень похож на базовую проблему CS, которую я вижу, когда студенты в колледже должны решить ...) wave hand Это не тот ответ, который вы ищете. Тем не менее, хотя исходный ответ неверен, мы можем использовать его как ступеньку для решения O ( n ).

Итак, возьмите неверный ответ ниже, который разрешает только одно значение (т. Е. Минимальную монету, требуемую для 68 центов), и просто запускайте ее для каждого значения.

changes = []
for amount in xrange(1, 100): # [1, 99]
    changes.append( run_the_algo_below( amount ) )
# Take the maximum for each coin type.
# ie, if run_the_algo_below returns (q, d, n, p):
change = [0, 0, 0, 0]
for c in changes:
    change = [max(c[i], change[i] for i in xrange(0, 4)]

Теперь это, безусловно, даст вам верный ответ, но это минимальный ответ? (это сложнее. В настоящее время моя кишка говорит «да», но я все еще думаю об этом ...)

( Неправильный ответ )

Вау. Loops? Динамическое программирование? Неужели люди?

В Python:

amount = ( your_amount_in_cents )

quarters = amount // 25
dimes = amount % 25 // 10
nickels = amount % 25 % 10 // 5
pennies = amount % 25 % 10 % 5

Вероятно, некоторые из этих модульных операций могут быть упрощены ...

Это не сложно, вам просто нужно подумать о том, как вы делаете изменения в реальной жизни. Вы отдаете четверти, пока добавление другой четверти не поставит вас на нужную сумму, вы дадите десятину до тех пор, пока добавление другой копейки не поставит вас на нужную сумму и так далее. Затем преобразуйте в математические операции: по модулю и делению. То же решение применяется для долларов, конвертируя секунды в ЧЧ: ММ: СС и т. Д.


Here's a simple c# solution using Linq.

internal class Program
{
    public static IEnumerable<Coin> Coins = new List<Coin>
    {
        new Coin {Name = "Dime", Value = 10},
        new Coin {Name = "Penny", Value = 1},
        new Coin {Name = "Nickel", Value = 5},
        new Coin {Name = "Quarter", Value = 25}
    };
    private static void Main(string[] args)
    {
        PrintChange(34);
        Console.ReadKey();
    }
    public static void PrintChange(int amount)
    {
        decimal remaining = amount;
        //Order coins by value in descending order
        var coinsDescending = Coins.OrderByDescending(v => v.Value);
        foreach (var coin in coinsDescending)
        {
            //Continue to smaller coin when current is larger than remainder
            if (remaining < coin.Value) continue;
            // Get # of coins that fit in remaining amount
            var quotient = (int)(remaining / coin.Value);

            Console.WriteLine(new string('-',28));
            Console.WriteLine("{0,10}{1,15}", coin.Name, quotient);
            //Subtract fitting coins from remaining amount
            remaining -= quotient * coin.Value;
            if (remaining <= 0) break; //Exit when no remainder left
        }
        Console.WriteLine(new string('-', 28));
    }
    public class Coin
    {
        public string Name { get; set; }
        public int Value { get; set; }
    }
}    

Inspired from this https://www.youtube.com/watch?v=GafjS0FfAC0 following
1) optimal sub problem 2) Overlapping sub problem principles introduced in the video

using System;
using System.Collections.Generic;
using System.Linq;

namespace UnitTests.moneyChange
{
    public class MoneyChangeCalc
    {
        private static int[] _coinTypes;

        private Dictionary<int, int> _solutions;

        public MoneyChangeCalc(int[] coinTypes)
        {
            _coinTypes = coinTypes;
            Reset();
        }

        public int Minimun(int amount)
        {
            for (int i = 2; i <= amount; i++)
            {
                IList<int> candidates = FulfillCandidates(i);

                try
                {
                    _solutions.Add(i, candidates.Any() ? (candidates.Min() + 1) : 0);
                }
                catch (ArgumentException)
                {
                    Console.WriteLine("key [{0}] = {1} already added", i, _solutions[i]);
                }
            }

            int minimun2;
            _solutions.TryGetValue(amount, out minimun2);

            return minimun2;
        }

        internal IList<int> FulfillCandidates(int amount)
        {
            IList<int> candidates = new List<int>(3);
            foreach (int coinType in _coinTypes)
            {
                int sub = amount - coinType;
                if (sub < 0) continue;

                int candidate;
                if (_solutions.TryGetValue(sub, out candidate))
                    candidates.Add(candidate);
            }
            return candidates;
        }

        private void Reset()
        {
            _solutions = new Dictionary<int, int>
                {
                    {0,0}, {_coinTypes[0] ,1}
                };
        }
    }
}

Тестовые случаи:

using NUnit.Framework;
using System.Collections;

namespace UnitTests.moneyChange
{
    [TestFixture]
    public class MoneyChangeTest
    {
        [TestCaseSource("TestCasesData")]
        public int Test_minimun2(int amount, int[] coinTypes)
        {
            var moneyChangeCalc = new MoneyChangeCalc(coinTypes);
            return moneyChangeCalc.Minimun(amount);
        }

        private static IEnumerable TestCasesData
        {
            get
            {
                yield return new TestCaseData(6, new[] { 1, 3, 4 }).Returns(2);
                yield return new TestCaseData(3, new[] { 2, 4, 6 }).Returns(0);
                yield return new TestCaseData(10, new[] { 1, 3, 4 }).Returns(3);
                yield return new TestCaseData(100, new[] { 1, 5, 10, 20 }).Returns(5);
            }
        }
    }
}

There are a couple of similar answers up there but my solution with Java seems a little easier to understand. Check this out.

public static int findMinimumNumberOfCoins(int inputCents) {

     // Error Check, If the input is 0 or lower, return 0.
     if(inputCents <= 0) return 0;

     // Create the List of Coins that We need to loop through. Start from highest to lowewst.
     // 25-10-5-1
     int[] mCoinsArray = getCoinsArray();

     // Number of Total Coins.
     int totalNumberOfCoins = 0;

     for(int i=0; i < mCoinsArray.length; i++) {

         // Get the Coin from Array.
         int coin = mCoinsArray[i];

         // If there is no inputCoin Left, simply break the for-loop
         if(inputCents == 0) break;

         // Check If we have a smaller input than our coin
         // If it's, we need to go the Next one in our Coins Array.
         // e.g, if we have 8, but the current index of array is 10, we need to go to 5.
         if(inputCents < coin) continue;

         int quotient = inputCents/coin;
         int remainder = inputCents%coin;

         // Add qutient to number of total coins.
         totalNumberOfCoins += quotient;

         // Update the input with Remainder.
         inputCents = remainder;
     }

     return totalNumberOfCoins;
 }

 // Create a Coins Array, from 25 to 1. Highest is first.
 public static int[] getCoinsArray() {

     int[] mCoinsArray = new int[4];
     mCoinsArray[0] = 25;
     mCoinsArray[1] = 10;
     mCoinsArray[2] = 5;
     mCoinsArray[3] = 1;

     return mCoinsArray;
 }

This the code in c# to find the solution.

public struct CoinCount
{
    public int coinValue;
    public int noOfCoins;
}

/// <summary>
/// Find and returns the no of coins in each coins in coinSet
/// </summary>
/// <param name="coinSet">sorted coins value in assending order</param>
/// <returns></returns>
public CoinCount[] FindCoinsCountFor1to99Collection(int[] coinSet)
{
    // Add extra coin value 100 in the coin set. Since it need to find the collection upto 99.
    CoinCount[] result = new CoinCount[coinSet.Length];
    List<int> coinValues = new List<int>();
    coinValues.AddRange(coinSet);
    coinValues.Add(100);

    // Selected coin total values
    int totalCount = 0;
    for (int i = 0; i < coinValues.Count - 1; i++)
    {
        int count = 0;
        if (totalCount <= coinValues[i])
        {
            // Find the coins count
            int remainValue = coinValues[i + 1] - totalCount;
            count = (int)Math.Ceiling((remainValue * 1.0) / coinValues[i]);
        }
        else
        {
            if (totalCount <= coinValues[i + 1])
                count = 1;
            else
                count = 0;
        }
        result[i] = new CoinCount() { coinValue =  coinValues[i], noOfCoins = count };
        totalCount += coinValues[i] * count;
    }
    return result;
}




algorithm