How to convert a number to a range of prices

Question

I want to calculate the amount to charge my customers, when they buy licenses of my product.

I sell it in ranges of licenses:

• 1-10 : $50/user
• 11-20 : $40/user
• 21-30 : $30/user
• 31-50 : $20/user

So when someone purchases 136 licenses, I will charge him:

50 x 2 x $20 = $2000
30 x 1 x $30 = $900
     6 x $50 = $300

I'm looking for an algorithm on how to process the given number and break it into number of occurrences in a range.. How can I do this in plain C# or LINQ?

------------ EDIT ----------------------------

I started a less confusing question (http://stackoverflow.com/questions/2685391/algorithm-for-fogbugz-pricing-scheme) and I got the answer I've been looking for.

Thank you all..

Answer 1

A KeyValuePair collection or dictionary maybe?

Answer 2

This looks like it would be very similar to algorithms that make change for purchases (which coins to choose). The only difference is that you're comparing against a range instead of a single number.

The code could look something like this:

var val = 136;
var price = 0;
while (val > 0) 
{
  var range = FindMatchingRange(val); // Use a dictionary, list, or array.
  var number = Math.Min(val, range.Max);
  price += range.CostPerUser * number;
  val -= number;
}

Answer 3

If presented with this price structure I would think that it is in the customer's best interest to minimize the cost by buying the package that best suits their need. The following algorithm uses dynamic programming to calculate the minimal possible price to exactly buy a certain number of licenses (you can save money by buying more than you need, although I haven't implemented that):

int getPrice(int n)
{
    if (n >= 1 && n <= 10) return 50 * n;
    if (n >= 11 && n <= 20) return 40 * n;
    if (n >= 21 && n <= 30) return 30 * n;
    if (n >= 31 && n <= 50) return 20 * n;
    throw new Exception("Impossible");
}

int minimizePrice(int n)
{
    int[] minimumPrice = new int[n + 1];
    for (int i = 1; i <= n; ++i)
    {
        minimumPrice[i] = int.MaxValue;
        for (int j = Math.Max(0, i - 50); j < i; ++j)
        {
            minimumPrice[i] = Math.Min(minimumPrice[i],
                minimumPrice[j] + getPrice(i - j));
        }
    }
    return minimumPrice[n];
}

For 70 licenses the minimal price is $1400 which can be obtained by buying 2 blocks of 35 licenses. You are suggesting a greedy algorithm. This will confuse your customers. A clever customer will place two orders instead of one large order and save $400.

I'd suggest changing your prices so that there is no upper limit to the number of licenses you can buy at $20 each.

Answer 4

If I were a person who needed 10 licenses, under your suggested pricing plan why would I ever buy just 10 licenses?

10 licenses * $50/license = $500

11 licenses * $40/license = $440

What you would want is plan that lowers the cost for the most recently purchased licenses. So that for person wanting 11 licenses they would pay:

(10 licenses * $50/license) + (1 license * $40/license) = $540

A possible plan would look like this:

first 10 licenses (1-10): $50/user
next 10 licenses (11-20): $40/user
next 10 licenses (21-30): $30/user
all licenses after that (31+) : $20/user

Writing code to compute final cost for any number of users is a simple exercise. The calculation for someone purchasing 136 licenses would look like this:

(10 licenses * $50/license) + (10 licenses * $40/license) + (10 licenses * $30/license) + (106 licenses * $20/license) = $500 + $400 + $300 + $2120 = $3,220.

The original pricing plan is wacky, in my opinion. Take the customer who purchased 130 licenses last year who comes back and wants 10 more. What justification is there for charging them the highest rate? They are a high volume customer, you want to sell them (and they justifiably expect to receive) additional licenses at the lowest "marginal" price.

Answer 5

I made a calculation class for you... just more customer-orientated. It calculates the cheapest price possible with your defined priceranges.

Example: 136 Licenses

50 Licenses 20$ each ( because: 31-50 : $20/user )

