Fogbugz定价方案的算法

Question

我正在寻找一种算法来计算基于"FogBugz for your“定价方案(http://www.fogcreek.com/FogBugz/PriceList.html)购买的许可证的总成本。

Fogbugz的定价是：

• 1许可证$299
• 5许可证包$999
• 10许可证包$1,899
• 20许可证包$3,499

H 11050许可证包$7,999H 211F 212

如果你想要一个报价，比如说136个许可证，他们就会把它算成22,694美元。

如何在C#或LINQ中做到这一点？

任何帮助都将不胜感激。

Answer 1

接受的答案，虽然从程序员的角度来看是一段优雅的代码，但并没有为客户提供尽可能好的价格，因此，从客户的角度来看，可能不是一个优雅的解决方案。例如，当n= 4时，接受的答案是1196美元，但客户显然更喜欢选择5许可证包，而只支付999美元。

可以构造一种算法，该算法可以计算客户购买所需数量的许可证时可能支付的最低价格。其中一种方法是使用动态规划。我想像这样的东西可能会起作用：

int calculatePrice(int n, Dictionary<int, int> prices)
{

    int[] best = new int[n + prices.Keys.Max()];
    for (int i = 1; i < best.Length; ++i)
    {
        best[i] = int.MaxValue;
        foreach (int amount in prices.Keys.Where(x => x <= i))
        {
            best[i] = Math.Min(best[i],
                best[i - amount] + prices[amount]);
        }
    }
    return best.Skip(n).Min();
}

void Run()
{
    Dictionary<int, int> prices = new Dictionary<int, int> {
        { 1, 299 },
        { 5, 999 },
        { 10, 1899 },
        { 20, 3499 },
        { 50, 7999 }
    };

    Console.WriteLine(calculatePrice(136, prices));
    Console.WriteLine(calculatePrice(4, prices));
}

输出：

22694
999

生成故障的Update要复杂一些，但我肯定会对您的客户有好处。您可以这样做(假设打印到控制台，虽然一个真正的程序可能会输出到一个网页)：

using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static Dictionary<int, int> prices = new Dictionary<int, int> {
            { 1, 299 },
            { 5, 999 },
            { 10, 1899 },
            { 20, 3499 },
            { 50, 7999 }
    };

    class Bundle
    {
        public int Price;
        public Dictionary<int, int> Licenses;
    }

    Bundle getBestBundle(int n, Dictionary<int, int> prices)
    {
        Bundle[] best = new Bundle[n + prices.Keys.Max()];
        best[0] = new Bundle
        {
            Price = 0,
            Licenses = new Dictionary<int, int>()
        };

        for (int i = 1; i < best.Length; ++i)
        {
            best[i] = null;
            foreach (int amount in prices.Keys.Where(x => x <= i))
            {
                Bundle bundle = new Bundle
                {
                     Price = best[i - amount].Price + prices[amount],
                     Licenses = new Dictionary<int,int>(best[i - amount].Licenses)
                };

                int count = 0;
                bundle.Licenses.TryGetValue(amount, out count);
                bundle.Licenses[amount] = count + 1;

                if (best[i] == null || best[i].Price > bundle.Price)
                {
                    best[i] = bundle;
                }
            }
        }
        return best.Skip(n).OrderBy(x => x.Price).First();
    }

    void printBreakdown(Bundle bundle)
    {
        foreach (var kvp in bundle.Licenses) {
            Console.WriteLine("{0,2} * {1,2} {2,-5} @ ${3,4} = ${4,6}",
               kvp.Value,
                kvp.Key,
                kvp.Key == 1 ? "user" : "users",
                prices[kvp.Key],
                kvp.Value * prices[kvp.Key]);
        }

        int totalUsers = bundle.Licenses.Sum(kvp => kvp.Key * kvp.Value);

        Console.WriteLine("-------------------------------");
        Console.WriteLine("{0,7} {1,-5}           ${2,6}",
            totalUsers,
            totalUsers == 1 ? "user" : "users",
            bundle.Price);
    }

    void Run()
    {
        Console.WriteLine("n = 136");
        Console.WriteLine();
        printBreakdown(getBestBundle(136, prices));
        Console.WriteLine();
        Console.WriteLine();
        Console.WriteLine("n = 4");
        Console.WriteLine();
        printBreakdown(getBestBundle(4, prices));
    }

    static void Main(string[] args)
    {
        new Program().Run();
    }
}

输出：

n = 136

 2 * 50 users @ $7999 = $ 15998
 1 * 20 users @ $3499 = $  3499
 1 * 10 users @ $1899 = $  1899
 1 *  5 users @ $ 999 = $   999
 1 *  1 user  @ $ 299 = $   299
-------------------------------
    136 users           $ 22694


n = 4

 1 *  5 users @ $ 999 = $   999
-------------------------------
      5 users           $   999

Answer 2

int licenses = 136;
int sum = 0;

while (licenses > 0)
{
    if (licenses >= 50)      { sum += 7999; licenses -= 50; }
    else if (licenses >= 20) { sum += 3499; licenses -= 20; }
    else if (licenses >= 10) { sum += 1899; licenses -= 10; }
    else if (licenses >= 5)  { sum += 999;  licenses -= 5; }
    else                     { sum += 299;  licenses -= 1; }
}

// sum == 22694

或

int licenses = 136;
int sum = 7999 * Math.DivRem(licenses, 50, out licenses)
        + 3499 * Math.DivRem(licenses, 20, out licenses)
        + 1899 * Math.DivRem(licenses, 10, out licenses)
        +  999 * Math.DivRem(licenses,  5, out licenses)
        +  299 * licenses;

// sum == 22694

Answer 3

Mark的解决方案是一个很好的通用解决方案，而且肯定是您应该使用的(以防价格发生变化)。该解决方案结合了dtb的简单性和Mark的正确性：

int licenses = 136;
int sum = 7999 * Math.DivRem(licenses, 50, out licenses)
        + 7999 * Math.DivRem(licenses, 46, out licenses)
        + 3499 * Math.DivRem(licenses, 20, out licenses)
        + 1899 * Math.DivRem(licenses, 10, out licenses)
        +  999 * Math.DivRem(licenses,  5, out licenses)
        +  999 * Math.DivRem(licenses,  4, out licenses)
        +  299 * licenses;

看起来唯一的边缘情况是5好于4，50好于46.49。虽然，实际上，当有人找45的时候，你应该建议50，因为额外的5张许可证只需要2美元。所以，在代码中可能需要46到45。