Rucksackproblem

[bisaflor]

Hallo,

ich habe folgende Aufgabe:

Betrachten Sie folgende Instanz des Rucksackproblems: Gegeben sind n = 4 Objekte mit

i 1 2 3 4
c_i 15 20 15 10
w_i 75 100 50 25 (sorry keine Ahnung wie/ob man eine schöne Tabelle erstellen kann)

sowie ein Rucksack mit Gewichtsbeschränkung W = 200.

(a) Bestimmen Sie alle zulässigen Lösungen für das binäre Rucksackproblem.

Meine Lösung: (1,1,0,1) , (1,1,0,0) , (1,0,1,1) , (1,0,1,0) , (1,0,0,1) , (1,0,0,0) , (0,1,1,1) , (0,1,0,1) , (0,1,1,0), (0,1,0,0) , (0,0,1,1) , (0,0,1,0), (0,0,0,1) , (0,0,0,0)

ist das korrekt (Notation etc. …)

(b) Bestimmen Sie alle optimalen Lösungen für das binäre Rucksackproblem

Meine Lösung: (1,1,01) und (0,1,1,1)

gleiche Frage wie bei (a)

mfg

[bisaflor]

/push

[Landei]

Nicht so ungeduldig…

Die Ergebnisse scheinen jedenfalls korrekt zu sein:

[0, 0, 0, 0] weight: 0 value: 0
[1, 0, 0, 0] weight: 75 value: 15
[0, 1, 0, 0] weight: 100 value: 20
[1, 1, 0, 0] weight: 175 value: 35
[0, 0, 1, 0] weight: 50 value: 15
[1, 0, 1, 0] weight: 125 value: 30
[0, 1, 1, 0] weight: 150 value: 35
[0, 0, 0, 1] weight: 25 value: 10
[1, 0, 0, 1] weight: 100 value: 25
[0, 1, 0, 1] weight: 125 value: 30
[1, 1, 0, 1] weight: 200 value: 45
[0, 0, 1, 1] weight: 75 value: 25
[1, 0, 1, 1] weight: 150 value: 40
[0, 1, 1, 1] weight: 175 value: 45

Für Tabellen u.s.w. kannst du übrigens das [****code]-Tag nutzen.

[spoiler]

Das Programm (benutzt etwas Bitschubserei wegen der Kürze, ginge aber auch noch lesbarer):

public class Knapsack {

    private static final int[] values = {15,20,15,10};
    private static final int[] weights = {75,100,50,25};
    private static final int MAX_WEIGHT = 200;

    public static void main(String[] args) {
        for (int i = 0; i < 16; i++) {
            int weight = 0;
            int value = 0;
            int[] bits = new int[4];
            for(int b = 0; b < 4; b++) {
                if (((i >> b) & 1) == 1) {  
                    weight += weights**;
                    value += values**;
                    bits** = 1;
                }
            }
            if (weight <= MAX_WEIGHT) {
                System.out.println(Arrays.toString(bits) + " weight: " + weight + " value: " + value);
            }
        }
    }
}

[/spoiler]

[bisaflor]

danke^^. ich habe immer Angst keine Antwort zu kriegen, weil das ziemlich wichtig für mich ist.

Dann noch eine weitere Frage: © Bestimmen Sie alle optimalen Lösungen für das ganzzahlige Rucksackproblem.

Antwort: (0,0,0,8) weil das 4.te Item den besten Nutzen/Gewicht Wert hat.

sogar mit extra java Programm, das ist wirklich nett (Gibt es eine Möglichkeit das in eclipse zu kopieren ohne die Zeilennummerierung)?

[L-ectron-X]

Scheint eine Browsereigenart zu sein. Im Firefox geht das auch ohne die Zeilennummer.
Ansonsten schreibt man sich dafür ein kleines Java-Programm.

[Dow_Jones]

@bisaflor

ist das korrekt (Notation etc. …)

