Minimieren Sie den Preis für Mengenrabattaufträge

Question

Ich versuche ein System zusammenzustellen, das Verbrauchsmaterial-Kits basierend auf einer angeforderten Menge vorschlägt. Die Herausforderung besteht darin, dass die Kits Volumen-/Mengenrabatte haben, so dass es für den Kunden billiger sein kann, eine größere Menge zu bestellen, weil der Preis geringer sein kann. Zum Beispiel, sagen wir mal, die verfügbaren Kits sind:

• 25 Widgets für $ 15
• 10 Widgets für $ 7
• 5 Widgets für $ 4
• 1-Widget für $ 1

Gerade jetzt, Für eine angeforderte Menge von 74 schlägt mein Algorithmus 2 x 25, 2 x 10 und 4 x 1 = $ 48 vor. Es wäre jedoch billiger für den Kunden, nur 3 x 25 = $ 45 zu bestellen.

Irgendwelche Gedanken, wie man das anpackt? Ich codiere in C#.

Danke!

Answer 1

Das sieht wie Standard-DP (dynamische Programmierung) aus.

// bestPrice is array of best prices for each amount 
// initially it's [0, INFINITY, INFINITY, INFINITY, ...] 

for (int i = 0; i <= 74; ++i) { 
    for (Pack pack : packs) { 
     // if (i + pack.amount) can be achieved with smaller price, do it 
     int newPrice = bestPrice[i] + pack.price; 
     if (newPrice < bestPrice[i + pack.amount]) { 
      bestPrice[i + pack.amount] = newPrice; 
     } 
    } 
} 

Die Antwort ist min(bestPrice[74], bestPrice[74 + 1], ... bestPrice[74 + 25 - 1]). Overhead 25 - 1 ist offensichtlich genug, weil sonst würden Sie ein Paket entfernen und Menge wäre immer noch >= 74.

Einige Links zum Thema:
http://en.wikipedia.org/wiki/Dynamic_programming
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

bearbeiten
Sie optimale Lösung finden können, wenn Sie es ein wenig ändern. Fügen Sie lastPack Array hinzu, also lastPack[i] ist die Größe des Pakets, das Sie verwendet haben, um die Menge i zu erreichen. Ich denke, Sie können herausfinden, wie Pseudocode oben zu aktualisieren.

Sobald Algorithmus abgeschlossen ist, können Sie bekommen Lösung wie diese

int total = 74; 
while (total > 0) { 
    // package of size lastPack[total] was used to get amount 'total' 
    // do whatever you want with this number here 

    total -= lastPack[total]; 
} 

Answer 2

Nun, beginnend mit der 25. Einheit ist der Preis $ 0.60/Stück. Also, wenn der Kunde mehr als 25 bestellt, vergessen Sie die Pakete, die Sie berechnen und einfach die Menge mit 0,60 $ multiplizieren.

Answer 3

So sind Sie tatsächlich manuell haben, gehen alle von den einzelnen Stützpunkten für Elemente unter einer Größenordnung von 25 ermitteln dann im Grunde eine Lookup-Tabelle verwenden Geben Sie das Szenario ein, um zu bestimmen, was für Mengen unter 25 zu bestellen ist. Wie bereits erwähnt, ist dies dem Knapsack-Problem sehr ähnlich.

Grundsätzlich würde Ihr Code etwa so aussehen;

int qtyOrder; 
int qtyRemain; 
int qty25pack; 
int qty10pack; 
int qty5pack; 
int qty1pack; 

//Grab as many 25 packs as possible 
qty25pack = (qtyOrder % 25); 
qtyRemain -= qty25Pack * 25; 

//Here use your lookup table to determine what to order 
// for the qty's that are less than 25 

Sie könnten eine Art gierigen Algorithmus verwenden, um es im laufenden Betrieb zu bestimmen. Was wäre ideal, wenn sich die Preise voraussichtlich stark ändern werden.

Das könnte so aussehen, als würde man die Paketgröße mit einer genauen Übereinstimmung füllen und dann die engste Übereinstimmung ermitteln, die gerade über der verbleibenden Menge liegt, und sehen, ob sie billiger ist.

So zum Beispiel:

//find the perfect product amount price 
While (qtyRemain != 0) { 
perfectPrice += (qtyRemain % nextSmallestSize) * nextSmallestPackagePrice; 
qtyRemain -= (qtyReamin % nextSmallestSize) 
} 

//Find the closest match over price 
While ((qtyRemain % nextSmallestSize) != 0){ 
closePrice += (qtyRemain % nextSmallestSize) * nextSmallestPackagePrice; 
qtyRemain -= (qtyRemain % nextSmallestSize) 
} 
//add the last price before we reached the perfect price size 
closePrice += nextSmallestPackagePrice; 

//determine lowest price 
if closePrice < perfectPrice { 
cost = closePrice; 
} 
else { 
cost = PerfectPrice; 
} 

Dieser Code ist nicht annähernd vollständig, aber sollte Ihnen eine Idee geben. Der Code ist wahrscheinlich auch nicht der beste.

bearbeiten

Der zweite Teil des Codes nach dem ersten Chunk anstelle des Lookup gehen würde