0

esto es lo que me piden la verdad ya me canse de estar intentando resolverlo esto es lo que me pide: Implementar una aplicación en java que lea un archivo de texto plano con la siguiente información: • los costos y beneficios de los 𝑛 artículos. • la capacidad de la mochila 𝐶. • Un vector binario (de ceros y unos) de longitud 𝑛 que representa la selección de artículos. La aplicación deberá decidir si la selección de artículos es factible o in-factible. De ser factible deberá calcular el beneficio aportado

la verdad es que despues de pensarlo tanto e optado mejor por pedir ayuda... porfas si me pueden dar una idea de como empezar o si alguien ya lo a resuelto me oriente.

anexo lo que tengo avanzado en cuanto a leer el documento de texto

package proyectofinal;

    import java.io.BufferedReader;
    import java.io.FileReader;



    public class MochilaProblema {

        public void leer(){  
    //String ruta = "C:\\Users\\ekt110\\Desktop\\mochila.txt";

           String fichero = "C:\\\\Users\\\\ekt110\\\\Desktop\\\\mochila.txt";
        String[][] arr = new String[4][4];
        int i=0;
        try {
          FileReader fr = new FileReader(fichero);
          BufferedReader br = new BufferedReader(fr);

          String linea;
          while((linea = br.readLine()) != null){
              System.out.println(linea);  //Aquí tenemos las líneas por separado
              arr[i++]=linea.split(";");

          }

           System.out.println(arr[1][1]);
          fr.close();
        }
        catch(Exception e) {
        //  System.out.println("Excepcion leyendo fichero "+ fichero + ": " + e);
        }
      }




        public static void main(String[] arcgs) {


            MochilaProblema mp = new MochilaProblema();
               mp.leer();


        }


    }

se supone el txt tendra lo siguiente pesnse en meterlo en un arreglo

100; capacidad de la moochila 40;30;50;10 beneficios 10;20;50;20 peso de los objetos

1
  • esos valores separados por ";" los deseas agregar en donde? o solo imprimirlos?
    – Jorgesys
    el 20 may. 2020 a las 3:53

2 respuestas 2

0

Por lo que veo, tu problema no es estrictamente el problema de la mochila, sinó un problema de satisfactibilidad, puesto que te dan una solución propuesta y no debes hacer más que comprobarla (y de paso valorarla).

No creo que el programa que muestras sirva de mucho, lo único que hace es cambiar el formato de los datos, a fichero a matriz cuadrada. Ese no es el problema.

package proyectofinal;

import java.io.BufferedReader;
import java.io.FileReader;

public class MochilaProblema {
    private int n;
    private boolean[] x;   // si x[i] -> objeto i está en mochila
    private double[] b; // beneficios
    private double[] c; // costos

    public void leer(){  
       try {
          String fichero = "C:\\Users\\ekt110\\Desktop\\mochila.txt";
          FileReader fr = new FileReader(fichero);
          BufferedReader br = new BufferedReader(fr);

          // se dice que en la primera linea del archivo hay los n beneficios
          String linea_beneficios = br.readLine();
          String[] beneficios = linea.split(";");

          // en la segunda los costos
          String linea_costes = br.readLine();
          String[] costos = linea.split(";");

           // en la tercera línea está la capacidad de la mochila, que llamamos k
          double k = Double.parseDouble(br.readLine());

          // y en la cuarta, la solución a verificar que supondremos un
          // vector de longitud n, sin puntoycomas;

          String vector = br.readLine()              

          // y ya hemos leído todos los datos, cerramos fichero
          fr.close();

          n = beneficios.length; // que se supone igual a costos.length y a vector.length()              
          x = new boolean[n];
          b = new double[n];
          c = new double[n];

          double z = 0.0;    // valor de la solución dada
          for (int i=0; i<n; i++) {
               x[i] = vector.charAt(i) == '1';
               b[i] = Double.parseDouble(beneficios[i]);
               c[i] = Double.parseDouble(costos[i]);

               if (x[i]) {
                   z = z + b[i];
                   k = k - c[i];
                   if (k<0.0) break;
               }
          }
          if (k<0)
              System.out.println("La solución propuesta no es factible");
          else 
              System.out.println("El valor de la solución propuesta es " + z);

    }
    catch(Exception e) {
    //  System.out.println("Excepcion leyendo fichero "+ fichero + ": " + e);
    }
  }

  public static void main(String[] args) {
        MochilaProblema mp = new MochilaProblema();
           mp.leer();
    }
}

Espero que sirva.

3
  • probare asi como planteas ya que bueno mas o menos asi lo estube pensando ayer muchas gracias
    – kripton
    el 20 may. 2020 a las 19:25
  • entonces no entiendo porqué te cansaste de intentar resolverlo...porque por lo que veo, ni siquiera aceptaste la respuesta... en fin, suerte!
    – carles
    el 20 may. 2020 a las 23:07
  • disculpa era nuevo en la plataforma e aceptado la respuesta, muchas gracias me salvaste cuando no sabia gran cosa de programación
    – kripton
    el 26 jun. 2021 a las 19:43
-1

