Minimizar el precio para las órdenes de descuento por volumen

Question

Estoy tratando de armar un sistema para sugerir kits de consumibles basados ​​en la cantidad solicitada. El desafío al que me estoy enfrentando es que los kits tienen descuentos por volumen/volumen, por lo que puede ser más barato para el cliente pedir una cantidad mayor porque el precio puede ser menor. Por ejemplo, digamos que los kits disponibles son:

• 25 los widgets por $ 15
• 10 accesorios por $ 7
• 5 los widgets por $ 4
• 1 Reproductor de $ 1

En este momento, para una cantidad solicitada de 74, mi algoritmo sugerirá 2 x 25, 2 x 10 y 4 x 1 = $ 48. Sin embargo, sería más barato que el cliente simplemente pida 3 x 25 = $ 45.

¿Alguna idea sobre cómo abordar esto? Estoy codificando en C#.

Gracias!

Answer 1

Eso se parece al DP estándar (programación dinámica).

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

La respuesta es min(bestPrice[74], bestPrice[74 + 1], ... bestPrice[74 + 25 - 1]). La sobrecarga 25 - 1 es obviamente suficiente, porque de lo contrario eliminaría un paquete y la cantidad seguiría siendo >= 74.

Algunos enlaces sobre el tema:
http://en.wikipedia.org/wiki/Dynamic_programming
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

editar
puede encontrar la solución óptima si se modifica un poco. Agregue lastPack matriz, por lo que lastPack[i] es el tamaño del paquete que utilizó para alcanzar la cantidad i. Supongo que puedes averiguar cómo actualizar el pseudo-código anterior.

Una vez que finaliza el algoritmo, se puede obtener una solución como esta

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

Bueno, comenzando con la unidad 25, el precio es $ 0,60/artículo. Entonces, si el cliente pide más de 25, olvide los paquetes que está calculando y simplemente multiplique la cantidad por $ 0.60.

Answer 3

por lo que son en realidad va a tener que determinar manualmente todos los puntos de corte para artículos bajo una orden de 25. Entonces, básicamente, usar una tabla de búsqueda escriba escenario para determinar qué orden para qty es menor que 25. Como se señaló anteriormente, esto es muy similar al problema Knapsack.

Básicamente su código se parecería a algo así como;

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 

Puede usar algún tipo de algoritmo codicioso para determinarlo sobre la marcha. Lo cual sería ideal si se espera que los precios cambien mucho.

Podría parecer algo como llenar el tamaño del paquete con una coincidencia exacta y luego determinar la coincidencia más cercana que está justo por encima del resto restante y ver si es más barato.

Así, por ejemplo:

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

Este código no está cerca completa, pero debe darle una idea. El código tampoco es probablemente el mejor.

Editar

El segundo trozo de código iría después de que el primer fragmento en el lugar de las operaciones de búsqueda