Algoritmo per schema di prezzi Fogbugz

Question

Sto cercando un algoritmo per calcolare il costo totale delle licenze acquistate in base allo schema di tariffazione "FogBugz per il server" (http://www.fogcreek.com/FogBugz/PriceList.html).

Fogbugz prezzi è:

• 1 Licenza $ 299
• 5 Licenza pack $ 999
• 10 pacco licenza $ 1.899
• 20 pacco licenza $ 3.499
• 50 pacco licenza $ 7.999

Se chiedete un preventivo, diciamo 136 licenze che calcolano lo mangiò come $ 22,694.

Come posso farlo in C# o LINQ?

Qualsiasi aiuto sarà apprezzato.

Answer 1

la risposta accettata, mentre un elegante pezzo di codice dal punto di vista del programmatore, non dà il miglior prezzo possibile per il cliente e, pertanto, potrebbe non essere una soluzione elegante dal punto di vista del cliente. Ad esempio, quando n = 4, la risposta accettata restituisce $ 1196, ma un cliente preferirebbe ovviamente scegliere il pacchetto di licenze 5 e pagare solo $ 999.

È possibile costruire un algoritmo che può calcolare il prezzo minimo possibile che il cliente può pagare per acquistare il numero di licenze richiesto. Un modo per farlo è usare la programmazione dinamica. Penso che qualcosa di simile potrebbe fare il trucco:

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)); 
} 

uscita:

22694 
999 

---

Aggiornamento Produrre un guasto è un po 'più complicato, ma io sicuramente penso che sarà utile per i tuoi clienti Si potrebbe fare qualcosa di simile (assumendo la stampa alla console, anche se un vero e proprio programma sarebbe probabilmente uscita a una pagina 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(); 
    } 
} 

uscita:

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 

o

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

soluzione di Marco è una grande soluzione generale , e sicuramente quello che si dovrebbe andare con (nel caso in cui i prezzi mai cambiare.) Questa soluzione combina la semplicità di DTB di con la correttezza della Marco:

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; 

sembra che l'onl i casi limite sono 5 è meglio di 4 e 50 è meglio di 46 ... 49. Anche se, realisticamente, dovresti suggerire 50 quando qualcuno cerca 45, dato che le 5 licenze extra costano solo $ 2. Quindi, forse da 46 a 45 nel codice.