Bundeswettbewerb Informatik: BWINF

michib

Hi,
äääh ich glaub du hast meinen Algorithmus falsch verstanden bzw.. ich hab ihn unverständlich beschrieben... natürlich geschieht da viel mehr... das Beispiel war totalaus der Luft gegriffen und gar nicht überlegt...ich weiß schon was ich mache
Michi

michib

A vor B
A vor C
D vor C

was wäre hier ein Problem?

Michael E.

Nix, wenn du weißt, was du machst

michib

OK, ich hab gerade gemerkt dass mein Algo bissl blöd ist um solche Fälle zu bestimmen muss ich halt nen neuen schreiben

Maverick89

hat schon jemand einen Algo, der ALLE möglichen reihenfolgen bestimmt entwickelt? mir fällt nix ein

bei A3 - was habt ihr da für veränderungen implimentiert, falls es kein geheimniss ist? ich habe bisher nur 2 strukturelle veränderungen - eine tabelle "umkehren" und elemente der seite verwechseln.

michib

Hi,

hat schon jemand einen Algo, der ALLE möglichen reihenfolgen bestimmt entwickelt? mir fällt nix ein

ich habe einen Algorithmus entwickelt der wirklich alle möglichen Reihenfolgen herausfindet!

bei A3 - was habt ihr da für veränderungen implimentiert, falls es kein geheimniss ist

na damit werde ich bald anfangen...leider isch nur noch wenig Zeit! Naja meinen HTML Parser werd ich schon noch hinbekommen! Ich hab an Farbveränderungen gedacht, Umstrukturierungen usw...

Gruß Michi

Maverick89

Naja meinen HTML Parser werd ich schon noch hinbekommen!

Womit programmierst du eigentlich? ich will ja nicht cheaten, aber .NET 2.0 hat eingebauten DOM-Html-Parser

michib

Hi,

Womit programmierst du eigentlich?

Java

.NET 2.0 hat eingebauten DOM-Html-Parser

Java hat sowas in der Art auch...ich wollte es bloß bissl abspecken...

Michi

Wieso? Wenn es in der Java-API ist, dann blähst du doch mit jedem Rad-Erfinden nur auf..

michib

Hi,

Wenn es in der Java-API ist, dann blähst du doch mit jedem Rad-Erfinden nur auf..

ja stimmt schon, nur kenn ich mich dem DOM Zeugs net so aus, da dachte ich mir halt, dass ich des selber schreib...

Also der Algorithmus für alle Reihenfolgen von Aufgabe 2 steht jetzt und funktioniert perfekt!

Michi

Ich programmiere jetzt schon einige Jahre und bin auch sehr interressiert, d.h. ich lese viel zu den unterschiedlichsten Themen. Aber bei Aufgaben wie sie im bwinf gestellt werden scheitere ich regelmäßg. Ich hab einfach keine Ahnung wie man z.B. Aufgabe2 (die mit dem Anziehen) lösen soll. Gibts da Bücher die diese Art von Problemen beschreiben und wie man sie löst?

Maverick89

Interressierter Leser schrieb:

Ich programmiere jetzt schon einige Jahre und bin auch sehr interressiert, d.h. ich lese viel zu den unterschiedlichsten Themen. Aber bei Aufgaben wie sie im bwinf gestellt werden scheitere ich regelmäßg. Ich hab einfach keine Ahnung wie man z.B. Aufgabe2 (die mit dem Anziehen) lösen soll. Gibts da Bücher die diese Art von Problemen beschreiben und wie man sie löst?

Du solltest dich weniger auf Programmieren sondern in Mathematik steigern: zB Graphen und solches Zeug. Wenn du erstmal lernst, theoretische zusammenhänge mathematisch darzustellen, wird für dich die zu programmieren kein problem sein.

Also ich habe die Aufgabe eins mit einer Rekursivfunktion gelöst. Dabei erhalte ich für Beispiel 2 172 Monate. Allerdings benötigt meine Funktion für die letzten 20 Monate bestimmt eine halbe Stunde zum rechnen!?

Wie seid umgangen, dass man alles ausprobieren muss, wenn keine augenscheinliche Lösung als Restgeld 0 lässt?

mfg

Marc

argh - vergesst es, ich habs *freu* ~1sek für die Aufgabe.

mfg

Marc

michib

Hi,

Wie seid umgangen, dass man alles ausprobieren muss, wenn keine augenscheinliche Lösung als Restgeld 0 lässt?

...Restgeld 0 muss ja nicht sein

ich habs *freu* ~1sek für die Aufgabe.

welche Programmiersprache benutzst du? Hast du nach der Optimierung immer noch 172 Monate?

Welche Aufgaben mach du außer der ersten?

