C# 货币排列

Question

只是为了让大家知道，这是我第一次寻求有关堆栈溢出的帮助。我通常会搜索网站并找到满意的答案，或者在 MSDN 或其他网站上进一步挖掘。但这一次我被严重卡住了。

我收到招聘人员发来的一个编程问题，我必须完成该问题才能提交给客户，看看他们是否愿意邀请我。挑战如下：对于任何给定的值，确定该值可以用 100 美元面额表示的方式数， $50, $20, $10, $5, $1, .25, .10, .05, .01

我从未学过三角学或微积分，也从未在我的学习中遇到过如此复杂的数学问题 。 14 年编程经验。他们希望用 C# 找到答案，因为它是 Microsoft .NET 商店。

招聘人员给了我他提交的另一位候选人的代码。这个人一定是一位出色的数学家，因为她真正编写了整个算法以达到预期的结果。我把它插入到网页中，它确实满足了要求。问题是我什至无法弄清楚并以允许我编写自己的实现的方式理解它。

我真的非常想要这份工作，因为它是在纽约的一家初创公司，听起来很棒。我能够回答第二个问题，因为它是一个架构/设计问题，但这个问题让我感到困惑。

顺便说一句，我在维基百科上查找了硬币找零问题和背包型问题，这远远超出了我的数学技能。我什至无法阅读答案，因为我不懂微积分。所以我在这方面需要一些认真的帮助。

这是她的代码，顺便说一句，它确实有效：

protected void Page_Load(object sender, EventArgs e)
{
    var numberToSplit = new List<int>() {123};  
    foreach (int a in numberToSplit)
    {
        Response.Write(a + "  can be split in ");
        foreach (List<double> splits in GetDenominations(a).Values)
        {
            foreach (double b in splits)
            {
                Response.Write(b + ",");
            }
            //next split
            Response.Write("<br/>");
        }      
        Response.Write("<br/>");
    }
}

public Dictionary<double, List<double>> GetDenominations(int value)
{
    var denominations = new List<double> {100, 50, 20,10,5,1,0.25,0.10,0.05,0.01};
    var AllPossibleSplits = new Dictionary<double, List<double>>();
    var hightestdenomination = 100.0;

    while (hightestdenomination != 0)
    {
        var remainingDenominations =
                denominations.Where(a => (a <= value && !AllPossibleSplits.Keys.Contains(a)));

        if (remainingDenominations.Count() > 0)
            hightestdenomination = remainingDenominations.Max();
        else
            hightestdenomination = 0;

        var splits = new List<double>(); 

        if (hightestdenomination != 0)
        {
            int valueToSplit = value;
            while (valueToSplit > 0)
            {
                foreach (double denomination in remainingDenominations.Where(a => a <= valueToSplit))
                {
                    int absoluteValue = (int) (valueToSplit/denomination);
                    valueToSplit = valueToSplit - (int) (absoluteValue*denomination);
                    int absoluteValueSplit = 0;

                    while (absoluteValueSplit < absoluteValue)
                    {
                        splits.Add(denomination);
                        absoluteValueSplit++;
                    }
                }
           }   
        }

        AllPossibleSplits[hightestdenomination] = splits;
    }

    return AllPossibleSplits;
}

Answer 1

您可以将其视为树遍历问题：

在这里，您将遍历树并检查以下内容。

Is the cost of the path currently lower then what I want 
 -> Go deeper in the tree

Is the cost of the path currently higher then what I want 
 -> Stop

Is the cost of the path currently the same as what I want 
 -> Permutation found

下面是一个示例：您想要获得 25 美元、5 美元、10 美元和 20 美元钞票的所有可能排列。蓝色表示成本 25，红色表示成本> 25 绿色表示cost = 25

图像免责声明：也许其中有一些错误，但你明白了

另外，如果你这样做，它会给出像 5,5,5,10 <> 这样的排列。 10,5,5,10 因此，请保留您已有的解决方案的列表，这样您就不会得到这些倍数。此外，这棵树有一个有点大（有争议的）分支因子（10），所以如果你得到很大的数字，就有很多可能的选择。不要先创建整棵树然后遍历它。它可以加起来（我无法想象有多少种可能性可以赚到 1,000,000 美元）。

Answer 2

出色地，
发布的算法仅让您了解所有可能的排列，尝试使用值 1 它给出的答案如下：

• 1
• 0,25 , 0,25 , 0,25 , 0,25
• 0,1 , 0,1 , 0,1 , 0,1 , 0,1 , 0,1 , 0,1 , 0,1 , 0,1 , 0,1
  。
  。
  。

但这只是整个答案的一瞥，缺少答案，例如
0,25 , 0,25 , 0,1 , 0,1 , 0,1 , 0,1 , 0,1
仅举一例。
实现自己的算法是一个好方法。
我是一名计算科学的实习生，我可以在我的脑海中想到一种算法，虽然不那么复杂，但很有效。
在我之前发帖的人给出了一个很好的提示：
从最大可能的分裂到最小的可能分裂，计算出现的最大数量，然后以较小的数量继续，直到最终剩余 0 次。
要获得所有可能的解决方案，需要做更多的工作，但是您提供的解决方案给出了不同最大数量的解决方案。

Answer 3

您可能想看看贪婪算法。

Answer 4

虽然我觉得这是一次工作面试，你应该能够编写这段代码，但我更愿意推动你朝着正确的方向前进。
这是一个需要简单数学的经典编程任务，我将在下面进行解释。
想象一下每个教派都有 1 个，在现实生活中你会如何区分它们。
首先，您将每种面值堆成一堆，在本例中对应于一个变量，即 var HundredDollarNotes、var五十美元Notes，或者具有该效果属性的对象。

而您的金额不等于零。
减去 100 美元的金额，并将 1 加入到 HundredDollarNotes 变量中，重复此操作，直到无法减去 100 美元。
继续减少金额，直到没有剩余金额为止。

简而言之，就是贪婪算法。

Answer 5

不要让问题变得更困难。

假设您有 51 个硬币。使用您拥有的最大账单 (50) 51-50=1
然后使用你拥有的最大的硬币 (1) 1-1=1

就这样。

该代码只是遍历整个价值列表并使用可能的最大钞票/面额，并对剩下的任何内容执行相同的操作，直到什么都没有剩下。