Min-Coin change - лучшее решение для ограниченного набора

Question

Некоторое время назад я читал о проблеме изменения минимальных монет и хочу реализовать ее для гипотетического автомата.

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

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

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

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

Это мой первый вопрос, и я надеюсь, что он поможет кому-то в будущем.

Answer 1

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

    protected void CalculateCoins(int sum)
    {
        int remainder = sum;
        int required = 0;

        // Array of coins should be sorted by value of coins
        CoinQnt[] normalizedCoins = new CoinQnt[]
        {
            new CoinQnt { Value = 50, Qnt = 1 }
            , new CoinQnt { Value = 20, Qnt = 100 }
            , new CoinQnt { Value = 10, Qnt = 100 }
            , new CoinQnt { Value = 5, Qnt = 100 }
            , new CoinQnt { Value = 2, Qnt = 100 }
            , new CoinQnt { Value = 1, Qnt = 100 }
        };

        Debug("Splitting {0}", sum);
        // Loop through available coins
        foreach( CoinQnt c in normalizedCoins )
        {
            if( remainder >= c.Value )
            {
                // Determine how many coins we need and how many are left
                required = Math.Min(remainder / c.Value, c.Qnt);
                Debug("Using {0} qnt of {1}", required, c.Value);
                remainder -= required * c.Value;
            }
        }
    }