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中执行此操作？
任何帮助将不胜感激。
虽然从程序员的角度来看，优雅的代码片段并不能为客户提供最优惠的价格，但从客户的角度来看，这可能并不是一个优雅的解决方案。 例如，当n = 4时，接受的答案为1196美元，但客户显然更愿意选择5个许可证包，而只需支付999美元。
可以构建一种算法，该算法可以计算客户可以支付的最低价格以购买所需数量的许可证。 一种方法是使用动态编程。 我认为像这样的事情可能会成功：
int calculatePrice(int n, Dictionary 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 prices = new Dictionary { { 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 prices = new Dictionary { { 1, 299 }, { 5, 999 }, { 10, 1899 }, { 20, 3499 }, { 50, 7999 } }; class Bundle { public int Price; public Dictionary Licenses; } Bundle getBestBundle(int n, Dictionary prices) { Bundle[] best = new Bundle[n + prices.Keys.Max()]; best[0] = new Bundle { Price = 0, Licenses = new Dictionary() }; 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(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
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
Mark的解决方案是一个很好的通用解决方案，绝对是您应该使用的（如果价格发生变化）。这个解决方案结合了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。 虽然，实际上，当有人寻找45时你应该建议50，因为额外的5个许可证只花费2美元。 所以，代码中可能只有46到45位。