algo:knapsack

Diskussionen zu Tutorials, Änderungs- und Erweiterungswünsche
nufan
Wiki-Moderator
Beiträge: 2557
Registriert: Sa Jul 05, 2008 3:21 pm

algo:knapsack

Beitrag von nufan » Di Apr 10, 2012 4:39 am

Es ist 5:39, aber ich bin damit fertig geworden...
http://www.proggen.org/doku.php?id=algo:knapsack
Feedback lese ich später ^^

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: algo:knapsack

Beitrag von Xin » Di Apr 10, 2012 9:49 am

Schöner Artikel. :-)
Rechtschreibung oder Funktion habe ich nicht geprüft, nur auf die schnelle gelesen.

Könntest Du die Wörter "Kombinatorische Optimierung" noch in den Artikel einpflegen und dort einen Link nach glossary:combinatorics reinpacken?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

LadyBird
Beiträge: 24
Registriert: So Jul 31, 2011 8:12 pm

Re: algo:knapsack

Beitrag von LadyBird » Di Apr 10, 2012 12:22 pm

Ich finde den Artikel gut und leicht verständlich.
Aber könnte es sein, dass du die Nummern der Gegenstände vertauscht hast?
In der ersten Tabelle hat Gegenstand 1 noch das Volumen 5 und den Wert 8, in der zweiten Tabelle hat der 1. Gegenstand das Volumen 6 und auch den Wert 6.

nufan
Wiki-Moderator
Beiträge: 2557
Registriert: Sa Jul 05, 2008 3:21 pm

Re: algo:knapsack

Beitrag von nufan » Di Apr 10, 2012 2:14 pm

Xin hat geschrieben:Könntest Du die Wörter "Kombinatorische Optimierung" noch in den Artikel einpflegen und dort einen Link nach glossary:combinatorics reinpacken?
Ok, werde ich machen :)
LadyBird hat geschrieben:Ich finde den Artikel gut und leicht verständlich.
Danke :) Gibt es vielleicht irgendwas, dass nicht auf den ersten Blick klar war? Etwas das ich vergessen habe? Ein weiterer möglicher Lösungsweg? Ich bin da schon etwas voreingenommen und auf dynamische Rekursion fokussiert, vielleicht kannst du mir da eher helfen :)
LadyBird hat geschrieben:Aber könnte es sein, dass du die Nummern der Gegenstände vertauscht hast?
In der ersten Tabelle hat Gegenstand 1 noch das Volumen 5 und den Wert 8, in der zweiten Tabelle hat der 1. Gegenstand das Volumen 6 und auch den Wert 6.
Du hast recht, danke für den Hinweis :) Es ist auch verdammt schwer in Beispiel zu finden, in dem die Greedy-Lösung schlechter ist als die Rekursion. Deshalb hab ich da viel herumprobiert und geändert, irgendwann hab ich dann auf die Nummer vergessen. Aber auf die weitere Lösung hat das ohnehin keinen Einfluss.

LadyBird
Beiträge: 24
Registriert: So Jul 31, 2011 8:12 pm

Re: algo:knapsack

Beitrag von LadyBird » Mi Apr 11, 2012 7:45 pm

nufan hat geschrieben:Danke :) Gibt es vielleicht irgendwas, dass nicht auf den ersten Blick klar war? Etwas das ich vergessen habe? Ein weiterer möglicher Lösungsweg? Ich bin da schon etwas voreingenommen und auf dynamische Rekursion fokussiert, vielleicht kannst du mir da eher helfen :)
Mit dem Thema Algorithmen habe ich mich noch kaum genauer auseinandergesetzt. Deshalb kann ich nicht beurteilen, ob du etwas vergessen hast. Zum Teil musste ich etwas länger überlegen, aber das lag wahrscheinlich eher daran, dass das Thema komplett neu war und ich auch von binären Bäumen nur bisher nur mal gehört habe. Also ich denke, da kann ich dir im Moment nicht wirklich weiter helfen. Vielleicht irgendwann später :)

