Backtracking Waage Problem

[dutchman79]

In unsere Algortihmen Vorlesung sollen wir folgendes Problem mit Backtracking lösen.

Man hat eine Balkenwaage und folgende Gewichte: 1, 3 ,8 und 20 Gramm.
Ausserdem ein Artikel der 16 Gramm wiegt.

Aufgabe ist es nun, alle möglichen Verteilungen der Gewichte auf die Waagschale
darauf zu testen, ob der Artikel gewogen werden kann, d.h. ob es eine oder mehrere
Kombinationen aus Artikel und Gewichten gibt, sodass die Waage im Gleichgewicht ist.
Geben Sie alle Lösungen aus.

Also gedanklich würde ich so vorgehen dass ich mein 16 Gramm Artikel links auf die Waage stelle dann einen Art Baum erzeugen, indem ich das erste Gewicht ( 1Gramm) entweder links drauf setze, nicht drauf setze oder rechts.
usw.

Letzendlich durchlaufe ich alle Möglichkeiten und suche die raus wo die Differenz zwischen linke und rechte Seite gleich Null ist ---> balanciert und Artikel kann gewogen werden ...

Aber jetzt: welche Ansätze ??

 

[F.S.WhiTeY]

Na der Ansetz ist Backtracking. Ich würde Backtracking zum verdeutlichen immer als Brettmuster darstellen. 4x5 oder 5x4 Felder, oben links ist die Eins und unten Rechts ist die 20. Dieses Brett gehst du mit allen möglichen wegen ab und merkst dir jeden Weg der 16 ergibt. Wenn du einen ungültigen Schritt gemacht hast ( weg > 16 ) musst du ihn rückgängig machen.

Schau dir mal das Labyrinth-Problem an, expliziet den Backtracking-Ansatz. Den kannst du für deine zwecke umbauen.

 

[XHelp]

Dieses Brett gehst du mit allen möglichen wegen ab und merkst dir jeden Weg der 16 ergibt. Wenn du einen ungültigen Schritt gemacht hast ( weg > 16 ) musst du ihn rückgängig machen.

In diesem Fall muss man es etwas anders angehen, denn du kannst 16+1+3 auf die eine Seite und 20 auf die andere Packen und das wäre richtig.

 

[XHelpistOpLol]

Man hat eine Balkenwaage und folgende Gewichte: 1, 3 ,8 und 20 Gramm.
Ausserdem ein Artikel der 16 Gramm wiegt.

Die fetten Gewichte draufpacken, bis das Gewicht 16 oder mehr Gramm ist. Ist es mehr, das nächstkleinere Gewicht wählen usw.

 

[Marco13]

usw.

uww? (Und wie weiter?)

 

[XHelpistOpLol]

Backtracking kein Begriff?

Let me google that for you

 

[Marco13]

Doch, aber das, was du beschrieben hast läßt sich nicht als Backtracking erkennen. (Ich gehe (schon wegen des Namens) davon aus, das du ein Troll bist, und werde darauf nicht weiter eingehen).

 

[dutchman79]

Danke schonmal für eure Beiträge.

Unser Prof meinte dass die Schwierigkeit bei solchen Problemen drin besteht um die entsprechende Baumstruktur zu erkennen.
Wenn mann diese erstmal hat, entspricht jedes Blatt letzendlich eine Möglichkeit um die Waage zu bestücken.

Dann müsste man nur noch mit einer Breiten- oder Tiefensuche die ganzen Blätter durchgehen und die Blätter die die Bedingung Gewicht links - Gewicht rechts =0 erfüllen ausgeben.

Genau diese Struktur in Java umsetzen finde ich sehr schwierig. ( Abstrakte Datenstrukturen im Allgemeinen eigentlich)

Hätte jemand hierfür einen konkreten Ansatz ?

 

[Empire Phoenix]

Object mit zwei referenzen auf links und rechts ? Dazu dann noch welcehs gewicht hinzugefügt wird.
Beim durchlaufen mit Tiefensuche dann:
Bei jeden blatt das erreichtw ird prüfen ob gewicht > 16 wenn ja einen hoch gehen und das letzte hinzugefügte gewicht entfernen. sonst den baum dynamisch weiter bauen lassen.

 

[Marco13]

Hm. Ich bin nicht sicher, ob man den Baum explizit als Datenstruktur aufbauen muss. Üblicherweise wird der ja "implizit" durch die Funktionsaufrufe gebaut. GANZ abstrahiert ist das sowas wie

void solve(Problem problem)
{
    if (problem.isSolved()) reportSolution();
    else
    {
        for (each possible modification)
        {
            doModification(problem); // Hier: Füge ein Gewicht auf einer der beiden Seiten hinzu 
            solve(problem);
            undoModification(problem); // Nimm das Gewicht wieder weg
        }
    }
}

 

