Fogbugz定价方案的算法

Question

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

Fogbugz的定价是:

• 1份许可证$ 299
• 5个许可证包999美元
• 10个许可证包$ 1,899
• 20个许可证包$ 3,499
• 50个许可证包$ 7,999

如果你问一个让我们说136个许可证的报价,他们会把它计算为22,694美元.

如何在C#或LINQ中执行此操作？

任何帮助将不胜感激.

Answer 1

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 2

虽然从程序员的角度来看,优雅的代码片段并不能为客户提供最优惠的价格,但从客户的角度来看,这可能并不是一个优雅的解决方案.例如,当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

更新生成细分有点复杂,但我绝对认为这对您的客户有利.您可以这样做(假设打印到控制台,虽然真正的程序可能会输出到网页):

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