Problema del reparto del botín
De Wikipedia, la enciclopedia libre
Este artículo debería estar en Wikilibros ya que es una guía o manual en vez de un verdadero artículo enciclopédico.
Si modificas este artículo dándole una orientación enciclopédica, elimina por favor esta plantilla.
Tabla de contenidos |
[editar] Descripción del problema
Tenemos un botín con lingotes empaquetados en n cajas de diferentes pesos (reales) y, para dividir el botín a medias decidimos basarnos en los pesos de las cajas. Queremos saber si se puede dividir el botín en dos partes iguales sin desempaquetar ninguna de las cajas.
[editar] Solución del problema
Esto podría realizarse mediante programación dinámica, sin embargo, al decirnos que los pesos son números reales no podemos, ya que para utilizar dicho método, los pesos tendrían que ser naturales. Por tanto, vamos a estudiar la estrategia de vuelta atrás para la resolución del problema que se nos plantea.
Considerando P = ∑ (i:=k+1 .. n) pi, el problema es equivalente a comprobar, si es posible, sumando algunos de los pesos, obtener P/2.
Veamos cómo buscar un subconjunto de los pi cuya suma sea igual a cierta cantidad dada, C. Supondremos que ∑ (i:=k+1 .. n) ≥ C, ya que en otro caso no hay solución, y que para todo i : 1 ≤ i ≤ n : pi ≤ C, para no considerar pesos que sabemos de antemano tiene sentido sumar.
La solución la vamos a dar mediante una tupla (x0, …, x n) que represente la función característica de este subconjunto, es decir, xi = 1 si el elemento pi pertenece al subconjunto y xi = 0 en caso contrario.
Es mejor, para la eficiencia del algoritmo que probemos primero con xk = 1, aunque no seguro, pues al reducir el valor de la suma pendiente de acumular facilitaremos el acceso más rápido a una solución. Llevamos como marcador una variable suma que representa la suma acumulada de los números elegidos hasta el momento. Así, cuando suma sea igual a C podemos acabar (los restantes pesos no son considerados, no se cogen). El algoritmo recursivo de vuelta atrás es el siguiente :
[editar] Implementación en pseudocódigo
Proc reparto (P[1..n] de real, C : real, sol[1..n] de 0..1, k : 1..n, suma : real, éxito : bool)
{hijo izquierdo → añadir peso}
si (suma + P[k] ≤ C) entonces
sol[k] := 1;
{marcar}
suma := suma + P[k];
si (suma = C) entonces
éxito := cierto;
para i:=k+1 hasta n hacer
sol[i]:=0;
sino
si (k < n ^ suma < C) entonces
reparto (P, C, sol, k+1, suma, éxito);
fsi
fsi
{desmarcar}
suma := suma – P[k] ;
fsi
{hijo derecho → no añadir peso, no puede generar solución}
si (éxito ^ k<n) entonces
sol[k] := 0;
reparto (P, C, sol, k+1, suma, éxito);
fsi
fproc.
Podemos realizar una mayor poda, mejorando la eficiencia del algoritmo, si aprovechamos el hecho de que son positivos. En este caso, si suma + ∑(i:=k+1 .. n) P[i]<C, podemos podar el nodo actual porque nunca vamos a poder alcanzar la solución desde él. Además, si los pesos están ordenados de forma creciente, también podemos podar el nodo actual si suma + P[k+1] > C. Para comprobar fácilmente la primera condición llevamos otro marcador resto tal que resto = ∑ (i:=k+1.. n) P[i].
En el algoritmo, al probar el hijo izquierdo no es necesario comprobar la primera condición, ya que si era posible alcanzar C para el padre y hemos cogido un nuevo peso, sigue siendo posible.
{resto = ∑ (i:=k..n) P[i] ^ P[1]≤…≤P[n]}
Proc repartoBotin (P[1..n] de real, C : real, sol[1..n] de 0..1, k : 1..n, suma, resto : real, éxito : bool)
{marcar común a los dos hijos}
resto := resto –P[k];
{hijo izquierdo}
sol[k] :=1;
{marcar}
suma := suma + P[k];
si (suma = C) entonces
éxito := cierto;
para i:=k+1 hasta n hacer
sol[i]:=0;
fpara
sino
si (k < n ^ suma + P[k+1] ≤ C) entonces
repartoBotin (P, C, sol, k+1, suma, resto, éxito);
fsi
fsi
{desmarcar}
suma := suma – P[k] ;
fsi
si (éxito) entonces
{hijo derecho}
sol[k] := 0;
si (k<n ^ suma+resto≥C ^ suma+P[k+1]≤C) entonces
repartoBotin (P, C, sol, k+1, suma, resto, éxito);
fsi
fsi
{desmarcar, común a los dos}
resto := resto + P[k];
fproc.
[editar] Inicialización
La función principal que comprueba si se puede repartir el botín en dos partes iguales es:
Fun principal (P[1..n] de real) dev <éxito : bool, sol[1..n] de 0..1>
peso :=0;
para i:=1 hasta n hacer
peso := peso + P[i];
fpara
suma := 0;
resto := peso;
éxito := falso;
reapartoBotin (P, peso/2, sol, 1, suma, resto, éxito);
ffun.
[editar] Bibliografía
Martí, Narciso; Verdejo, Alberto; Ortega Yolanda (2003), Estructuras de datos y métodos algorítmicos: ejercicios resueltos, Madrid: Prentice Hall