[XHelpistOpLol]

Dafür bräuchte man kein Backtracking, wenn man sich im Methodenrumpf nicht die zuletzt gemachte Änderung merkt.

Doch, aber das, was du beschrieben hast läßt sich nicht als Backtracking erkennen. (Ich gehe (schon wegen des Namens) davon aus, das du ein Troll bist, und werde darauf nicht weiter eingehen).

Wenn ich keine Ahnung hätte, würde ich auch nicht drauf eingehen, LoL

 

[F.S.WhiTeY]

Also irgendwie verwirrt mich nun die Aufgabenstellung.... man soll doch laut des ersten posts garnicht links und rechts gewichte verteilen....

Es soll ein artikel geworgen werden:

Aufgabe ist es nun, alle möglichen Verteilungen der Gewichte auf die Waagschale
darauf zu testen, ob der Artikel gewogen werden kann, d.h. ob es eine oder mehrere
Kombinationen aus Artikel und Gewichten gibt, sodass die Waage im Gleichgewicht ist.
Geben Sie alle Lösungen aus.

Also sind bei einem 16 Gramm artikel links IMMER 16 Gramm und man muss schauen welche kombinationen mann ziehen kann.

Bei 16 Gramm kann ich die gewichte 17-20 aueßer acht lassen und tesete alle anderen kombinationen durch.

Also ich würde, wenn ich tomaten abwiegen will, zu den tomaten keine gewichte stellen.


Hab ich nun was nich richtig verstanden ?

 

[XHelp]

Hab ich nun was nich richtig verstanden ?

Meiner Meinung nach ja. Der Teil:

ob es eine oder mehrere Kombinationen aus Artikel und Gewichten gibt, sodass die Waage im Gleichgewicht ist

ist für mich recht eindeutig

 

[muckelzwerg]

Es gibt doch drei Varianten. Entweder "alles" ist gewollt, also auch nur Gewichte und gar kein Artikel auf der Waage. Das wird es wohl nicht sein.
Oder es geht darum auf der einen Seite nur den Artikel zu haben und auf der anderen Seite eine/alle Kombinationen der Gewichte für den Ausgleich der Waage zu suchen.
Und dazwischen gibt es noch die Variante, dass man die Gewichte auch auf die Seite mit dem Artikel stellen kann.
Bsp.: Artikel mit 5 kg. Gewichte mit 7kg und 2kg. Nur mit der einen Seite kann man das nicht abwiegen. Legt man aber 7 links und Artikel + 2 rechts, ist die Waage ausgeglichen. Also lässt sich eine Gleichung bilden 7 = A + 2 und damit das Gewicht ermitteln.

 

[F.S.WhiTeY]

Nagut, ich wäre da wahrscheinlich reingefallen und hätte lediglich die kombinationen zum wiegen des artikels gesucht. Für mich war das halt nicht eindeutig.

Ich muss auch zugeben ,dass ich mich verlesen habe. 1,3, UND 20 Gramm ist nicht wirklich das gleiche wie 1 bis 20 Gramm. Dann macht es auch Sinn 16 + 3 + 1 = 20 als links und rechts anzunehmen.

Von daher ist meine gepostete herangehensweise wirklich nicht empfehlenswert.

Ich würde allerdings kein baum draus machen sondern es rein aus der mengenlehre übernehmen. Es gibt sicherlich einen Algorithmus der Potenzmengen bildet. Oder man schreibt sich einen, das ist nun auch nicht soooo schwer.

Ich würde zwei Potenzmengen bilden, eine für die Menge inklusieve des Artikels und eine exklusiev des artikels.

bei {1,3,8,20} sind das 2^4 also 16 varianten, mit dem Artikel 2^5 = 32 möglichkeiten.

Die kann man nun durchgehen und/oder sie sogar als Baum aufbauen.

Nur wie ich das backtracking angehen würde ist mir gerade noch nicht ganz klar da muss ich noch nen moment drüber nachdenken.

Ich neige allerdings auch dazu, zu kompliziert zu denken ^^ von daher kann es wehsentlich einfachere ansätze geben. Allerdings hätten wir damit schon mal einen Baum

EDIT: Mann sollte natürlich bei der menge mit dem artikel alle kombinationen außer acht lassen, welche nicht den artikel enthalten. sonst wäre das sinnfrei.

LG

WhiTeY

 

[XHelp]

Naja, einfach mal so Potenzmengen aufbauen kannst du nicht, denn Teils ist dann der Artikel gar nicht mit dabei, teils werden gleiche Gewichte auf beiden Seiten verwendet. Und alle Kombinationen aufbauen und dann noch selektieren... hm. Da kannst du direkt die richtigen aufbauen. Darüber hinaus hat man dann bei der Abbruchsbedingung größeren Spielraum, z.B.: "Auf der Linken Seite liegen 30g, wenn die Summe der übrigen Gewichte <30g ist, dann braucht man auch nicht versuchen eine passende Kombination zu finden"

 

