Принятый ответ, в то время как элегантный кусок кода С точки зрения программиста, не дает наилучшую цену для клиента и, следовательно, не может быть элегантным решением с точки зрения клиента. Например, когда 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
В чем именно вам нужна помощь?Вы пытаетесь выяснить, как они выбирают подходящую схему ценообразования для значений, превышающих стандартные пакеты (51+ лицензий)? –
Вид странного вопроса (или способ расспросить его с конкретной ссылкой на FogBugz ...), но я не уверен, что его нужно проголосовать вниз ... – mmacaulay
См. [Предыдущий вопрос] OP (http: /stackoverflow.com/questions/2684261/how-to-convert-a-number-to-a-range-of-prices). –