• Lunes 29 de Abril de 2024, 21:50
« anterior próximo »
Páginas: [1]

Autor Tema:  LA MOCHILA USANDO VUELTA ATRAS  (Leído 4384 veces)

jeamcarlos

  • Nuevo Miembro
  • *
  • Mensajes: 1
    • Ver Perfil
LA MOCHILA USANDO VUELTA ATRAS
« en: Miércoles 24 de Noviembre de 2010, 22:48 »
0
Buenos dias amigos en la facultad me dejaron un trabajo sobre implementar problemas en java usando backtracking(vuelta atras), como el problema de las N-Reinas, la asigacion de tareas, la pareja estable y ya los hice solo me falta el de la mochila usando este metodo la verda que no se como implementarlo con este metodo se hacerlo con voraz pero el profesor quiere usando vuelta atras. Algun experto en este metodo me puede ayudar a implementar este problema en java. Es para el viernes y se me han acumulado los trabajos de los demas curso. Una ayuda para solucionar este problema please.

fjmc22

  • Nuevo Miembro
  • *
  • Mensajes: 18
    • Ver Perfil
Re: LA MOCHILA USANDO VUELTA ATRAS
« Respuesta #1 en: Jueves 25 de Noviembre de 2010, 21:29 »
0
Aqui lo tienes, espero que te sirva:


Código: Java
  1. public class Mochila_0_1
  2. {
  3.    public static int mochila_0_1 (int[] ps, int[] bs, int c) {
  4.       int[] solParcial = new int[ps.length];
  5.       int[] solOptima = new int[ps.length];
  6.       int bOpt = buscar01 (ps.length-1, 0, c, 0, solParcial, solOptima, -1, ps, bs, c);
  7.       imprimir (solOptima);
  8.       return bOpt;
  9.    }
  10.    private static int buscar01 (int n_1, int i, int p, int b, int[] solParc,
  11.                                 int[] solOpt, int bOpt,
  12.                                 int[] ps, int[] bs, int c) {
  13.       for (int k=0; k<=1; k++) {
  14.          if (k*ps[i]<=p) {
  15.             solParc[i] = k;
  16.             int np = p - k*ps[i];
  17.             int nb = b + k*bs[i];
  18.             if (i==n_1) {
  19.                if (nb>bOpt) {
  20.                   bOpt = nb;
  21.                   for (int j=0; j<ps.length; j++)
  22.                      solOpt[j] = solParc[j];
  23.                }
  24.             }
  25.             else
  26.                bOpt = buscar01 (n_1, i+1, np, nb, solParc, solOpt, bOpt, ps, bs, c);
  27.             //int np = p + k*ps[i]; innecesarias porque en la primera iteración k==0
  28.             //int nb = b - k*bs[i];
  29.          }
  30.       }
  31.       return bOpt;
  32.    }
  33.    private static void imprimir (int[] v) {
  34.       for (int i=0; i<v.length; i++)
  35.          System.out.print (v[i]+" ");
  36.       System.out.println();
  37.    }
  38. }
  39.  
Páginas: [1]
« anterior próximo »