[muckelzwerg]

Die Seiten braucht man nicht unterscheiden, wenn es zu umständlich wird. Stattdessen kann man auch die Gewichte negativ ansetzen.
Also statt 7 = A + 2 wird eben gleich 7 - 2 = A gewogen.
Der wechselseitige Ausschluss von +Xkg und -Xkg würde sich ganz gut in ein Suchverfahren/Backtracking einbauen lassen.

Allerdings ist sowas doch der totale Overkill. Zum einen steckt da wohl im Kern sowas wie das Binpacking-Problem dahinter und es lässt sich deshalb kein effizienter Algorithmus finden. Zum anderen SOLL ja nicht bloß eine, sonder jede Lösung gefunden werden.
Dementsprechend MUSS man sowieso alle Kombinationen ausprobieren.
Aufwändige Konstruktionen von Bäumen etc. kann man sich spaaren. Stattdessen kann man alle "X aus Y" Kombinationen bauen und die "straightforward" durchtesten.
Mit negativen Gewichten und den eingeschränkten Kombinationen (4 aus 8 vielleicht? ...) wird das noch genug Arbeit.
Aber vielleicht geht es ja auch noch "simpler". Stichwort "Summenformel".

 

[XHelpistOpLol]

    public static boolean g16(List<Integer> li, int g, final int gmax) {
        if (g >= gmax) {
            return g == gmax;
        }

        final int[] gs = {20, 8, 3, 1};
        for (int i = 0; i < gs.length; i++) {
            li.add(gs[i]);
            if (g16(li, g + gs[i], gmax)) {
                return true;
            }
            li.remove(li.size() - 1);
        }

        return false;
    }

 
        List<Integer> li = new LinkedList<Integer>();
        g16(li, 0, 16);
        System.out.println(li);

li: Gramm-Ergebnisliste
g: Gramm-Summe der vorher aufgerufenen Methoden
gmax: Ziel
gs: Gramm-Array (könnte auch Parameter sein, Klassenvariable oder sonstwas); wenn umgekehrt sortiert, kleinste Anzahl Gramm
g16: rek. Met.

 

[XHelp]

...code...

Schon mal selber ausprobiert? Das ist in jeder hinsicht falsch.

 

[muckelzwerg]

XHelpistOpLol erzähl doch mal ein bisschen was dazu. Wieviele Lösungen gibt es? Wie lauten sie? Legst Du die Gewichte auf beide Seiten? ...

 

[XHelpistOpLol]

Schon mal selber ausprobiert? Das ist in jeder hinsicht falsch.

Lol, schließ dich doch Marco13 an, als Mod kannst '0falsche' Beiträge ja jetzt löschen.

@muckelzwerg: von allen Lösungen war nicht die Rede oder

 

[muckelzwerg]

Doch klar.

Aufgabe ist es nun, alle möglichen Verteilungen der Gewichte auf die Waagschale
darauf zu testen, ob der Artikel gewogen werden kann, d.h. ob es eine oder mehrere
Kombinationen aus Artikel und Gewichten gibt, sodass die Waage im Gleichgewicht ist.
Geben Sie alle Lösungen aus.

 

[XHelp]

Lol, schließ dich doch Marco13 an, als Mod kannst '0falsche' Beiträge ja jetzt löschen.

@muckelzwerg: von allen Lösungen war nicht die Rede oder

Und seit wann bin ich ein Mod? :bahnhof:
Dein Programm liefert als Ausgabe:

[8, 8]

Wo zauberst du denn das 2te 8er Gewicht her? Und bei einer Balkenwaage kann man auf beide Seiten Gewichte draufpacken.

 

[XHelpistOpLol]

Ich hab die Aufgabe gar nicht richtig verstanden. Aber dann eben Gewichte auf beiden Seiten.

Wenn es unendl. Gewichte gibt, gibt es auch unedl. Lösungen.. ..
Deshalb müssen es endl. Gewichte sein, die verfügbar sind oder die insgesamt in der Lösung vorkommen dürfen.

Wird prinzipiell genauso implementiert. Man trifft in der Methode die Wahl, wie viele Stücke mit immer so und soviel Gramm gerade gesetzt werden.
Dafür Arrays mit Stückzahlen.

Um alle Lösung zu erhalten, die Methoden nicht mit return true; verlassen, sondern Lösungen ausgeben/hinzufügen und Methoden fortführen.

Nur gedanklich durchgespielt, sollte aber, wenn Backtracking bekannt is, kein großes Problem bereiten.