Алгоритм для схемы оценки Fogbugz
Я ищу алгоритм для вычисления общей стоимости лицензий, купленных на основе "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?
Любая справка будет цениться.
3 ответа
Принятый ответ, хотя и представляет собой элегантный фрагмент кода с точки зрения программиста, не дает наилучшей возможной цены для клиента и, следовательно, не может быть элегантное решение с точки зрения заказчика. Например, когда 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
Решение Марка - отличное общее решение, и определенно то, что вам нужно. должно идти с (в случае, если цены когда-либо изменятся.) Это решение сочетает в себе простоту 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. Хотя на самом деле вам, вероятно, следует предложить 50, когда кто-то будет искать 45, поскольку дополнительные 5 лицензий стоят всего 2 доллара. Итак, возможно, измените код с 46 на 45.
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