Este problema admite una solución codiciosa O (N).
Suponga que x₁, x₂ son ubicaciones de dos casas que desean vender vino, e y₁, y₂ son ubicaciones de dos casas que desean comprar vino de manera tal que x₁ <x₂ e y₁ <y₂. El núcleo de la solución radica en darse cuenta de que nunca es mejor enviar una unidad de vino de x₁ a y₂ y una unidad de x₂ a y₁ que enviar una unidad de x₁ a y₁ y una unidad de x₂ a y₂. Es decir, tiene sentido enviar vino del vendedor de la izquierda al comprador de la izquierda y así sucesivamente.
El problema se puede resolver de esta manera: localice el vendedor más a la izquierda y envíe la mayor cantidad de vino posible / requerida al primer comprador. Si al vendedor no le queda vino después de esto, pase al siguiente vendedor. Alternativamente, si se ha cumplido el requisito del comprador, pase al siguiente comprador. Siga haciendo esto hasta que todo el vino haya sido transferido de los vendedores a los compradores. Como las ubicaciones de las casas ya se han proporcionado en orden, esto se puede hacer en O (N).
- Cómo mejorar mis estructuras de datos y algoritmo desde el nivel básico
- ¿Por qué la complejidad espacial de quicksort es "log n"?
- ¿Los expertos de ML de primer nivel crean su propio algoritmo de ML o utilizan bibliotecas de Python o módulos R?
- ¿Qué algoritmo se debe usar para una tesis que tiene al menos tres desventajas que se pueden resolver?
- ¿Existen constructores de algoritmos comerciales Plug and Play que no requieren ninguna habilidad de codificación?
Aquí está el pseudocódigo:
def mincost (N, a [])
{
ret = 0
vendedor = 0, comprador = 0
mientras que (1)
{
while (vendedor = 0) vendedor ++;
while (comprador <N y un [comprador] <= 0) comprador ++;
si (vendedor == N o comprador == N) se rompe;
transacción = min (un [comprador], - un [vendedor]);
ret + = transacción;
un [comprador] - = transacción;
una [vendedor] + = transacción;
}
volver ret;
}
