Bundeswettbewerb Informatik: BWINF
-
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?
-
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?
-
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...
-
Zwar hat bislang niemand geantwortet, aber das ist erstmal egal.
Ich habe nun die möglichen Ergebnisse in einen Array gehauen. Man merkt einen deutlichen Perfomance-Zuwachs.
Das Problem stellt nun nur dar, dass bei einer gewissen Anzahl an Gegenständen die Kombinationsmöglichkeiten durch die Decke gehen und man den Array nicht unendlich vollschreiben kann.Mich wundert ernsthaft, wie einige es geschafft haben, einen Algorithmus zu entwickeln, der in der Lage ist, die Probleme in wenigen Sekunden zu lösen.
Ihr habt eure Algorithmen nicht rekursiv aufgebaut, oder? Und ihr seid euch auch sicher, dass euer Algorithmus aus allen vorhandenen Gegenständen diejenigen auswählt, die sich zu einem optimalen Preis addieren?
Ich bin da ehrlich gesagt skeptisch und kann mir nicht vorstellen, wie das genau funktionieren soll.
-
[quote="stalafin"]Zwar hat bislang niemand geantwortet, aber das ist erstmal egal.
mein Algo ist rekursiv, mit einiegen optimierungen um das process zu beschleunigen. die zeiten sind zwar recht akzeptabel, aber ich glaube es gibt leute deren progs gehen noch besser.
(ich selber benutze C#)
-
In dem Falle denke ich mal, muss ich mir noch irgendwelche Bedingungen zur Optimierung ausdenken.
Auf alle Fälle bringt mein bisheriger Ansatz nicht so viel... Aber mir kommt da gerade eine Idee, hihi...
-
Die ganzen Angaben zu einer haleb Sekunde usw. sind ohne Ausgabe, oder?
Wie lange dauert bei euch die Ausgabe der gesamten Ergebnisse von der Aufgabe2?
-
Ich würde mich der Frage von Chief_C++ anschließen:
Haben diejenigen, die bei der ersten Aufgabe Zeiten von einer Sekunde erreichen, auch die Ausgabe mit dabei?
Das heißt - sind eure Programme in der Lage, für jeden Monat anzugeben, welche Gegenstände gekauft werden sollen?
-
hehe, wenn das programm dazu nicht fähig ist, dann löst es die aufgabe sehr wahrscheinlich auch nicht optimal
-
Sag mal an, wielang dein Programm für alle Aufgaben braucht.
Ich habe bisher keine genauen Zeitwerte. Beispiel 3 wird gerade noch zusammengebaut (die Liste mit den vieeelen Zahlen).
Die anderen wollte ich gerade noch nicht durchlaufen lassen.
-
meinste mich? hab nur aufgabe 1 implementiert. die rennt unter einer sekunde durch, stütz mich aber auch nur auf lokale optimierung.
-
Ja, ich mein Dich!
Ich rede von Aufgabe 1 (närrische Wirtschaft). Und da halt alle Beispiele (die, die Online auf www.bwinf.de als txt-Dokumente zu finden sind).
Oder hast Du nur bei der Aufgabe 1 das Beispiel 1?
-
Hey,
da ich im Moment viel Zeit habe habe ich gedacht, ich mach mal auch den BWINF mit. Leider habe ich gleich schon eine Frage zu Nr1 (die Aufgabenstellung ist leider nicht sehr präzise). Ist es erlaubt, mehere gleiche Gegenstände zu kaufen und am Ende auch mehere gleiche Gegenstände zusammen gegen andere Gegenstände (<-Plural) umzutauschen?[EDIT]Auch ich habe jetzt die FAQ gefunden und darin steht:
Nein, auch wenn das in der Aufgabenstellung nicht sehr deutlich ausgeschlossen ist. Entscheidend ist die Liste der Preise; jedem Listeneintrag entspricht genau ein Gegenstand, der zu diesem Preis erworben werden kann. Der Schatzmeister kann jederzeit immer nur eine Teilmenge der durch die Liste festgelegten Gegenstände haben; am Ende soll die Teilmenge möglichst groß sein und am besten der Gesamtmenge entsprechen.
[/EDIT]
OK, keine doppelten Gegenstände
-
also ganz ehrlich gesagt; die erste aufgabe des diesjährigen bwinf ist alles andere als trivial und hat sehr starke berühungspunkte mit diskreter optimierung. ist meiner meinung nach zu komplex für eine erste aufgabe.
-
thordk schrieb:
also ganz ehrlich gesagt; die erste aufgabe des diesjährigen bwinf ist alles andere als trivial und hat sehr starke berühungspunkte mit diskreter optimierung. ist meiner meinung nach zu komplex für eine erste aufgabe.
Optimierung? Nach was wird den bewertet? Stärke des Algorithmus (effizienz)? Codestyle? Geschwindigkeit?
-
J. Mueller schrieb:
Ich will kein Spielverderber sein, deshalb frage ich ob es jemanden stoeren wuerde wenn ich meinen Code hier fuer alle zugaenglich mache?
Es würde stören. Sollte es nämlich eine korrekte Lösung sein, würde es doch den Bundeswettbewerb Informatik total verzerren - soll der Erfolg von der Googlefähigkeit abhängen?
Ich fänd's total unfair.
-
Ich finde die erste Aufgabe allegemeinhin auch krass.
Immerhin gehört das Problem, welches da gelöst werden will, zu den NP-P Problemen. Und wer das löst, braucht beim BWINF wohl nicht mehr mitmachen. Der hat das dann nicht mehr nötig.
-
stalafin schrieb:
Ich finde die erste Aufgabe allegemeinhin auch krass.
Immerhin gehört das Problem, welches da gelöst werden will, zu den NP-P Problemen. Und wer das löst, braucht beim BWINF wohl nicht mehr mitmachen. Der hat das dann nicht mehr nötig.
whaa??? Ich hab die erste Aufgabe gelöst, obwohl ich mich erst seit zwei wochen mit C++ richtig beschäftige (davor nen bischen Delphi/Pascal aber mehr als arrays hab ich da auch nich gelernt) und habe die erste aufgabe dennoch an einem abend geschafft. Btw: Was zur Hölle ist ein NP-P Problem?
Hab mir ma das auf Wikipedia durchgelesen, aber daraus werd ich nich schlau. Was hat das mit der Aufgabe zu tun?
-
stalafin schrieb:
Ich finde die erste Aufgabe allegemeinhin auch krass.
Immerhin gehört das Problem, welches da gelöst werden will, zu den NP-P Problemen. Und wer das löst, braucht beim BWINF wohl nicht mehr mitmachen. Der hat das dann nicht mehr nötig.
Das eine hat mit dem anderen nix zu tun. Wenn man einfach einen brute-force algorithmus implementiert (weil man z.B. keine Lust hat, sich übermäßig gedanken zu machen
), und ein paar sehr naheliegende optimierungen durchführt, sind alle Probleme bis auf das ganz große sehr schnell lösbar (und selbst das in unter 15min). Da muss man weder was über Komplexitätsklassen wissen noch die NP-Komplettheit des Problems erkennen (ist es das? es sieht ja so aus, aber ich kann grad nichts darauf reduzieren).
-
Habe irgendwann mal im Netz etwas über NP in Zusammenhang mit Streckenoptimierung gelesen (100 Orte sind gegeben - welcher Weg ist der schnellste, wenn man am alle 100 Orte bereisen möchte). Kommt unserem Problem ja recht nahe.
Jaja - in die Richtung Brute Force geht mein Algorithmus auch.
Hehe, nur schein ich nicht auf die entscheidende Optimierung zu kommen.
Ich mein, eine habe ich (ohne die es wohl Jahre dauern würde, die ganze Geschichte durchzugehen).
Aber ansonsten...Aber ganz ehrlich - ihr benutzt Brute Force Methoden und braucht unter 15 Minuten egal für welche Aufgabe? Ich kann mir das irgendwie nicht so recht vorstellen.
Auch mit Ausgabe und allem (jeden Monat)?