Hi,
richtig ist die Lösung schon, aber - da du ja fragst - die Notation ist formal betrachtet nicht wasserdicht. Wenn die einzelnen Objekte in Form einer Menge vorgegeben sind dann ist eine Angabe à la (1, 0, 1, 1) eigentlich unzulässig. Mengen haben iirc per Definition keine Ordnung, daher kann man die Einsen und Nullen keinen Elementen zuordnen (ganz zu schweigen von der Frage was die Einsen und Nullen bedeuten sollen). Verstehen wird das zwar jeder - und an dieser Stelle wird auch häufig geschludert ohne das es irgendjemanden stört - aber formal korrekt ist es eben nicht.
Die korrekte Antwort auf die Aufgabenstellung wäre eine Menge von Mengen von Elementen. Um dies zu formulieren müsste man die einzelnen Elemente in irgendeiner Weise referenzieren können. Dazu fallen mir ad hoc drei mögliche Vorgehensweisen ein:

a) man listet die konkreten Elemente (Wertepaare, bestehend aus Nutzen/Gewicht) einer jeden Menge einfach auf
Lösung = { {(15, 75), (20,100)}, {(15, 75), (15,50), (10,25)}, … }

b) man benennt die einzelnen Elemente: „O0-On seien die Elemente aufsteigend nach ihrem Nutzen-Gewichts-Quotienten sortiert, Oi bezeichne dabei das Element mit dem i-t kleinsten Nutzen-Gewichts-Quotienten“. Dann könnte man in der in a) genannten Auflistung die solchermaßen definierten Elementnamen verwenden.
Lösung = { {O0, O1}, {O0, O2, O3}, … }

c) man definiert die Lösungsmenge gleich in mathematischer Ausdrucksweise:
Lösung = {X | blablabla…Quantoren…blabla*}

Falls es mehrere Elemente bzw. Wertepaare gibt die nach einer dieser Definitionen identisch sind dann sollte man ggf. explizit darauf hinweisen das jedes einzelne dieser Elemente/Wertepaare zu betrachten ist.

• hier kann @Bleiglanz uns sicher weiterbilden, falls der mal zufällig hier hereinschaut

[SlaterB]

über Notationen kann man immer streiten, hier aber bisschen arg streng,
ich habe nix gegen Extrempositionen, oft selber, aber dann kann man ja auch bisschen dagegen reden :

es wurde ‚binäres Rucksackproblem‘ genannt, die Links dazu im Netz sehen schon recht ähnlich aus,

Man nennt diesen Schritt Relaxation. Die Relaxation des binärren Rucksackproblems besteht darin, dass man die binären Variablen
xj,j= 1,2, …, n, durch beschränkte, aber stetige Variable ersetzt, für die 0≤xj ≤1 für j= 1,2, …, n gilt.
Dadurch geht das Rucksackproblem in ein einfaches lineares Programm über, […]

Opt.pdf

die 4 Objekte sind bereits in Posting 1 mit i=1-4 nummeriert, das ist vielleicht willkürlich (selbst-)gewählt,
wie bei b) letztlich auch herauskäme, aber von einer ungeordneten Menge kann man kaum sprechen

worauf sich das ‚binär‘ hierbei wirkllich bezieht, will ich mal nicht endgültig tippen,
aber ist schon recht passend, dass die denkbaren Lösungen allen Binärzahlen von 0000 bis 1111 entsprechen, 16 Werte

2 davon gehen nicht, 14 gehen, sind auch in Posting 1 genannt, fast ganz in absteigender Reihenfolge,
nur eine Vertauschung, die hätte ich am Anfang fast schon angemerkt

---

die 16 Werte sind auch im Pascalsches Dreieck – Wikipedia zu finden, 4er-Zeile, 16 = 1 + 4 + 6 + 4 + 1,
je eine Lösung ganz mit 1en, ganz mit 0en, je 4 Lösungen (4 über 1 sowie 4 über 3) mit drei 1en, oder nur einer 1,
6 Lösungen (4 über 2) mit zwei 1en

[Landei]

