Programación General > Java

 LA MOCHILA USANDO VUELTA ATRAS

(1/1)

jeamcarlos:
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:
Aqui lo tienes, espero que te sirva:



--- Código: Java ---public class Mochila_0_1{   public static int mochila_0_1 (int[] ps, int[] bs, int c) {      int[] solParcial = new int[ps.length];      int[] solOptima = new int[ps.length];      int bOpt = buscar01 (ps.length-1, 0, c, 0, solParcial, solOptima, -1, ps, bs, c);      imprimir (solOptima);      return bOpt;   }   private static int buscar01 (int n_1, int i, int p, int b, int[] solParc,                                int[] solOpt, int bOpt,                                int[] ps, int[] bs, int c) {      for (int k=0; k<=1; k++) {         if (k*ps[i]<=p) {            solParc[i] = k;            int np = p - k*ps[i];            int nb = b + k*bs[i];            if (i==n_1) {               if (nb>bOpt) {                  bOpt = nb;                  for (int j=0; j<ps.length; j++)                     solOpt[j] = solParc[j];               }            }            else               bOpt = buscar01 (n_1, i+1, np, nb, solParc, solOpt, bOpt, ps, bs, c);            //int np = p + k*ps[i]; innecesarias porque en la primera iteración k==0            //int nb = b - k*bs[i];         }      }      return bOpt;   }   private static void imprimir (int[] v) {      for (int i=0; i<v.length; i++)         System.out.print (v[i]+" ");      System.out.println();   }} 

Navegación

[0] Índice de Mensajes