50 Licenses 20$ each ( because: 31-50 : $20/user )

36 Licenses 20$ each ( because: 31-50 : $20/user )

TOTAL: 1720

---

Example 130 Licenses

50 Licenses 20$ each

50 Licenses 20$ each

30 Licenses 30$ each

TOTAL: 1900

---

Code for the class:

   public class PriceCalculator
    {
        public List<OrderPackage> CalculateCheapestPrice(Int32 AmountOfLicenses, 
            List<PriceRange> PriceRanges, out Double Total)
        {
            List<OrderPackage> result = new List<OrderPackage>();
            Total = 0;

            Int32 AmountsOfLicensesleft = AmountOfLicenses;

            PriceRanges.Sort(ComparePrice);

            for (int i = 0; i < PriceRanges.Count; i++)
            {
                for (int j = PriceRanges[i].MaxAmount; j >= PriceRanges[i].MinAmount; j--)
                {
                    if (j <= AmountsOfLicensesleft)
                    {
                        OrderPackage Order = new OrderPackage();
                        Int32 AmountOfThisPackage = AmountsOfLicensesleft / j;
                        //Int32 AmountForThisPrice = Convert.ToInt32(Math.Floor(tmp));

                        Order.PriceRange = PriceRanges[i];
                        Order.AmountOfLicenses = j;

                        Total += Order.AmountOfLicenses * Order.PriceRange.PricePerLicense;

                        for (int k = 0; k < AmountOfThisPackage; k++)
                        {
                            result.Add(Order);
                        }

                        AmountsOfLicensesleft = AmountsOfLicensesleft - (AmountOfThisPackage * j);
                    }
                }
            }

            return result;
        }

        private static int ComparePrice(PriceRange x, PriceRange y)
        {
            if (x.PricePerLicense == y.PricePerLicense)
                return 0;

            if (x.PricePerLicense > y.PricePerLicense)
                return 1;

            if (x.PricePerLicense < y.PricePerLicense)
                return -1;

            return 0;
        }

        public class OrderPackage
        {
            public PriceRange PriceRange { get; set; }
            public Int32 AmountOfLicenses { get; set; }
        }

        public class PriceRange
        {
            public int MinAmount { get; set; }
            public int MaxAmount { get; set; }

            public Double PricePerLicense { get; set; }
        }
    }

Usage example:

private void button1_Click(object sender, EventArgs e)
{
    // Preparing PriceRangeDefinitions
    List<PriceCalculator.PriceRange> PriceRangeDefinitions = new List<PriceCalculator.PriceRange>();
    PriceRangeDefinitions.Add(new PriceCalculator.PriceRange() { MinAmount = 1, MaxAmount = 10, PricePerLicense = 50 });
    PriceRangeDefinitions.Add(new PriceCalculator.PriceRange() { MinAmount = 11, MaxAmount = 20, PricePerLicense = 40 });
    PriceRangeDefinitions.Add(new PriceCalculator.PriceRange() { MinAmount = 21, MaxAmount = 30, PricePerLicense = 30 });
    PriceRangeDefinitions.Add(new PriceCalculator.PriceRange() { MinAmount = 31, MaxAmount = 50, PricePerLicense = 20 });

    // Start the Calculation
    PriceCalculator calculator = new PriceCalculator();
    Double Total;
    List<PriceCalculator.OrderPackage> Packages =
        calculator.CalculateCheapestPrice(130, PriceRangeDefinitions, out Total);

    // Show Proof of Concept
    String ProofOfConcept = String.Empty;
    for (int i = 0; i < Packages.Count; i++)
    {
        ProofOfConcept += Packages[i].AmountOfLicenses.ToString() + " Licenses " +
            Packages[i].PriceRange.PricePerLicense.ToString() + "$ each" + Environment.NewLine;
    }
    ProofOfConcept += Environment.NewLine + "TOTAL: " + Total.ToString();

    MessageBox.Show(ProofOfConcept);
}