Fogbugz定價方案的算法

Question

我正在尋找一種算法來計算基於「服務器的FogBugz」定價方案（http://www.fogcreek.com/FogBugz/PriceList.html）購買的許可證的總成本。

FogBugz的定價是：

• 1許可$ 299
• 5許可證包$ 999產品
• 10許可證包$ 1,899
• 20許可證包$ 3,499
• 50許可證包$ 7999

如果你問一個報價讓我們說136個許可他們calcul吃了22,694美元。

如何在C＃或LINQ中執行此操作？

任何幫助將不勝感激。

Answer 1

接受的答案，而優雅的一塊從一個程序員的角度代碼，不給最好的價格爲客戶，因此可能不是一個完美的解決方案從客戶的角度來看。例如，當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 

---

更新產生故障是更復雜一些，但我絕對認爲這將是有益的你的客戶。你可以做這樣的事情（假設打印到控制檯，雖然真正的程序可能輸出到Web頁面）：

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 

Answer 2

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 

Answer 3

馬克的解決方案是一個很好的通用解決方案，你應該用（如果價格不斷變化）。該解決方案與馬克的正確性DTB的的簡單結合去肯定什麼：

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; 

它看起來像ONL y邊緣情況是5比4好，而50比46 ... 49好。儘管實際上，當某人尋找45時，你應該建議50，因爲額外的5個許可只需要2美元。所以，在代碼中可能是46到45。