import javax.swing.*;
import java.awt.*;
import java.awt.event.ActionListener;
import java.awt.event.ActionEvent;

/**
 * User: Marcus Liwicki
 */

public class Rucksack extends JFrame implements ActionListener{
    // Anzahl der Elemente 
    private static final int n = 15;
    // Kapazität des Rucksacks
    private static final int c =15;
    //  n elemente
    static Item[] items = new Item[n];
    // ier werden die Lösungen für die Teilprobleme gespeichert
    static int[][] temporary_results = new int[n+1][c+1];
    static JButton b1 = new JButton("nehmen");
    static JButton b2 = new JButton("neue Werte");
    private boolean calculated = false;
    // Initialisierung der Variablen
    Rucksack(){
        super("0-1 Rucksackproblem");
        setSize(750,400);
        setResizable(false);
        getContentPane().setLayout(null);
        b1.setBounds(200,300,90,25);
        b1.setVisible(true);
        b1.addActionListener(this);
        getContentPane().add(b1);
        b2.setBounds(300,300,90,25);
        b2.setVisible(true);
        b2.addActionListener(this);
        getContentPane().add(b2);

        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        iniEl();
        setVisible(true);

    }
    public void iniEl() {
        /**
         * n Elemente erzeugen, mit Wer zwischen 1 und 9 und Gewicht zwischen 1 und 4
         */
        for (int i=0;i<n;i++){
            items[i] = new Item((int)(Math.random()*9+1),(int)(Math.random()*4+1));
        }
        repaint();
    }
    
    /**
     * Visualisierung
     */
    public void paint(Graphics g){
        super.paint(g);
        
        // die Elemente anzeigen mit ihren Werten V und Gewichten W:, X bedeutet dass sie
        // ausgewählt wurden.
        

        int accWert=0;
        int accGewicht=0;
        for (int i=0;i<n;i++){
            g.drawString("V: "+items[i].value,i*50+5,55);
            g.drawString("W: "+items[i].weight,i*50+5,70);
            g.drawString((items[i].selected) ? "X" : "-",i*50+5,90);
            if (items[i].selected){
                accWert+=items[i].value;
                accGewicht+=items[i].weight;
            }
        }

        // Informationen über das Ergebins
        g.drawString("Elemente:  "+n,7,130);
        g.drawString("Kapazität: "+((calculated) ? accGewicht+"" :"0")+" von " +c,7,150);
        /**
         * temporary_results[n][c] enthält die Lösung für das gesamte Rucksackproblem
         */
        g.drawString("max. Gewinn    : "+((calculated) ? accWert+"" : " noch nicht ermittelt"),7,170);


    }

    public static void main(String args[]){
        new Rucksack();
    }
    // Wird ausgeführt wenn der nehmen Knopf geklickt wird
    public void actionPerformed(ActionEvent e) {
    	if(e.getSource()==b1) {
	        solve();
    	    repaint();
    	} else {
    		iniEl();
    	}
    }
    // Lösung in O(n*c)
    private void solve(){
        // Von unten nach oben die Teillösungen bestimmen für
        // R(0,0) -> R(0,1) ...

        for (int i=0;i<=n;i++)
            for (int h=0;h<=c;h++){
                if (i==0)
                    temporary_results[i][h]=0;       // enthält 0en wenn i=0, d.h. keine Elemente mehr sind
                else if (items[i-1].weight>h)
                // wenn das i-te Element zu groß ist und nicht in den Rucksack passt, ist die Lösung
                // die gleiche, wie die ohne das i-te Element aber der gleichen Kapazität
                // items[i-1] stellt hierbei immer das i-te Element dar (da i1 = 0)
                    temporary_results[i][h]=temporary_results[i-1][h];
                else
                // ansonsten ist die Teillösung als maximum dieser beiden Lösungen zu definieren
                    temporary_results[i][h]=Math.max(temporary_results[i-1][h],temporary_results[i-1][h-items[i-1].weight]+items[i-1].value);
            }

        /**
         * bestimmen welche Gegenstände, die im Ergebnis genommen werden.
         */
        int h = c;
        for (int i=n;i>=1;i--){
            if (temporary_results[i][h] == temporary_results[i-1][h])
                items[i-1].selected=false; // i-tes Item nicht genommen
            else{
                items[i-1].selected=true;       // i-tes Item genommen
                h-=items[i-1].weight;
            }
        }

        // dient der GUI zum anzeigen der berechneten Werte!
        calculated=true;
    }

}

class Item {
    ImageIcon pic = null;
    int value =0;
    int weight =0;
    boolean selected;       // ausgewählt

    Item(int v, int w){
        value = v;
        weight = w;
        selected=false;
    }

}