Como se ha mencionado, el problema se resuelve eligiendo el índice $i$ para el cual $b_i/a_i$ es el más pequeño. Luego, estableciendo $x_i = a_0/a_i$ y todas las demás variables a cero, obtenemos la función objetivo que suma:
$$ a_0 \cdot \frac{b_i}{a_i} $$
La complejidad temporal es entonces $O(n)$. Permítanme dar un ejemplo para ilustrar que limitar las variables (y tal vez los coeficientes) a enteros hace que el problema sea más difícil pero aún manejable.
El siguiente ejemplo de "cambio de monedas" se toma del artículo de programación dinámica de Wikipedia programación dinámica, donde se utiliza para motivar una alternativa a algoritmo voraz.
Supongamos que las monedas están disponibles en denominaciones $1,4,5,15,20$. Nos preguntan cómo hacer $23$ en cambio, donde "mejor" significa la menor cantidad de monedas.
Minimice $g(x) = x_1 + x_2 + x_3 + x_4 + x_5$ tal que $x_i \ge 0$ sean enteros y $$ 1x_1 + 4x_2 + 5x_3 + 15x_4 + 20x_5 = 23 $$
Si tratamos esto como un problema de programación lineal, relajando la restricción entera para permitir valores reales (racionales) de los $x_i$, entonces como se mencionó anteriormente, se logra un valor mínimo de $g(x)$ tomando $x_5 = 23/20 = 1.15$ (con las demás variables establecidas en cero). Nótese que la restricción del "problema" se cumple como igualdad (restricción ajustada) porque la solución es un vértice del politopo formado por la intersección de semi-espacios definidos por todas las restricciones (tanto la restricción del problema como las restricciones de no negatividad).
Una forma de cumplir con la restricción entera es mediante un algoritmo voraz que selecciona la moneda de mayor denominación tantas veces como sea posible sin exceder la cantidad de cambio que se debe hacer. Siguiendo este procedimiento, elegiríamos $x_5=1$ para seleccionar una moneda de denominación $20$, después de lo cual todavía se necesitaría hacer un cambio por los $23-20 = 3$ restantes. Dado que solo se puede usar la moneda de denominación $1$ sin exceder ese resto, este algoritmo voraz utiliza cuatro monedas en total para dar cambio exacto (igualdad):
$$ 23 = 20 + 1 + 1 + 1 $$
Pero esto en realidad no minimiza $g(x)$ ya que es posible una solución con tres monedas:
$$ 23 = 15 + 4 + 4 $$
Encontrar esa solución, con la restricción de igualdad, se puede hacer utilizando el enfoque de programación dinámica descrito en el artículo. Básicamente implica una búsqueda para superar las limitaciones del algoritmo voraz "sigue tu nariz".
Queremos utilizar el ejemplo para ilustrar que relajar la restricción de igualdad a una desigualdad permite soluciones enteras con incluso menos monedas:
$$ 1x_1 + 4x_2 + 5x_3 + 15x_4 + 20x_5 \ge 23 $$
tiene soluciones enteras no negativas con tan solo dos monedas.
El Lector atento notará que con esta restricción de desigualdad "relajada" (restricción del problema) el algoritmo anterior vuelve a ser considerado. Es decir, al verificar qué índice tiene el menor $b_i/a_i$ (donde en este caso de cambio de monedas todos los $b_i=1$), encontramos la solución no entera $g(x) = 1.15$ (es decir, $x_5 = 1.15$ y los demás $x_i$ cero).
Por lo tanto, para obtener una solución entera podemos "redondear hacia arriba" $x_5$ a dos monedas, y esta es realmente una solución óptima ya que cualquier solución de valor entero debe dárnos $g(x) \ge \lceil 1.15 \rceil = 2$.
Sin embargo, no siempre podemos lograr una solución tan simple para los problemas descritos aquí. Nuestro fácil éxito con el problema del cambio de monedas dependió del hecho de que aquí todos los $b_i = 1$, lo que significó:
$$ \left\lceil a_0 \cdot \frac{b_i}{a_i} \right\rceil = b_i \cdot \lceil a_0/a_i \rceil $$
cualquier índice $i$ da el menor $b_i/a_i$.
El caso general de sus problemas requerirá una búsqueda estructurada por programación dinámica, u otro de los enfoques mencionados en el artículo de programación entera.