Hier noch einmal eine “ordentliche” Version, die das Bitschubsen vermeidet, und stattdessen ein BitSet verwendet. Die Lösungsliste wird sortiert, und alles ist etwas mehr OO:

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Knapsack {

    private static final int[] values = {15, 20, 15, 10};
    private static final int[] weights = {75, 100, 50, 25};
    private static final int MAX_WEIGHT = 200;

    private final BitSet bits;
    private int value;
    private int weight;

    private Knapsack(int i) {
        bits = BitSet.valueOf(new long[]{i});
        for (int b = 0; b < 4; b++) {
            if (bits.get(b)) {
                weight += weights**;
                value += values**;
            }
        }
    }

    public boolean isValid() {
        return weight <= MAX_WEIGHT;
    }

    @Override
    public String toString() {
        return String.format("%s weight: %d value: %d", bits.toString(), weight, value);
    }

    public static void main(String[] args) {
        List<Knapsack> list = new ArrayList<>();
        for (int i = 0; i < 16; i++) {
            Knapsack knapsack = new Knapsack(i);
            if (knapsack.isValid()) {
                list.add(knapsack);
            }
        }
        Collections.sort(list, Comparator.comparingInt((Knapsack k) -> k.value).reversed());
        list.forEach(System.out::println);
    }
}

Bei der Ausgabe werden jetzt die “gesetzten” Indizes (siehe BitSet.toString) und nicht mehr die Bits angegeben (was man aber leicht ändern könnte).

Natürlich müsste man etwas mehr Aufwand treiben, um größere Probleme noch lösen zu können (ist wahrscheinlich ein guter Kandidat für Branch-and-Bound-Strategien)

[Bleiglanz]

@Dow_Jones;124715

hier kann @Bleiglanz uns sicher weiterbilden, falls der mal zufällig hier hereinschaut

diesmal für den angeklagten: ist doch eh klar, dass ein Vektor betrachtet wird, da kann man sich die Bedeutung von (1,0,1,1) doch aus dem Kontext erschließen.

[bisaflor]

ich habe jetzt noch eine weitere Programmieraufgabe in java zum Thema Rucksackproblem.

Laden Sie sich Rucksack.zip herunter. Dieses Archiv enthält Klassen und Rucksack-Instanzen. Implementieren Sie einen Algorithmus, der alle Lösungen für das binäre Rucksackproblem erzeugt. Ihre Klasse soll das Interface SolverInterface implementieren.

Lassen Sie sich für jede mögliche Lösung ausgeben, ob sie zulässig ist und bestimmen Sie ihren Zielfunktionswert. Implementieren Sie dazu die Methoden isFeasible() und set() der Klasse Solution. Die anderen Methoden sollen unverändert bleiben.

Testen Sie Ihr Programm anhand der Probleminstanzen mit bis zu 20 Objekten. Protokollieren Sie die Zeiten.
Ihre Implementierung muss nicht mit größeren Instanzen umgehen können.

Meine erste Frage dazu: einen Algorithmus, der alle Lösungen erzeugt… da muss man dann gucken wieviele items es gibt und alle möglichen Vektoren als (0,1,0,1,0,…) dieser Länge erzeugen?

*** Edit ***

Falls meine Annahme stimmt, hier mein Algorithmus dazu

	
	private static void generate_sol(int length, String pref) {
		if(length == 0) {
			System.out.println(pref);
		}
		
		else {
		
		generate_sol(length-1, pref + "0");
		
		generate_sol(length-1, pref + "1");
		}
	
	}
	public static void main(String[] args) {
		generate_sol(50,"");
	}
	
}

*** Edit ***

ich habe jetzt einen vorläufigen Programmentwurf ich bin mir nicht sicher ob er korrekt ist zum Beispiel kriege ich bei dieser Probleminstanz zwar eine Ausgabe, aber auch eine NullPointerException

kop_Blatt1c scheint zu funktionieren, bin mir aber nicht sicher, ob es korrekt funktioniert…

noch eine andere Frage ist es möglich aus einem Eclipse Projekt aus den Java Quelltexdateien Textdateien zum ausdrucken zu exportieren??

[bisaflor]

/push *zu ungeduldig :rolleyes:

[CyborgBeta]

[QUOTE=bisaflor]
noch eine andere Frage ist es möglich aus einem Eclipse Projekt aus den Java Quelltexdateien Textdateien zum ausdrucken zu exportieren??[/QUOTE]

Drucken ist in Eclipse möglich, nur die Funktion finden…

Mal eine algemeine Frage, wo ich meine, es stimmt, das Rucksackproblem (binär):
gewichtet, gewertet, keine obere Grenze => nicht np,
gewichtet, gewertet, <= oder >= obere Grenze => nicht np,
gewichtet, gewertet, genaue /scharfe obere Grenze => np, aber auch:
gewichtet, gewertet, max./min. obere Grenze => np,
stimmt’s?

