performance - sacar - Comercio electrónico: algoritmo para calcular descuentos.

como saber que descuento me hicieron

Question

Necesito un consejo experto sobre un asunto difícil.

El escenario es:

• sitio web de comercio electrónico
• muchos productos
• Muchos descuentos mezclados en estos productos.

Un producto se identifica con un ProductID único y tiene un precio de venta. Escenario muy clásico. El producto también puede estar en uno o más descuentos.

Un descuento puede ser de diferentes tipos. Un ejemplo de un descuento es:

• Compre dos o más dentro de un conjunto de productos y obtenga un X por ciento de descuento en cada producto

Una línea de pedido solo puede obtener un descuento, por lo que una vez que se ha descontado la línea de pedido, no estará disponible para otros descuentos.

Datos del caso de prueba:

• Producto-1: $ 10
• Producto-2: $ 10
• Producto-3: $ 50
• Producto-4: $ 100

Descuento A : compre dos o más y obtenga un 20% de descuento en cualquiera de los siguientes productos

• Producto-1
• Producto-2
• Producto-3
• Producto-4

Discount-B : compre productos y obtenga un 50% de descuento en el siguiente producto

• Producto-3

Escenario de prueba 1:

Cesta : contiene artículos de línea con:

• Producto-1
• Producto-3
• Producto-4

Cálculo # 1 :

• Descuento-A: Producto-1, Producto-3, Producto-4 = $ 2 + $ 10 + $ 20 = $ 32
  • = $ 32 de ahorro total

Cálculo # 2 :

• Descuento-A: Producto-2, Producto-4 = $ 2 + $ 20 = $ 22
• Descuento-B: Producto-3 = $ 25
  • = $ 22 + $ 25 = $ 47 de ahorro total

Lo que significa que una combinación de Discount-A y Discount-B dará el mejor descuento posible para el cliente.

Escenario de prueba 2:

Cesta : contiene artículos de línea con:

• Producto-3
• Producto-4

Cálculo # 1 :

• Descuento-A: Producto-3, Producto-4 = $ 10 + $ 20 = $ 30
  • = $ 30 de ahorro total

Cálculo # 2 :

• Descuento-B: Producto-3 = $ 25
  • = $ 25 de ahorro total

Lo que significa que la aplicación de Discount-A dará el mejor descuento posible para el cliente.

Para calcular el mejor descuento para una cesta determinada, se deben evaluar literalmente todas las combinaciones de productos y los descuentos disponibles en estos productos.

Normalmente hay 30-40 artículos de línea en una canasta, cada uno con 0-3 descuentos cada uno.

Básicamente estoy atascado con encontrar una manera eficiente de hacer este cálculo.

En este momento el algoritmo que tengo para aplicar los descuentos es algo así como:

• Borrar descuentos en la cesta
• Obtenga todos los ProductID únicos para los artículos de línea en la cesta
• Obtenga todos los descuentos disponibles para estos ProductID''s
• Para cada descuento (sin orden)
  • Aplique el descuento si lo satisfacen las líneas de pedido marcadas sin descuento.
    • Marcar artículos de línea en descuento como descuento

Pero esto no es suficiente, ya que no prueba diferentes combinaciones de artículos de línea / descuentos.

He estado buscando algoritmos estandarizados que puedan resolver problemas como este, pero hasta ahora no han tenido suerte.

Esperamos oír de usted :)

Answer 1

Asumiendo que:

1. Puede calcular todos los descuentos disponibles en función de su cesta.
2. A cada producto solo se le puede aplicar un descuento único.
3. Cada descuento solo puede ser usado una vez.

Entonces, el problema se convierte en uno que se denomina problema de assignment y se puede resolver de manera óptima en O (n ^ 3) utilizando el algoritmo húngaro .

Deberá calcular una matriz M [a, b] que contiene el dinero ahorrado si utiliza el descuento a en el producto b. (Si no se aplica un descuento, establezca el dinero guardado en 0).

El algoritmo húngaro calculará la forma de asignar descuentos a los productos que ahorran más dinero.

Si no tiene el mismo número de descuentos y productos, agregue descuentos ficticios (con cero ahorros) o productos ficticios (nuevamente con cero ahorros) hasta que la cantidad de descuentos coincida con la cantidad de productos.