C # Вычислить деноминацию в долларах

Question

Вот код, чтобы найти общее количество способов получить 87 с 4 различными счетами.Мне интересно, как изменить это, чтобы получить наименьшее количество счетов (4-х, 1-пять, 2-х) вместо каждого в отдельности.Любая помощь будет оценена.

int target = 87;
int[] dollarSizes = { 1, 5, 10, 20 };
int[] ways = new int[target+1];
ways[0] = 1;

for (int i = 0; i < dollarSizes.Length; i++) {
    for (int j = dollarSizes[i]; j <= target; j++) {
        ways[j] += ways[j - dollarSizes[i]];
    }
}

Answer 1

Действительно, вы хотите отслеживать, как быстро вы можете добраться до цели.Таким образом, с учетом 20,10,5,1 наименований код выглядит следующим образом: psuedo

int initial = 87;             initial  twenties  tens   fives   ones
int twenties = initial / 20;    87        4
initial = initial % 20;          7        4    
int tens = initial / 10;         7        4       0
initial = initial % 10;          7        4       0
int fives = initial / 5;         7        4       0       1
initial = initial % 5;           2        4       0       1
int ones = initial;              2        4       0       1       2

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

Answer 2

        int target = 87;
        int[] dollarSizes = { 100, 20, 10, 5, 1 };
        int[] counts = { 0, 0, 0, 0, 0 };

        int remainder = target;
        int bill = 0;
        while (remainder > 0)
        {
            counts[bill] = remainder / dollarSizes[bill];
            remainder -= counts[bill] * dollarSizes[bill];
            bill++;
        }

Answer 3

public static int MakeChange(int amount)
{
    if (amount < 0)
        throw new ArgumentOutOfRangeException("Amount should be greater than 0.");

    int[] availableBills = { 20, 10, 5, 1 };
    int[] availableBillCounts = { 0, 0, 0, 0 };
    int iterator = 0;
    int reminder = amount;

    while (reminder > 0)
    {
        availableBillCounts[iterator] = reminder / availableBills[iterator];
        reminder = amount % availableBills[iterator];
        iterator++;
    }

    return availableBillCounts.Sum();
}

Answer 4

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

class Program
{
    static void Main(string[] args)
    {
        var target = 87;
        var current = 0;
        var dollarSizes = new[] { 1, 5, 10, 20 }.OrderByDescending(x => x); // just make sure they're descending.
        var bestWay = new List<int>();

        foreach (var dollarSize in dollarSizes)
        {
            while (current + dollarSize <= target)
            {
                current += dollarSize;
                bestWay.Add(dollarSize);
            }

            if (current == target)
                break;
        }

        foreach (var dollar in bestWay)
        {
            Console.Write("{0}, ", dollar);
        }

        Console.ReadLine();
    }
}