El problema de la mochila lo enunciaria de forma mas didactica con el siguiente ejemplo:
Supongamos que somos ladrones y hemos entrado en la casa de un rico, tenemos un saco que tiene un determinada capacidad de volumen ;) , entonces encontramos diferentes objetos con un valor y volumen determinado, entonces surge la pregunta ¿Cuales nos conviene llevar?
//...
static int mochila( int capacidad, int n , int [ ] peso, int [ ] utilidad ) {
int NUMERO_DE_ELEMENTOS = n;
int W = capacidad;
int [ ][ ] dp = new int[ NUMERO_DE_ELEMENTOS + 1 ][ W + 1 ];
for (int j = 0; j < W + 1 ; ++j)
dp[ 0 ][ j ] = 0;
for (int i = 0; i < NUMERO_DE_ELEMENTOS + 1 ; ++i)
dp[ i ][ 0 ] = 0;
for (int i = 1; i < NUMERO_DE_ELEMENTOS + 1; ++i ) {
for (int w = 1; w < W + 1; ++w ) {
if ( w - peso[ i ] < 0 )
dp[ i ][ w ] = dp[ i - 1 ][ w ];
else // if ( w - peso[ i ] >= 0 )
dp[ i ][ w ] = Math.max( dp[ i - 1 ][ w ],
utilidad[ i ] + dp[ i - 1 ][ w - peso[ i ] ] ) ;
}
}
return dp[ NUMERO_DE_ELEMENTOS ][ W ];
}
public static void main(String[] args) {
int n, capacidad;
Scanner cin = new Scanner(System.in);
System.out.printf("INGRESE EL NUMERO DE LOS ELEMENTOS:");
n = cin.nextInt();
int [ ] peso = new int[ n + 1];
int [ ] utilidad = new int[ n + 1];
System.out.printf("INGRESE LOS PESOS DE LOS ELEMENTOS:");
for(int i=1; i < n + 1; ++i)
peso[ i ] = cin.nextInt();
System.out.printf("INGRESE LA UTILIDAD DE LOS ELEMENTOS:");
for(int i=1; i < n + 1; ++i)
utilidad[ i ] = cin.nextInt();
System.out.printf("INGRESE LA CAPACIDAD DE LA MOCHILA:");
capacidad = cin.nextInt();
System.out.println( mochila(capacidad , n, peso, utilidad) );
return ;
}
//...
La complejidad es O(n * W), donde n es el número total de elementos y W es el peso máximo.
PD: encontré el siguiente blog que me ayudo a resaltar mi código:
http://patrickwebster.blogspot.com/2009/02/syntaxhighlighter-in-blogger.html
Otras referencias para resaltar codigo:
http://sistemasolutions.blogspot.com/2009/08/codigo-fuente-en-tu-blog_23.html
http://tamanmohamed.blogspot.com/2012/02/blog-how-to-professionally-highlight.html
