SoloCodigo

Hola,
trataré de explicar de qué va el problema de la mochila.

Supongamos que tenemos n elementos y cada uno de estos items tiene un peso y un valor. Y tenemos una "mochila" con una capacidad máxima para aguantar cierto peso (llamémosle M). El problema de la mochila tiene dos versiones.
1) La primera es encontrar la mejor forma de combinar estos elemento en la mochila de forma que el peso de la suma de los items no sobrepase el  límite de la mochila y que el valor de la suma de los items sea máximo, dado cierto conjunto de elementos.

2) El segundo es el llamado problema de la mochila fraccionada. Aquí en realidad lo que se puede fraccionar son los items. De modo que podrías meter 'medio' item en la mochila hasta llegar al límite del peso y tratando, de nuevo, de obtener el valor más alto sumando todos los items metidos en la mochila. Por supuesto, si metes una fracción de item su valor también se fracciona. Es decir, si tenemos el item 3 que pesa 6 y cuyo valor es 4 y metemos 1/2 item, entonces el peso será 3, pero el valor será 2 (es decir, 4/2=2). Queda claro ¿no?

Según la teoría de la complejidad computacional este problema es NP-completo. Es decir, no tiene un solución eficiente en términos de complejidad temporal. Para casos sencillos se puede resolver sin problemas, pero para casos con muchos items el coste temporal va creciendo exponencialmente, con lo que en problemas con tallas grandes se hace inviable resolverlo con ningún tipo de algoritmo conocido hasta ahora.

Se suelen emplear algoritmos voraces para su resolución.

Por cierto, si alguno consigue resolverlo con un algoritmo de coste polinómico o lineal que vaya preparándose para empezar a dar conferencias en universidades porque habrá resuelto un dilema computacional que viene desde los años 50. Ya que existe una teoría que dice que si se encuentra solución para algún problema NP-completo, muchos de los demás problemas de la familia NP-completa se podrán resolver aplicando un algoritmo similar. Suerte.

PD: Había en este foro algún matemático que estaba estudiando la rama de computación. Me gustaría comentar sobre la teoría de la complejidad. Es que no recuerdo quién era ni dónde lo he leído. Si me lees, avisa:)

Bueno, manos a la obra (yo tengo una solución algorítmica no implementada).

Saludos.

Los caracteres raros me salen cuando contesto desde Linux. ¿? No sé por qué.

Hola Lucia,

digo yo que para repetir la rutina solo necesitarás una instrucción del tipo repeat... until.
Lo que pasa es que en C se llama do...while.

podrí­as hacer....

char q;

do{

     rutina a implementar
      printf("Desea repetir la rutina?n");
      q = getchar();
}while (q=='s');

O podrí­as usar un scanf("Desea repetir la rutina?  %cn", q); en lugar del printf y el getchar.

Y en cuanto al new eso es para crear un nuevo objeto. En C++ necesitarás la librerí­a iostream.h si no me equivoco y, por supuesto, tener definido el objeto.

Bueno, espero haber sido de ayuda.
Un saludo.

Me bajé el gpc para compilar programas en Pascal para linux y no me funciona, me da un error. ¿A qué puede deberse?
A parte de bajarme el gpc ¿debo bajarme algo más? ¿algún tipo de librería o alguna leche de esas?
Bueno, un saludo.

:P:P

Eh solocodigo, solo quedan dos más, ¿no? Si lo apoyan dos más lo pones, ¿no?


(qué poco éxito:()
Saludos

¿¿¿Será posible que estés aprendiendo a  programar y lo primero que quieras hacer es un virus???

Mira, empieza con esto:

#include <stdio.h>

int main(void)
{
   printf("Hola, mundon");
   return 0; //si no pones el return te dará un warning al compilar
}


Venga hombre, un saludo.

Hola,
¿la estructura del array es así:

char *array[N];

o así:

char array[N][M]?

Pura curiosidad.
Un saludo.

Hola icelon,
¿podrías explicarme qué son los algoritmos "case insensitive"?

(Case insensitive = insensible a las mayúsculas??)

Bueno, desconocía esos algoritmos, ¿dónde puedo encontrar información sobre eso?

Un saludo.

Hola, el acrobat me dice que ese archivo está dañado.
Un saludo.

No hace falta, ya lo he conseguido. Tengo un algoritmo poco eficiente porque me he dedicado a tratarlo como lo haría yo sobre el papel, sacando las clases de equivalencia y basándome en el teorema de Nerode. Una barbaridad, pero funciona.

Bueno, gracias de todos modos. Ya tengo un generador de autómatas aleatorios:P:P
Saludos.

Si resuelves el problema de calcular el determinante lo tienes todo hecho, porque para calcular la matriz adjunta necesitas calcular el determinante de submatrices de la susodicha matriz (¡vaya lio!).
Supongo que necesitas un algoritmo para matrices cuadradas invertibles de dimensión mayor o igual que cuatro, ¿no?
Si son de dimensión 2 ó 3 la cosa es mucho más sencilla. Por ejemplo, para n=3 el determinante sería:

det(A)=(a11+a22+a33)+(a12+a23+a31)+(a21+a32+a13)-(a13+a22+a31)-(a23+a32+a11)-(a12+a21+a33);

Bueno, supongo que eso ya lo sabrías.
A ver si encuentro algo, que parece interesante. Si lo resuelves pon la solución por aquí, ¿vale?

Hola,
¿alguien tiene alguna implementación de algún tipo de algoritmo genético?
Es pura curiosidad.
Gracias,
un saludo.