计算美元面额

本文关键字：美元 计算 | 更新日期: 2023-09-27 17:49:45

这是一个代码，用于查找4种不同账单获得87的总方法。我想知道如何改变这一点，以获得最少的钞票(4- 20,1- 5,2- 1)，而不是每一种方式。如有任何帮助，不胜感激。

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

计算美元面额

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

你真正想追踪的是你能多快到达目标。给定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

正如你所看到的，有很多重复的逻辑，所以可以从一个循环中提供(我们从最大值开始)。

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

先用最高的数。如果新的金额太大，不要添加该账单，并继续到下一个美元大小:

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();
    }
}
相关文章：