package mochila;
import java.util.ArrayList;
/**
* Guarda una lista con los distintos objetos disponible para meter en la mochila y otra lista con
* los objetos que voy introduciendo en la mochila.
*/
public class Mochila {
ArrayList objetos;
ArrayList mochila;
float pesoM;
/**
* Crea un objeto mochila con un peso maximo que le pasamos como parametro.
* Este valor sera el valor maximo de peso que se podra alcanzar cuando metemos
* objetos en la mochila
* @param peso Peso maximo de la mochila.
*/
public Mochila(float peso) {
objetos = new ArrayList();
mochila = new ArrayList();
pesoM = peso;
}
/**
* Mete en la mochila el objeto que esta en la posicion n de la lista de objetos
* disponibles. Ademas lo marca como usado con el atributo usado del objeto.
* @param n Posicion del objeto en la lista de objetos.
* @return Si pudo meterlo o no.
*/
public boolean meterMochila(int n){
Objeto o = (Objeto)objetos.get(n);
if (o==null) return false;
o.setUsado(true);
mochila.add(o);
return true;
}
/**
* Metodo para saber el valor total de los objetos que llevamos introducidos en
* la mochila.
* @return Valor actual de la mochila.
*/
public float getValor(){
int n=mochila.size();
float total=0;
for (int j=0;j<n;j++)
total+=((Objeto)mochila.get(j)).getValor();
return total;
}
/**
* Extrae el ultimo elemento de la mochila. Se utiliza para cuando nos pasamos
* de peso eliminar el ultimo introducido.
* @return Si hay elemento para sacar o no.
*/
public boolean sacarMochila(){
Objeto o= (Objeto)mochila.remove(mochila.size()-1);
if (o==null) return false;
o.setUsado(false);
return true;
}
/**
* Metodo para saber cual es el peso total de los objetos que llevamos introducidos en la
* mochila.
* @return El peso actual de la mochila.
*/
public float cuantoPesa(){
int n=mochila.size();
float total=0;
for (int j = 0; j<n;j++)
total+=((Objeto)mochila.get(j)).getPeso();
return total;
}
/**
* Copia nuestra mochila en otra, para poder guardar una posible solucion al problema.
* @param l Lista donde voy a copiar la mochila.
*/
public void clonarMochila(ArrayList m){
m.clear();
for (int j=0;j<mochila.size();j++){
m.add(mochila.get(j));
}
}
/**
* Metodo que se usa para despues de calcular la lista optima asignarsela a nuestra mochila
* @param l Lista optima de objetos.
*/
public void setMochila(ArrayList m){
mochila=m;
}
/**
* Añade un objeto a la lista de objetos disponibles para meter en la mochila.
* @param nombre Nombre del objeto.
* @param peso Peso del objeto.
* @param valor Valor del objeto.
*/
public void añadirObjeto(String nombre,float peso, float valor){
Objeto nuevo = new Objeto(nombre,peso,valor);
objetos.add(nuevo);
}
/**
* Metodo para realizar todas las posibles combinaciones que podemos hacer con
* los objetos y quedarnos con el de mayor valor. Se usa backtracking todas las
* soluciones para hacer los calculos.
* @param sol Lista con la posible solucion al problema.
* @param valor Valor de la lista sol.
*/
public void calcularBacktracking(ArrayList m, float valor) {
int j = 0;
do {
Objeto o = (Objeto) objetos.get(j);
if (!o.getUsado()) {
meterMochila(j);
if (valor <= getValor() && cuantoPesa()<= pesoM) {
clonarMochila(m);
valor = getValor();
}
calcularBacktracking(m, valor);
sacarMochila();
}
j++;
}
while (j < objetos.size());
}
/**
* Crea una cadena con los objetos introducidos en la mochila.
* @return String con los objetos de la mochila.
*/
public String toString(){
String cadena="";
Objeto o;
if (mochila.isEmpty()) return "Mochila Vacia.";
for (int j = 0;j<mochila.size();j++){
o = (Objeto)mochila.get(j);
cadena = cadena + " " + o.toString();
}
cadena = cadena + "nLibre: " + (pesoM-cuantoPesa());
return cadena;
}
/**
* Imprime por pantalla los nombres y atributos de los objetos introducidos en la mochila
*/
public void toString2(){
Objeto o;
for (int j = 0;j<objetos.size();j++){
o = (Objeto)objetos.get(j);
System.out.println(" NOMBRE: " + o.getNombre() + " PESO: " + o.getPeso() + " VALOR: " + o.getValor());
}
}
}
A continuacion mostramos el codigo de la clase Main:
package mochila;
import java.util.ArrayList;
import java.io.*;
/**
* Clase Main de la aplicacion que crea un objeto mochila y llama a los metodos
* para realizar los calculos.
*/
public class Main {
BufferedReader entrada=new BufferedReader(new InputStreamReader(System.in));
/**
* Constructor de la clase Main. Aqui se realizan todos las llamadas a los
* metodos de la mochila pra realizar los calculos.
*/
public Main() {
Mochila m=null;
m = new Mochila(35);
m.añadirObjeto("Chubasquero",30,12);
m.añadirObjeto("Movil",20,20);
m.añadirObjeto("Radio",12,20);
m.añadirObjeto("Linterna",10,90);
m.añadirObjeto("Navegador",20,30);
System.out.println("nLos objetos y sus valores introducidos en este ejemplo son:n");
m.toString2();
ArrayList solucion = new ArrayList();
m.calcularBacktracking(solucion,Integer.MIN_VALUE);
m.setMochila(solucion);
System.out.println("nSolucion:n" + m);
}
public static void main(String[] args) {
Main main1 = new Main();
}
