AuK/Greedy-Algorithmen SS10/JavaBeispiel

Wiki-Quelltext dieser Seite.

<language>Java</language>
<run id="4bd6870ce3fa6">
ArrayList KandidatenListe=new ArrayList();
ArrayList ResultatenListe= new ArrayList();

int c=0;
int size=0;

c = Integer.parseInt(JOptionPane.showInputDialog(null, "Bitte Kapazität eingeben:","10"));
size = Integer.parseInt(JOptionPane.showInputDialog(null, "Bitte Größe der Kandidatenliste eingeben:","10"));

for(int i=0;i<size;i++){
  int a = Integer.parseInt(JOptionPane.showInputDialog(null, "Bitte Kandidat "+i+" eingeben:","1"));
  KandidatenListe.add(a);    
}

/*Kernstück des Greedy-Algorithmus*/
//===============================================================================================================
for(int index=0;index<size;index++){                                   
  int a = KandidatenListe.get(index);
  while(a<=c){                                                
     c = c - a;
     ResultatenListe.add(a);       
  }
}

/*Prüfung ob mögliche Lösung richtig ist.*/
if(c==0){ 
   /*Ausgabe des ArrayList auf der Konsole*/
   System.out.print("{");
   for(int i=0;i<ResultatenListe.size();i++){
       System.out.print(ResultatenListe.get(i)+",");
   }
   System.out.println("}");
   System.out.println("Anzahl: "+ResultatenListe.size());
}else{
   System.out.println("!!!Kein Lösung gefunden!!!");
   System.out.println("Rest: "+c);
}
//===============================================================================================================
</run>