Algorithm for Fogbugz pricing scheme

I'm looking for an algorithm to calculate total cost of licenses purchased based on the "FogBugz for your server" pricing scheme (http://www.fogcreek.com/FogBugz/PriceList.html).

Fogbugz pricing is开发者_运维问答:

• 1 License $299
• 5 License Pack $999
• 10 License Pack $1,899
• 20 License Pack $3,499
• 50 License Pack $7,999

If you ask a quote for let's say 136 licenses they calculate it as $22,694.

How can I do this in C# or LINQ?

Any help will be appreciated.

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

or

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

The accepted answer, whilst an elegant piece of code from a programmer's point of view, does not give the best possible price for the customer and therefore might not be an elegant solution from the customer's point of view. For example when n = 4, the accepted answer gives $1196, but a customer would obviously prefer to choose the 5 license pack and pay just $999 instead.

It is possible to construct an algorithm which can calculate the minimum price possible that the customer can pay to purchase their required number of licenses. One way of doing this is to use dynamic programming. I think something like this might do the trick:

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

Output:

22694
999

Update Producing a breakdown is a little more complicated, but I definitely think it will be beneficial for your customers. You could do it something like this (assuming printing to the console, although a real program would probably output to a web page):

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

Output:

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

Mark's solution is a great general solution, and definitely what you should go with (in case prices ever change.) This solution combines the simplicity of dtb's with the correctness of the Mark's:

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;

It looks like the only edge cases are 5 is better than 4, and 50 is better than 46...49. Although, realistically, you should probably suggest 50 when someone looks for 45, since the extra 5 licenses only cost $2. So, maybe chnage 46 to 45 in the code.