Gruß Michi

Ich benutze c++

Aufgabe Zeit Lösung
Aufgabenblatt 0 ms 13 Monate
Beispiel 1 1422 ms 131071 Monate
Beispiel 2 313 ms 172 Monate
Beispiel 3 3079 ms 1026 Monate
Beispiel 4 / unlösbar

Joa natürlich muss das Ergebnis nicht 0 sein. Aber wenn es 0 ist hat man eine optimale Lösung gefunden und kann die Rekursivfunktion verlassen, während man sonst alle Kombinationen durchgehen muss, die auch noch das gewünschte Ergebnis ergeben könnten.
Aber ich habe gestern noch eine Optimierung gefunden, die die Rechenzeit von einer halben Stunde auf die 313ms reduziert hat !

Ich habe bis jetzt die Aufgabe 1 komplett gelößt, inklusive Dokumentation.
Bei der Aufgabe 2 habe ich soeben einen vernünftigen Algorithmus gefunden ( ich habe 90 Lösungen raus!?) und muss mich jetzt an die Doku machen.

Was ich noch bearbeite schau ich mir an, sobald ich die Doku fertig habe. Aber wenn es möglich ist noch eine logische Aufgabe ohne besonders tolle Oberfläche.

mfg

Marc

Maverick89

Aber ich habe gestern noch eine Optimierung gefunden, die die Rechenzeit von einer halben Stunde auf die 313ms reduziert hat !

irgendein cache oder was anders?

Ich habe zwar nicht vor am Wettbewerb teilzunehmen, aber Aufgabe 1 fand ich interessant genug um eine Loesung zu erarbeiten.
Mein Algorithmus erstellt zunaechst fuer jeden Preis ein Array in welchen steht, aus welchen vohergehenden Preisen sich ein Preis moeglichst optimal zusammensetzen laesst. Dies funktioniert natuerlich nur, wenn die Summe der vorangegangenen Preise groesser oder gleich des Preises minus des Budgets ist. Dies ist zum Glueck in allen ( loesbaren? ) Datensaetzen der Aufgabe der Fall. Mit Hilfe dieser Arrays wird nun gekauft und getauscht. Der Algorithmus ist nicht rekursiv.
Die "Daten des Karnevalsvereins" schafft mein Algorithmus in 13 Schritten. Beispiel 1 schafft er in 141 Schritten. Jeweils mit dem 1000 Euro Budget.
Die Rechenzeiten sind bei beiden sehr gering ( gefuehlt deutlich weniger als eine halbe Sekunde ). Mein Programm entspricht aber noch nicht den Anforderungen des Wettbewerbs. Das heisst es fehlt die Ausgabe, anhand derer man nachvollziehen kann, wie was getauscht und gekauft wird. Aber der Code sieht aus als wuerde er das Problem korrekt loesen
Wie kommt man bei Beispiel 2 auf eine Loesung ohne das Budget zu erhoehen? Der niedrigste Preis liegt schliesslich bei 7362 Euro.
Ich will kein Spielverderber sein, deshalb frage ich ob es jemanden stoeren wuerde wenn ich meinen Code hier fuer alle zugaenglich mache?

Maverick89

hm, also würd mich schon interessieren, aber lass damit etwas mehr warten

in den beispielen ist die erste Zeile jeweils das Budget, und dann kommen erst die gegenstände. In beispiel2 ist die erste zeile - 10000 - das ist das Budget

Also hast du alle möglichen kombinationen von gegenständen in einen preis-cache zusammengesetzt, oder wie soll ich das verstehen? Der muss aber dann bei bsp1 ziemlich riesig sein, oder?

stalafin

Also ich habe JAVA benutzt, um einen Algorithmus für das Problem bei Aufgabe 1 zu entwerfen.

Das Problem ist halt, dass er wahnsinnig lang arbeitet. Er ist rekursiv und versucht, aus allen Objekten die möglichst optimale Kombination herauszurechnen.

Was mich wundert ist die Geschichte mit dem Cache - ich nehme an, diejenigen, die das so gelöst haben, haben einfach zuerst sämtliche Kombinationen erstellt und dann in einem Array zwischengelagert?
Das ist aber auch heftig...
Wir haben dabei 17 verschiedene Zahlen bei den Musterobjekten aus Beispiel 1. Das ergibt dann eine Anzahl von Kombinationen in Höhe von 2^17-1. Das sind 131071 Kombinationsmöglichkeiten. Ich mein, das ist interessant. Aber ist das wirklich noch effizient?

Hm, ich denke, ich muss das mal ausprobieren. Bei mir erstellt das Programm im Moment alle Kombinationen von Neuem. Auch nicht gerade genial...