Sehr “naiv”, könnte man es auch so machen (4 Objekte zur Auswahl):

for (int i = 0; i < 16; i++) {
  if(isValid(i)) {
    if(isCompl(i)) {
      if(isMin(i) /* or isMax(i) */) {
        solutions.add(i);
      }
    }
  }
}
printSlt(solutions);```

Grüße

[bisaflor]

Meinst du mit “keine obere Grenze” das der Rucksack kein Gewichtsmaximum hat?
ich glaube nicht das das Sinn macht

mfg

[CyborgBeta]

Sry, ich muss mir erst “mehr” über dynamische Programmierung /Algos durchlesen, um das alles zu verstehen, es ist heute schon stressig gewesen. Aber jmd. kann dir sicher helfen, imho.
Grüße

[bisaflor]

kein problem^^

[Sen-Mithrarin]

[ot]Auch wenn ich hier und da auch gerne mal pushe, aber meinst du nicht auch dass zu der Zeit 13:15 - 16:15 (Wartezeit 3 h) und 14:15 - 16:45 (Wartezeit 2 1/2 h) in einem Forum in dem die meisten aktiven Member berufstätig sind schlicht und einfach keiner da ist der helfen kann, zu mal es ja schon ein nicht ganz so einfaches Thema ist, vor allem wenn man von sowas erstmal so gar keinen Plan hat …[/ot]

[bisaflor]

ja stimmt. Darüber hatte ich nicht nachgedacht

[SlaterB]

zu ‚allen möglichen Lösungen‘ ist wie immer und überall zu sagen, dass sie nicht unbedingt alle gleichzeitig in einer List oder ähnlich vorliegen müsssen,
man kann sie auch nacheinander im Programmablauf haben, und dann jeweils die Ausgabe machen

etwa bei if (length == 0) in generate_all_solutions() gleich verarbeiten,

bis zu 20 Elementen aus der Aufgabenstellung wird deine Liste + der Arbeitsspeicher aber nicht überfordert sein, 50 aus deinem Beispiel wären aber zuviel…

---

kop_Blatt1c.zip funktioniert mit rucksack0010.txt,
hast du zu der angesprochenen NullPointerException noch eine konkrete Frage?

---

man kann in Java in Textdateien schreiben, die Suche dafür lautet ‚java textdatei schreiben‘

Varianten sind zahlreiche über die Java-Versionen, unterschiedlicher try-catch-Overhead,
Probleme mit Zeilenumbrüchen je nach Betriebssystem

was einfaches wie
Javabeginners - In Textdatei schreiben
ist ein guter Anfang

[bisaflor]

ne, die NullPointerException konnte ich lösen. Das man in eine Textdatei schreiben kann weiss ich. Ich meinte aber eher das man die Quelltext java Dateien einfach als .txt oder so exportieren kann, weil ich auch einen Ausdruck abgeben muss. Ich hab mir da aber jetzt so beholfen, dass ich einfach per copy paste in einen Texteditor kopiert habe, das geht ja auch einfach. Bei 50 Lösungen wäre der Arbeitsspeicher überfordert, 50 klingt eigentlich nach wenig?

[SlaterB]

bei 50 Variablen/ Items

4 → 2^4 = 16 Lösungen
10 → 2^10 = 1024 Ausgaben in deinem Programm,
20 als Maximum der Aufgabe → 2^20 = 1024^2 ~ 1 Mio./ MB kein Problem für Liste/ Arbeitsspeicher,
wenn auch Ausgabe in Konsole vielleicht nicht mehr sinnvoll, in Datei noch denkbar

50 → 2 ^50 = 1024^5 > 1 Billiarde bzw. Petabyte, das ist doch etwas zuviel des Guten
wobei nacheinander zu verarbeiten für Suche nach den wenigen guten Lösungen noch vorstellbar ist,
nur nicht alles gleichzeitig in einer Liste halten wollen

---

.java-Dateien sind fast genausogut wie .txt
ein Tool zum Export/ Formatierung in txt, evtl. eine Datei, kenne ich nicht

tröstend ist vielleicht, dass das bei wenigen Dateien schnell von der Hand geht,
bei vielen andererseits auch kaum mehr sinnvoll ist, dann auch ruhig Menge von .java-Dateien abliefern