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

Question

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

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

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

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

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

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

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;
            }
        }
    }