Rucksackproblem

Sonstiges Hausaufgaben
21

Ich hab das (binäre, nicht fraktale) Rucksackproblem mal mit der der Schleife oben und dem Beispiel aus dem Buch gelöst:

        int[] gewicht = {1, 1, 1, 1, 1, 10,  20,  30};
        int[] wert =    {1, 1, 1, 1, 1, 60, 100, 120};
        int max_gewicht = 55;
		11111011
[ 24, 11,  13, 30, 30, 29,  26, 12]
[104, 78, 101, 69, 64, 64, 101, 75]
max_gewicht = 105
11100011

24+11+13  +26+12 = 86
459

        int max_wert = 0;
        int max_int = 0;

        for (int i = 0; i < Math.pow(2, gewicht.length); i++) { ...```

funktioniert zwar, ist aber eine Bitschubserei und rekursiv viel besser zu formulieren.

2^10 = 8^8 = 1024 geht natürlich schnell, für das andere, zB 100, könnte man Greedy-/Best-Ansatz verwenden, man sortiert nach Gewicht/Wert und fügt ein, bis 75 % oder nur noch 10 Gegenstände übrig sind, dann genau oben.

[Anmerkung SlaterB: 2^10 ist natürlich nicht 8^8..]
22

das Thema hat sich für mich jetzt erstmal erledigt, weil ich den Zettel abgegeben habe. Danke nochmal für die hilfreichen Beiträge ::manklatsch

23

Hier ist das Proggi:


/**
 * @author CB
 */
public class Rucksack {

    public static void main(String[] args) {
        int[] gewicht = {1, 1, 1, 1, 1, 10,  20,  30};
        int[] wert =    {1, 1, 1, 1, 1, 60, 100, 120};
        int max_gewicht = 55;
        genau(gewicht, wert, max_gewicht);

        for (int i = 0; i < gewicht.length; i++) {
            gewicht** = (int) (Math.random() * 21) + 10;
        }
        for (int i = 0; i < wert.length; i++) {
            wert** = (int) (Math.random() * 61) + 60;
        }
        max_gewicht = 8*20/2;
        System.out.println(Arrays.toString(gewicht));
        System.out.println(Arrays.toString(wert));
        System.out.println("max_gewicht = " + max_gewicht);
        genau(gewicht, wert, max_gewicht);
    }

    public static int genau(int[] gewicht, int[] wert, int max_gewicht) {
        int max_wert = 0;
        int max_int = 0;
        a:
        for (int i = 0; i < Math.pow(2, gewicht.length); i++) {
            int maxg = 0;
            int maxw = 0;
            for (int j = i, k = 0; j != 0; j >>>= 1, k++) {
                if ((j & 1) == 1) {
                    maxg += gewicht[k];
                    maxw += wert[k];
                    if (maxg > max_gewicht) {
                        continue a;
                    }
                }
            }
            if (maxw > max_wert) {
                max_wert = maxw;
                max_int = i;
            }
        }
        System.out.println(new StringBuilder(Integer.toBinaryString(max_int)).reverse().toString());
        return max_int;
    }
}```

Hat aber zwei wichtige Nachteile, es werden "dynamisch" alle Lösungen berechnet, ein int hat ja nur (2^31)-1 Bits, Bitschubserei.
24

Wenn ich mir deinen code style anschaue entdecke ich da noch sehr viel mehr…
Spagetticode und java-coding-convention-brüche:

  • nichts sagender Methodenname
  • nichts sagende Variablennamen
  • Labels sollte man nicht verwenden. Es gibt immer eine bessere alternative.
  • Naming Convention Brüche (max_int, max_gewicht ← man verwendet keine underscores für variablen in Java)
  • (… reicht hier erstmal)

CB ignoriert diese Hinweise sehr gern (er ließt die nicht zum ersten mal). Aber @TO: wenn du seinen Code einfach ignorierst, dann verpasst du auch nichts.

25

Ich hab das noch mal ins Reine geschrieben.

  1. Ist das kein spaghetti code.
  2. Erhebe ich keinen Anspruch darauf, für beliebige Größen usw.
  3. Hast du überhaupt die Schleife code nachvollzogen?
  4. Variablennamen schön ist ein nice-to-have, aber yagni, du brauchst es nicht, und könntest es auch so verstehen.
  5. Ein Backtrack nicht-rekursiv ist wahrscheinlich gesucht.
  6. So far for the Moment.
26

Edit: Ich hab es noch mal in Methoden aussagekräftiger Namen aufgeteilt:

Falls Interesse besteht, kann ich das gerne noch mal komplett posten, @Tomate_Salat .

27
  1. Labels sind die kleine Schwester von gotos. Beides Sachen die unnötig komplizierten Spagettihcode verursachen. Letzteres gibt es in Java zum Glück nicht und ersteres sollte man nicht verwenden.
  2. ???
  3. Nein, deinen Code tue ich mir nicht an.
  4. Nein sind sie nicht. Im Gegenteil, sowas ist z.B. ein Grund warum eine Code Review in Firmen nicht durch kommt.

Nein nicht wirklich.

Tut es eigentlich nicht. Hatte schon oft genug mit dir Diskussionen darüber. Aber du bist schlicht nicht fähig mit konstruktiver Kritik umzugehen, weswegen meine obige Aussage auch eigentlich an den TO und nicht an dich gerichtet war. Kannst mich praktisch einfach ignorieren wenn es um nicht-moderatorische Sachen geht.

28

Kompletter Blödsinn: Wenn Herr oder Frau X mal irgendeinen Beruf mit IT-Bezug ausüben möchte, dann ist die Verwendung aussagekräftiger Bezeichner ein MUSS.

gew wer nam anstatt gewicht, wert, name - glatter Kündigungsgrund.

29

[QUOTE=Bleiglanz]Kompletter Blödsinn: Wenn Herr oder Frau X mal irgendeinen Beruf mit IT-Bezug ausüben möchte, dann ist die Verwendung aussagekräftiger Bezeichner ein MUSS.

gew wer nam anstatt gewicht, wert, name - glatter Kündigungsgrund.[/QUOTE]

Und wenn es eine Konvention gibt, Variablennamen sollen nur 3 Zeichen betragen? Wenn, Hätte, Konjunktiv, Fahrradkette.

Das mit dem MUSS ist mir bekannt. Jetzt mal weg von den Namen/Bezeichnern.

Ein int hat ja nur 32 oder 31 Bit, mehr ist praktisch damit auch nicht lösbar, deswegen hab ich die Methode ungenau dazugepackt und mit 500 Elementen getestet. Zuerst der Greedy-Ansatz, wähle nach Gewicht/Wert “wertvollstes”, bis nur noch 20 Elemente übrig sind, fülle dann den Rucksack mit der Methode genau auf, bis <= max_gewicht.

2^20 => Berechnung in < 1 Sekunde
2^31 => Musste ich ausnahmsweise abbrechen, weil es zu viele Kombinationen gibt

Edit: Der TO hatte seine Abgabe und ist wahrscheinlich zufrieden damit, ich weiß über den Ratschlag Bescheid und darf (ihn/den/diesen) ignorieren. Alle sind glücklich.

Grüße

30

[quote=CyborgBeta]Und wenn es eine Konvention gibt, Variablennamen sollen nur 3 Zeichen betragen?[/quote]Dann würde ich selber kündigen…

bye
TT

31

[QUOTE=CyborgBeta]Und wenn es eine Konvention gibt, Variablennamen sollen nur 3 Zeichen betragen? Wenn, Hätte, Konjunktiv, Fahrradkette.

Das mit dem MUSS ist mir bekannt. Jetzt mal weg von den Namen/Bezeichnern.[/QUOTE]

Nein, nicht weg von den Bezeichnern. Selbst wenn du da völlig lernresistent bist, kann man das einfach so nicht stehen lassen, schon um der armen Seelen aufstrebender Eleven willen, denen wirklich daran gelegen ist, besser zu programmieren.

Und siehe da, nach kurzem Suchen findet man auch, dass „vernünftige“ Bezeichner nicht umsonst gefordert werden, sondern dass es dafür wissenschaftliche Bestätigung gibt:

Readability Studie - Entwicklertagebuch

In einem Satz: Durch explizite Bezeichner (customer, request, repository, etc.) lassen sich, gegenüber Abkürzungen (acm, req, rep, etc.) und einzelnen Buchstaben (a,c,s, etc.) Fehler in Quellcode um zwischen 10 und 25% schneller (und präziser) finden.

Readability Studie - Entwicklertagebuch

Link zur Studie: Dropbox - Studie.pdf - Simplify your life

Ich frage mich wirklich, wie man sonnenklaren Fakten direkt unter seiner Nase gegenüber so komplett vernagelt sein kann. Du nimmst keine Ratschläge an, du lernst nichts, entwickelst dich (und deinen Code) keinen Millimeter weiter, du verdirbst die aufstrebende Jugend mit schlechten bis unsinnigen Beispielen, und hältst dich tausendfacher Evidenz zum Trotz für den größten Programmierer aller Zeiten. Was soll aus dir nur einmal werden, mit deiner aktuellen Einstellung (*) wirst du nie einen anständigen Job in der Programmierung finden.

(*) Das Problem ist wirklich deine Einstellung, nicht dein Code. Wir alle haben mit miesem Code angefangen, aber wir haben dazugelernt.

32

Was soll denn diese Unterschriftenliste?

+1
Dein Beitrag ist gut formuliert geschrieben.

-1
@Tomate_Salat hat explizit gesagt, ich kann seinen gut gemeinten, konstruktiv-kritischen Verbesserungsvorschlag einfach ignorieren - das hab ich getan - nicht mehr, nicht weniger.

Das Gebashe ist doch völlig unnötig. :o)

33

Naja, da du von mir eh nix an nimmst ist es schlicht besser du ignorierst mich anstatt eine sinnlose Diskussion zu starten (was du ja streng genommen aber nicht getan hast). Falls du dennoch die Ratschläge hier (auch meine) annehmen würdest, wäre das aber nicht verkehrt ;). Egal, müssen das jetzt nicht ausdiskutieren.