¿Qué algoritmos se pueden usar para resolver este problema de optimización?

Esto se puede reducir al problema de la mochila, que tiene un tiempo pseudopolinomial. Es decir, tiene tiempo de ejecución en términos de su presupuesto, y suponiendo que los precios sean enteros (o digamos como máximo 2 dígitos después del punto decimal). En particular, tiene tiempo de ejecución [matemática] O (BG) [/ matemática], donde [matemática] B [/ matemática] es el presupuesto y [matemática] G [/ matemática] es el número de gemas disponibles. No tiene ninguna suposición sobre cómo se correlacionan los precios con su calidad y ofrece una solución exacta.

Vamos a restringirnos a un diseño específico, digamos 3 piedras rosas, 1 piedra verde, 2 piedras claras y 2 piedras azules. Mantendremos una tabla [matemáticas] T [/ matemáticas] con tamaño [matemáticas] B \ veces 4 \ veces 2 \ veces 3 \ veces 3 = 72B [/ matemáticas]. Es decir, la entrada [math] (m, p, g, c, b) [/ math] -th de la tabla será la calidad máxima que podemos lograr hasta ahora usando la unidad [math] m [/ math] de dinero, [matemáticas] p [/ matemáticas] piedras rosas, [matemáticas] g [/ matemáticas] piedras verdes, [matemáticas] c [/ matemáticas] piedras claras y [matemáticas] b [/ matemáticas] piedras azules.

Al principio, la tabla debe llenarse con [math] – \ infty [/ math], excepto [math] (0, 0, 0, 0, 0) [/ math] debe ser [math] 0 [/ math]. Cuando agregamos una nueva piedra, digamos que es una piedra clara con precio [matemática] m_i [/ ​​matemática] y calidad [matemática] q_i [/ ​​matemática], tenemos

[matemáticas] T (m, p, g, c, b) = [/ matemáticas] max [matemáticas] (T (m, p, g, c, b), T (m – m_i, p, g, c – 1, b) + q_i) [/ matemáticas]

en el que podemos actualizar la tabla en tiempo lineal al tamaño de la tabla. Hay algunos detalles menores, como los índices negativos y el orden de actualización, pero esto concluye la idea principal.

Finalmente, elija el máximo [matemática] T (*, 3, 1, 2, 2) [/ matemática] (donde * debería ser como máximo el presupuesto). Si desea rastrear la solución, es posible: simplemente registre qué gema eligió cuando actualice la tabla.

Gracias por las respuestas, recientemente he resuelto este problema de optimización con tres algoritmos separados (en un esfuerzo por encontrar el más eficiente). En caso de que alguien siga interesado, estoy publicando una breve descripción de ellos aquí.

El primer paso fue reducir la cantidad de piedras (gracias Somdeb Sarkhel) encontrando piedras que estaban “dominadas” y por lo tanto nunca fueron útiles. Si, por ejemplo, cualquier piedra rosada tiene otras tres piedras rosadas que cuestan lo mismo o menos y que tienen mayor calidad, podemos tirar esa piedra.

Ahora ideé mi primer algoritmo, que es una versión del algoritmo codicioso. Comienza a llenar cada ranura con la piedra más cara hasta que comienza a quedarse sin dinero, luego llena el resto con las piedras más baratas. Luego, comenzando desde el final y trabajando hacia atrás, cambia una piedra costosa por una un poco más barata, luego actualiza las ranuras restantes. Esto continúa por la línea hasta que la primera piedra se degrada por completo. Este algoritmo es confiable y siempre produce la optimización correcta, pero es lento.

Mi siguiente esfuerzo se basó en parte en la entrada del usuario de Quora. Comienza llenando cada ranura con la piedra de la mejor relación calidad / precio. Si la solución resultante supera el presupuesto, elegimos rebajas de piedra con la menor relación calidad / pérdida de precio. Si estamos por debajo del presupuesto, hacemos lo contrario. Este es el algoritmo más rápido, pero a veces solo produce un resultado casi óptimo.

Mi algoritmo final es similar al segundo. Llena cada espacio con la piedra más cara, que generalmente excede en gran medida el presupuesto. A continuación, baja la calificación de cada ranura eligiendo rebajas con la mejor relación. Este algoritmo es rápido y confiable produce el resultado óptimo, como se verifica usando el primer algoritmo.

Lo sorprendente para mí con los algoritmos es la frecuencia con la que hay varias formas de lograr el mismo objetivo. Gracias de nuevo por las ideas, fueron muy útiles.

Usa un árbol con peso. Asigne a cada nodo un valor que sea la calidad / precio. Elija el número superior de joyas de calidad / precio para cada categoría, luego determine la diferencia de precio entre las joyas superiores y el presupuesto máximo permitido. Luego, elija el número superior de joyas que rompan ese rango de precios con la más alta calidad / precio. Has reducido el número de combinaciones posibles; Si el número es lo suficientemente pequeño, puede recorrer cada combinación posible.

Por supuesto, este algoritmo es una versión modificada del algoritmo codicioso.

Tiene razón en que este es, de hecho, el problema de la mochila. Se pueden encontrar soluciones de ejemplo en Wikipedia, por ejemplo.

Usaría un algoritmo estocástico de escalada. Básicamente soy lo suficientemente flojo como para conformarme con un óptimo local 🙂