Alle Kombinationen aus ArrayList - Potenzmenge

[swerm]

Hi zusammen, bin seit längerem am suchen und langsam aber sicher am verzweifeln. Die Problemstellung ist eigentlich relativ einfach, allerdings macht mir die Umsetzung in Codeform sehr grosse Probleme. Es geht um das Rucksackproblem, daher habe ich eine gewisse Anzahl Objekte mit einer id, einem Wert und einem Gewicht erstellt. Nun möchte ich von allen möglichen Kombinationen das Gesamtgewicht und den Gesamtwert wissen.

z.B. habe ich 3 Objekte, {1, 2, 3}. Alle Möglichkeiten wären also {(1), (2), (3), (1,2), (1,3)... usw.}
Nun habe ich keine Ahnung wie ich alle diese Möglichkeiten "erzeuge". Die Objekte sind in einer ArrayList gespeichert. Wäre sehr froh wenn jemand helfen könnte! Hier Mal der bisherige Code:

//------------Code der Klasse Rucksack-------------------//
import java.util.ArrayList;
import java.math.*;

//Deklaration der Variabeln
public class Rucksack {
	private ArrayList<Objekt> objekte = new ArrayList<Objekt>();
	private ArrayList<Objekt> objekteInRucksack = new ArrayList<Objekt>();
	private int platz;
	private int gesamtwert;
	private int gesamtgewicht;
	private int bestwert;
	
//Konstruktor - Variabeln werden initialisiert
	public Rucksack(int platz){
		this.platz = platz;
		gesamtwert = 0;
		gesamtgewicht = 0;
	}
	
	//Objekte mit zufälligem Gewicht werden erzeugt
	public void erzeugeObjekte(){
		int i=0;
		int hoechstwert = 100;
		int hoechstgewicht = 100;
		int wert = 0;
		int gewicht = 0;
		
		for (i=0; i<50; i++){
			wert = (int) (Math.random()*hoechstwert+1);
			gewicht = (int) (Math.random()*hoechstgewicht+1);
			objekte.add(new Objekt(i, wert, gewicht));
		}
	}
	
	//Alle Objekte werden ausgegeben
	public void printAll(){
		for(Objekt obj : objekte){
			obj.print();
		}
	}
	
	//Alle Objekte die sich im Rucksack befinden werden ausgegeben
	public void printInRucksack(){
		for(Objekt obj : objekte){
			if(obj.getInRucksack() == 1){
				obj.print();
			}
		}
	}	
}


//------------------Code der Klasse Objekt----------------------------------

public class Objekt {
	int id;
	int wert;
	int gewicht;
	double verhaeltnis;
	int inRucksack;
	
	public Objekt(int id, int wert, int gewicht){
		this.wert = wert;
		this.gewicht = gewicht;
		verhaeltnis = wert / gewicht;
		inRucksack = 0;
		this.id = id;
	}
	
	public int getWert(){
		return wert;
	}
	
	public int getGewicht(){
		return gewicht;
	}
	
	public double getVerhaeltnis(){
		return verhaeltnis;
	}
	
	public void setInRucksack(int inRucksack){
		this.inRucksack = inRucksack;
	}
	
	public int getInRucksack(){
		return inRucksack;
	}
	
	public void print(){
		System.out.println("Objekt " + id);
		System.out.println("Gewicht: " + gewicht);
		System.out.println("Wert: " + wert);
		System.out.println("In Rucksack: " + inRucksack + "\n");
	}
}

Vielen Dank schon im Voraus für eure Hilfe!

 

[Fab1]

Hallo,

ich habe hier mal etwas Pseudocode, da ich es momentan nicht testen kann.

Dein Problem ist anscheinend, dass du nicht weißt wie du die Kombination erstellst? Versteh ich das richtig?

Ansich würde das mit 2 geschachtelten Schleifen gehen.

Nehmen wir mal an du hast die Zahlen 1,2,3,4,5

Am Anfang erstmal alle ausgeben, somit hast du schonmal die einzelnen Objekte.

Jetzt brauchst du natürlich noch die Kombinationen.

Diese wären folgende:

(1,2)(1,3)(1,4)(1,5)
(2,3)(2,4)(2,5)
(3,4)(3,5)
(4,5)

Man sieht schon, die Anzahl der Kombinationen nimmt stetig um eine ab.


Rein logisch ist es ja so: Du vergleichst das erste Objekt/Zahl mit jedem anderen, dass größer ist wie Sie selbst. Also 2,3,4,5

Bei dem zweiten Objekt/Zahl wieder genauso. Also 3,4,5

und so weiter.

Hier sieht man schon, dass die Lösung eine geschachtelte Schleife ist. Hier muss ich leider sagen, ich kann mich recht schlecht in solch geschachtelte Schleifen "eindenken" muss lieber alles sehen, was momentan aber nicht möglich ist.

Mein Pseudocode:

// Ich mach jetzt mal nur mit den Zahlen und nem Array mit Objekten ist es ja ähnlich.
String kombi = "";
int [] array = {1,2,3,4,5}

for(int i = 0; i<array.length(); i++){

      for(int x = 0; x<array.length(); x++){
          kombi = kombi + array[i] + ";" + array[x] // ob das so stimmt, ka :-)
      } 

   }
for(int r : array){
System.out.print(r + " ");
}

System.out.println(\n +kombi);

Wenn ich daheim bin, würde ich es testen. Wenn bis dahin keine bessere Lösung vorhanden ist.

Greez

 

[Marco13]

http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html#post646341 , PowerSetIterable

 

[swerm]

Hi, danke für die Antwort!
Diesen Ansatz habe ich auch schon durgedacht, allerdings sind in deinem Codebeispiel jeweils nur 2er Paare, ich brauche allerdings auch die 3er Paare, respektive bei n Einträgen im Array die "n"er Paare. D.h. ich müsste soviele ineinander geschachtelte For-Schleifen machen wie es Einträge im Array hat, was allerdings bei vielen Einträgen wenig sinnvoll ist, zumal das ganze noch variabel sein sollte.

Habe evt. Eine Lösung gefunden, die auf dem Binärsystem beruht, muss das ganze allerdings noch austesten. Falls es klappen sollte wird es natürlich geposted

 

[Fab1]

Ach, hat ich wieder nicht genug mitgedacht, tut mir Leid.

 

[Marco13]

Habe evt. Eine Lösung gefunden, die auf dem Binärsystem beruht

So wie das PowerSetIterable....?

 

[swerm]

Hi, sorry habe deinen Post doch glatt übersehen. Werde mir das Mal anschauen, wenn ich das nur kurz überfliege kapier ich noch ziemlich wenig von dem was in der Klasse geschieht. Aber vielen dank, ist wohl genau das was ich gesucht habe!

 

[Landei]

Das hier sollte alle Unter-Listen zurückgeben (ungetestet):

List<Integer> list = Arrays.asList(1,2,3,4);
for(int i = 0; i < 1 << list.size(); i++) {
    List<Integer> subList = new ArrayList<Integer>();
    for(int k = 0; k < list.size(); k++) {
        if ((i & (1 << k)) > 0) subList.add(list.get(k));
    }
    //tu was mit subList;
}