import java.util.ArrayList;
import java.util.Scanner;

public class Mochila {
    /*
    * Clase que representa un mochila en la cual se podra cargar Objetos
    * Atributos: maxPeso, valorTransportado, pesoOcupado, ObjetosDisponibles y ObjetosCargados
    * Metodos Importantes :
    *       Constructor: Instancia una mochila y le asigna un peso maximo;
    *       cargarMochilaEficientemente: Carga la mochila con los objetos disponibles;
    *       fillMochila: Clase helper de cargarMochilaEficientemente que rellena el ArrayList con los objetos cargados.
    * */
    private int maxPeso;
    private int valorTransportado = 0;
    private int pesoOcupado = 0;
    ArrayList<Objeto> objetosDisponibles;
    ArrayList<Objeto> objetosCargados;

    public Mochila(int maxPeso){
        this.maxPeso = maxPeso;
        this.objetosDisponibles = new ArrayList<Objeto>();
        this.objetosCargados = new ArrayList<Objeto>();
    }

    public float getMaxPeso() {
        return maxPeso;
    }

    public void setMaxPeso(int maxPeso) {
        this.maxPeso = maxPeso;
    }

    public int getValorTransportado() {
        return valorTransportado;
    }

    public void setValorTransportado(int valorTransportado) {
        this.valorTransportado = valorTransportado;
    }

    public int getPesoOcupado() {
        return pesoOcupado;
    }

    public void setPesoOcupado(int pesoOcupado) {
        this.pesoOcupado = pesoOcupado;
    }

    public void cargarMochila(int value, int peso){
        objetosDisponibles.add(new Objeto(value, peso));
    }

    public void imprimirObjDispobibles(){
        for(Objeto obj: objetosDisponibles){
            System.out.print("[val: "+obj.getValue()+", peso: "+obj.getPeso()+"]-");
        }
        System.out.println();
    }

    public void imprimirObjCargados(){
        for(Objeto obj: objetosCargados){
            System.out.print("[val: "+obj.getValue()+", peso: "+obj.getPeso()+"]-");
        }
        System.out.println();
    }

    private void fillMochila(String values){
        for(int i=0;i<values.length();i++){
            objetosCargados.add(objetosDisponibles.get((Character.getNumericValue(values.charAt(i)))));
            pesoOcupado += objetosCargados.get(i).getPeso();
        }
    }

    private static int max(int i, int j)
    {
        return (i > j) ? i : j;
    }


    private void cargarMochilaEficientemente()
    {
        objetosCargados.clear();
        pesoOcupado = 0;
        int[] dp = new int[maxPeso + 1];
        String[] flags = new String[maxPeso + 1];
        for(int i=0;i<maxPeso+1;i++){
            flags[i] = "";
        }

        for(int i = 0; i <= maxPeso; i++){
            String temp2="";
            for(int j = 0; j < objetosDisponibles.size(); j++){
                if(objetosDisponibles.get(j).getPeso() <= i){
                    int temp = dp[i];
                    dp[i] = max(dp[i], dp[i - objetosDisponibles.get(j).getPeso()] +
                            objetosDisponibles.get(j).getValue());
                    if(!(dp[i] == temp)){
                        temp2 = ""+flags[i - objetosDisponibles.get(j).getPeso()]+j;
                    }
                }
            }
            flags[i] = temp2;
        }
        fillMochila(flags[maxPeso]);
        valorTransportado = dp[maxPeso];
    }



    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        System.out.println("Ingrese la capacidad maxima de su mochila en KG: ");
        int capacidad = in.nextInt();
        Mochila mochila = new Mochila(capacidad);
        int choice=0;
        int valor = 0;
        int peso = 0;
        boolean continuar = true;
        do{
            System.out.println("Peso Maximo: "+capacidad+
                    "\nValor Transportado: "+mochila.getValorTransportado()+
                    "\nPeso Ocupado: "+mochila.getPesoOcupado()+
                    "\n-------------------\n1 - Crear Objeto\n2 - Imprimir Objetos Disponibles\n3 - Imprimir Objetos de Mochila\n4 - AutoRellenar Mochila\n5 - Salir\nEntrada: ");
            try{
                choice = in.nextInt();
            }catch (Exception e){
                System.out.println("Entrada no validad");
            }
            switch (choice){
                case 1:
                    System.out.println("Ingrese el valor del objeto: ");
                    valor = in.nextInt();
                    System.out.println("Ingrese el peso del objeto: ");
                    peso = in.nextInt();
                    mochila.cargarMochila(valor, peso);
                    break;
                case 2:
                    mochila.imprimirObjDispobibles();
                    break;
                case 3:
                    mochila.imprimirObjCargados();
                    break;
                case 4:
                    System.out.println("Mochila Cargada!");
                    mochila.cargarMochilaEficientemente();
                    break;
                case 5:
                    System.out.println("Saliendo...");
                    try {
                        Thread.sleep(1000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    continuar = false;
                    break;
                default:
                    System.out.println("Eleccion no validad");
            }
        }while(continuar);
    }
}

class Objeto {
    /*
    * Clase que representa objetos que se pueden cargar en la mochila
    * Atributos: peso y valor
    * */
    private int peso;
    private int value;


    public Objeto(int value, int peso){
        this.value = value;
        this.peso = peso;
    }

    public int getPeso() {
        return peso;
    }

    public void setPeso(int peso) {
        this.peso = peso;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }
}