nufan
Wiki-Moderator
Beiträge: 2557
Registriert: Sa Jul 05, 2008 3:21 pm

Re: algo:knapsack

Beitrag von nufan » Mi Apr 11, 2012 8:08 pm

@Xin:
Den Link aufs Glossar habe ich eingefügt und Mosi und FlorianLeimgruber drüberlesen lassen, die den Artikel verständlich und gut erklärt fanden. Ich würde den Link auf algo:knapsack gern in die Übersicht von algo:start (http://www.proggen.org/doku.php?id=algo:start) einfügen, aber unter welcher Überschrift? "Rekursionen" stimmt ja nicht ganz.
LadyBird hat geschrieben:Zum Teil musste ich etwas länger überlegen, aber das lag wahrscheinlich eher daran, dass das Thema komplett neu war und ich auch von binären Bäumen nur bisher nur mal gehört habe.
Irgendwas das man im Nachhinein vielleicht besser erklären hätte können? :)

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: algo:knapsack

Beitrag von Xin » Do Apr 12, 2012 1:27 am

nufan hat geschrieben:@Xin:
Den Link aufs Glossar habe ich eingefügt und Mosi und FlorianLeimgruber drüberlesen lassen, die den Artikel verständlich und gut erklärt fanden. Ich würde den Link auf algo:knapsack gern in die Übersicht von algo:start (http://www.proggen.org/doku.php?id=algo:start) einfügen, aber unter welcher Überschrift? "Rekursionen" stimmt ja nicht ganz.
Kombinatorische Optimierung? ^^
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

nufan
Wiki-Moderator
Beiträge: 2557
Registriert: Sa Jul 05, 2008 3:21 pm

Re: algo:knapsack

Beitrag von nufan » Di Jun 05, 2012 1:26 pm

*Update* ^^
Rückrechnung ergänzt, kleinere Änderung. Kritik erwünscht :)
http://www.proggen.org/doku.php?id=algo:knapsack

Benutzeravatar
oenone
Beiträge: 223
Registriert: Do Sep 01, 2011 2:42 pm
Wohnort: Bremen
Kontaktdaten:

Re: algo:knapsack

Beitrag von oenone » Fr Jun 29, 2012 2:54 pm

nufan hat geschrieben:*Update* ^^
Rückrechnung ergänzt, kleinere Änderung. Kritik erwünscht :)
http://www.proggen.org/doku.php?id=algo:knapsack
Der Beispielcode ist C++. Wäre es nicht schön, das auch für andere Sprachen zu übersetzen? quasi algo:knapsack:php oder ähnliches.. Klar, der Fokus hier liegt auf C und C++, daher sollte das auch die Hauptseite sein.

Dies soll jetzt nicht nur für den einen Algorithmus gelten, sondern eine generelle Frage sein.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: algo:knapsack

Beitrag von Xin » Fr Jun 29, 2012 3:31 pm

oenone hat geschrieben:
nufan hat geschrieben:*Update* ^^
Rückrechnung ergänzt, kleinere Änderung. Kritik erwünscht :)
http://www.proggen.org/doku.php?id=algo:knapsack
Der Beispielcode ist C++. Wäre es nicht schön, das auch für andere Sprachen zu übersetzen? quasi algo:knapsack:php oder ähnliches.. Klar, der Fokus hier liegt auf C und C++, daher sollte das auch die Hauptseite sein.
Man könnte Reiter verwenden, in denen man die Sprache auswählt.
oenone hat geschrieben:Dies soll jetzt nicht nur für den einen Algorithmus gelten, sondern eine generelle Frage sein.
Grundsätzlich ging das, allerdings gibt es viele Sprachen und irgendwo muss man sich auch fragen lassen, was in welcher Sprache noch sinnvoll ist.

Ist das Rucksackproblem ein PHP-Problem?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Antworten