Solución del reto

A continuación mi solución al reto.

Observación 1

La primera observación es que conviene intentar llegar primero con los coeficientes más grandes a un resultado lo más cercano posible al objetivo, y posteriormente intentar con los coeficientes restantes. De aquí que mi primer intento fué usar una función recursiva actuando sobre una lista ordenada de mayor a menor:

[java]
/**
* Regresa la suma de los coeficientes encontrados para lograr target o -1 si
* no se pudieron encontrar.
*/
public static int intento1(int[] list, int pos, int target) {
if ((pos == list.length) && (target > 0)) {
return -1; // llegamos al final de la lista
}
else if (target == 0) {
return 0; // si traget es 0, los coeficientes son 0 y su suma es 0
}

int currN = list[pos];
int x = target/currN; // x*currN es lo más cercano posible a target

for (int currX = x; currX >= 0; currX–) { // Comenzamos con la mayor X y retrocedemos.
int currTotal = currX*currN;
int sum = intento1(list, pos+1, target-currTotal); // El nuevo target es target-currX*currN
if (sum != -1) {
return currX+sum; // sum tiene la suma de los coeficientes restantes
}
}

return -1;
}
[/java]

Así usamos esta función:

[java]
int[] lista = { 98, 42, 23, 17, 3, 2 };
int sum1 = intento1(lista, 0, 2349);
int sum2 = intento1(lista, 0, 2102);
int sum3 = intento1(lista, 0, 2001);
int sum4 = intento1(lista, 0, 1747);
[/java]

Observación 2

La versión anterior es, efectivamente, la forma más rápida de encontrar coeficientes que nos den la suma que queremos. El problema es que la suma de dichos coeficientes podría no ser la menor. Para que esto quede claro, consideremos esta suma: X1*6+X2*4+x3*1 =9. Usando únicamente la observación 1, resolveríamos el problema de esta forma X1=1, X2=0,X3=3 (X1+X2+X3=4). Sin embargo, noten que el menor lo obtenemos realmente con X1=0, X2=2,X3=1, (X1+X2+X3=3). De aquí que debemos buscar con coeficientes menores también y obtener el mínimo de ellos:

[java]
public static int intento2(int[] list, int pos, int target) {
if ((pos == list.length) && (target > 0)) {
return -1;
}
else if (target == 0) {
return 0;
}

int currN = list[pos];
int x = target/currN;
int minSum = Integer.MAX_VALUE;

for (int currX = x; currX >= 0; currX–) {
int currTotal = currX*currN;
int currSum = intento2(list, pos+1, target-currTotal);
if (currSum != -1) {
int sum = currSum+currX;
if (sum < minSum) {
minSum = sum; // Ahora no nos detenemos y continuamos buscando el mínimo
}
}
}

return (minSum != Integer.MAX_VALUE ? minSum : -1);
}
[/java]

Observación 3

El código anterior encuentra el mínimo. El problema ahora es que la complejidad se volvió exponencial. Sin embargo, podemos acotar por mucho la búsqueda si consideramos que al encontrar un conjunto de coeficientes que logren el resultado, lo único que tenemos que hacer en adelante es tratar de reducir dicha suma y por ello no necesitamos probar con coeficientes que sean más grandes que la suma de un resultado válido:

[java]
/**
* maxN es una cota superior para los valores de los coeficientes.
*/
public static int intento3(int[] list, int pos, int target, int maxN) {
if ((pos == list.length) && (target > 0)) {
return -1;
} else if (target == 0) {
return 0;
}

int currN = list[pos];
int n = target/currN;
int minSum = Integer.MAX_VALUE;

for (int currX = Math.min(n, maxN); currX >= 0; currX–) { // Comenzamos ahora desde la cota maxN
int currTotal = currX*currN;
int currSum = intento3(list, pos+1, target-currTotal, maxN-currX); // La cota dismuye currX
if (currSum != -1) {
int sum = currSum+currX;
if (sum < minSum) {
minSum = sum;
maxN = Math.min(minSum, maxN); // Encontramos un resultado; tenemos una nueva cota
}
}
}

return (minSum != Integer.MAX_VALUE ? minSum : -1);
}
[/java]

Y esta es mi solución al problema. El siguiente código corre en mi máquina en menos de un segundo:

[java]
int[] lista = { 98, 42, 23, 17, 3, 2 };
int sum1 = intento3(lista, 0, 2349, Integer.MAX_VALUE);
int sum2 = intento3(lista, 0, 2102, Integer.MAX_VALUE);
int sum3 = intento3(lista, 0, 2001, Integer.MAX_VALUE);
int sum4 = intento3(lista, 0, 1747, Integer.MAX_VALUE);
System.out.println(sum1*sum2*sum3*sum4);
[/java]

Este código imprime: “354200”. Los coeficientes son los siguientes:

23*98 + 1*42 + 0*23 + 3*17 + 0*3 + 1*2 = 2349
21*98 + 1*42 + 0*23 + 0*17 + 0*3 + 1*2 = 2102
20*98 + 0*42 + 0*23 + 2*17 + 1*3 + 2*2 = 2001
17*98 + 1*42 + 0*23 + 2*17 + 1*3 + 1*2 = 1747

Un comentario en “Solución del reto

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s