En primer lugar, la realidad puede diferir de la teoría de este problema. Pongamos el ejemplo que se pone para explicar qué es el problema de knapsack. El máximo número de paquetes limitando la capacidad de la mochila por la cualidad peso total. En ese caso, cuantos más paquetes de menor peso se metan, más paquetes cabrán. Si se mete el primer paquete con peso 99% del peso admitido total, pocos paquetes más podrán entrar. Sin embargo, mi opinión es que luego esos paquetes que no caben en la mochila hay que llevarlos en la mano. Y yo prefiero llevar en la mano los que menos pesen, a llevar en la mano los que más pesen. Así que prefiero entrar en la mochila lo que más pese, aunque suponga menos cantidad.

Con esta explicación, lo que se hace patente es que a menor peso del paquete, menos capacidad total de paquetes se le quita a la mochila, y más paquetes restantes sigue siendo capaz de almacenar.

Esto no está comprobado matemáticamente. Es sólo lo que me dice la lógica.

Esto mismo aplicado a tu problema, se resuelve por una simple ordenación de rentabilidad de artículos. De más beneficio a menos beneficio. Para ello, se puede usar un ArrayList de objetos de tipo artículo. Y en la clase artículo se puede usar la interfaz comparable, junto con el método sort que compara 2 objetos.

Y ahora que los tienes ordenados lo que interesa meter no es N artículos con el máximo beneficio posible (metiendo primero el que más beneficio de, y siguiendo de más a menos). Sino que se pone un beneficio total, y el conjunto de más paquetes que más se aproxime sin pasarse a ese beneficio, es el conjunto que gana. Así pues, lo que hay que hacer es rellenar la mochila desde el artículo que menos beneficio de, porque ese es el que deja a la mochila con más capacidad de meter más artículos. Y continuar metiendo artículos hasta que, antes de meter un artículo, el beneficio total supere a la mochila. Y en ese caso, no meterlo. (esto último a mi me suena parecido a una condición de while o do while). do{ introducir artículo while (beneficio_articulo+beneficio_mochila

Bueno, hasta aquí supongo que es más o menos lógico y facil de llegar. Sin embargo, ahora resulta que lo que hay que tener en cuenta para meter un artículo u otro no es sólo contando con 1 única cualidad. Sino con 2 cualidades. Y en base al conjunto de las 2 cualidades, meter antes un artículo u otro.

Esas 2 cualidades (coste del artículo y beneficio del artículo) hacen un pack de cualidades, de una manera u otra. Sea como fuere, una vez hecho el pack, habrá que meter en la mochila primero el que menos valor tenga ese pack, para dejar más hueco en la mochila.

Así que, por último, lo único que te queda por decidir es cómo vas a crear ese pack de las 2 cualidades.

Puedes tener una cualidad primaria y una cualidad secundaria. En cuyo caso, como resultado final es que metes en la mochila por menor valor de cualidad primaria. Y en el último paquete a introducir puede que te quepan a elegir entre 2 o más antes de rebasar el máximo. En cuyo caso, si te da igual cual meter entre 2 o más artículos pues de todas formas será el último artículo, tendrás en cuenta la segunda cualidad.

Pero también puedes tener las 2 cualidades por igual. En cuyo caso, lo suyo es hacerse un índice coste-beneficio (el cual es el resultado de la suma entre coste y beneficio) Y meter en la mochila según ese índice, de menor a mayor.

Sin embargo, esto aunque es lo que resuelve el problema matemático, no es lo más lógico. Lo más lógico a la hora de seleccionar qué artículo seleccionar antes para vender en una tienda, debe ser el que de como división coste-beneficio más bajo. (para que ese índice sea bajo, el coste debe ser bajo y el beneficio alto. Algo que cuesta 1€ y se vende a 11€ (coste 1, beneficio 10) da un índice dividiendo de 0.1 y algo que cuesta 9€ y se vende a 10 da un índice de 9)

Esta no es una respuesta de java, es una respuesta logística de como resolver el problema. Aunque he dado pistas con el ArrayList de objetos artículos con 3 cualidades, coste, beneficio e índice coste-beneficio. (coste y beneficio deberían ser obligatorios de introducir en la creación del objeto). También como "extra" le podrías meter un método llamado setNombre que establezca si es una silla o un chupachups. Aunque eso de un poco igual.

La mochila será otro ArrayList, pues no sabes a la hora de crearla cuantos artículos vas a meter. Y de tu lista de artículos, debes de ir seleccionando por índice, así que lo suyo será ordenar ese ArrayList por orden según el índice. Con ayuda de la interfaz Comparable y con la ayuda del método sort. Y a la hora de programar sólo te queda decidir cómo construir ese índice según lo explicado arriba (yo usaría la suma, no la división. Lo que te piden es la resolución del problema de knapsack. No crear la lista de compra más rentable para llevar a vender a tu tienda. Al menos que uses cualidad-primaria y cualidad secundaria, en cuyo caso no usas indice ni sumando ni dividiendo ni nada. Seleccionas según la primeraria, y en el último artículo a introducir ves si puedes seleccionar entre varios, y si es así, seleccionas según la cualidad secundaria más baja).

1
  • Hola, varias de las publicaciones que has realizado en el sitio tienen este mismo formato, te sugerimos revises Cómo responder, hay que dar una solución o una opción para solucionar la pregunta planteada.
    – Jorgesys
    el 20 may. 2020 a las 13:37

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.