IT-Talents.de Code Competitions

Jump to last post
:p - wie kommst du darauf, das eine interpretierte nicht direkt maschinen-lesbare Sprache langsamer ist, als (hoch)optimierter Assembler Code? :D

Aber ich geb zu, selbst die "print"-Statements/Ausgabe in die Konsole haben/hat geblockt und alles verlangsamt, deßhalb mußte ich die größtenteils ausklammern um nen guten Wert zu bekommen ;)
 
Zuletzt bearbeitet:
Viel Glück an alle die bei der Mai Competition teilnehmen!

Ich melde mich wieder wenn ich die Bewertung meiner April abgabe erhalte.

Lg
 
You do not have permission to view link please Anmelden or Registrieren
Ich bedanke mich deswegen, weil mir das ähnlich ging als ich bei einem (meinem ersten) Wettbewerb mitgemacht habe.... ich wollte auch erst meine Antwort haben, bevor ich irgendwas weiter mache und an der nächste Wettbewerb teilnehme..... ;)

Aber danke für die Glückwünsche - kann ich gebrauchen, so wie es aussieht :T
 
Ich lese die letzten Tage hier nur mit und habe mich noch nicht ausführlich genug mit dem Thema beschäftigt.
Ich überlege gerade, wie eine Datenkonstellation aussehen könnte, wo eine Optimierung überhaupt greifen könnte.
Ein greifbares Problem, für das ein Algorithmus benötigt wird.

Für ein Ergebnis für die 50000 Dinge Maximaler Wert: 287384€ Gewicht: 9999kg braucht man keinen Algorithmus, da reicht es die Dinge nach value-to-weight ratio sortiert bis an das Maximalgewicht in den Sack zu füllen

Da wäre interessant, was bei dem Ergebnis von @jamestop (Maximaler Wert: 287399€ Gewicht: 10000kg) den Unterschied in der Bepackung ausmacht?
 
Ich wage gerade zu bezweifeln das man einen besseren Wert erhalten kann als die 287384 € mit 9999 kg... (Edit: Nein, wobei, ich hatte einen Denkfehler... habe mein Ergebniss übertroffen)

Dafür habe ich folgendes implementiert, was dafür sorgen soll, das wir in unserer Packliste Gegenstände austauschen die a) weniger Wert sind als ein einzelner Gegenstand und b) weniger oder gleich viel wie die zu tauschenden Gegenstände wiegen bzw. der Tausch im Maximalgewicht liegt.

Jetzt ist die Frage, habe ich hier einen Denkfehler?

Update/Edit: Habs nochmal in ein extra Loop gepackt, das wir bei einer Änderung nochmal alle Gegenstände durchgehen...

[src=c]unsigned int exchangeList[packedItems.count];

clock_t timeStart = clock();
bool hasChange = true;
while (hasChange) {

hasChange = false;

for (unsigned int i = 0; i < caseItems.itemCount; ++i) {
current = &caseItems.items;

if (!current->packed) {
unsigned int exchangeIndex = 0;
unsigned int exchangedWeight = 0;
unsigned int gainedValue = current->value;

for (unsigned int j = 0; j < packedItems.count; ++j) {
if (packedItems.items[j] != NULL && gainedValue > packedItems.items[j]->value) {
exchangeList[exchangeIndex++] = j;
exchangedWeight += packedItems.items[j]->weight;
gainedValue -= packedItems.items[j]->value;

if (exchangedWeight >= current->weight || ((maxWeight - packedItems.weight) + exchangedWeight) >= current->weight) {
printf("Exchanged weight: %d, gained value +%d ( Total %d Euro )\n", exchangedWeight, gainedValue, current->value);
hasChange = true;
packedItems.weight -= exchangedWeight - current->weight;
packedItems.value += gainedValue;

for (unsigned int k = 0; k < exchangeIndex; ++k) {
packedItems.items[exchangeList[k]]->packed = false;
packedItems.items[exchangeList[k]] = NULL;

if (k == 0) {
current->packed = true;
packedItems.items[k] = current;
}
}

break;
}

}
}
}
}
}

clock_t timeEnd = clock();

printf("Time for optimizing %ld milliseconds\n", (timeEnd-timeStart) / 1000);[/src]



Ich komme partou nicht auf das Ergebnis... aber ich komme auf ein etwas besseres:
[src=text]---- Overall stats for possible contents ----
Total value / weight: 12785605 Euro / 24880788 kg

Average value / weight: 256 Euro / 498 kg
Exchanged weight: 1, gained value +4 ( Total 28 Euro )
Time for optimization: 75 milliseconds

---- Packed stats ----
Capacity of backpack: 10000 kg

Total value / weight: 287388 Euro / 10000 kg


------- Finished packaging algorithm in 344.322000 milliseconds... -------

real 0m0,408s
user 0m0,396s
sys 0m0,008s
[/src]

Edit: Das ganze ist nun ohne Sorting...
 
Zuletzt bearbeitet:
Sieht ja fast so aus, als dass ich die Einleseroutine der Daten doch noch implementieren muss... Dann kann ich auch mal eine Zahl rauswerfen...
Ich melde mich, wenn ich da was habe.

You do not have permission to view link please Anmelden or Registrieren
Wollten wir nicht ohne Code posten arbeiten oder war das nur so ein "Ich will meine geile Lösung den anderen nicht zeigen, damit ich gewinne" - Sache ?
 
Naja, ich weiß nicht ob wir unbedingt während der Competion Code posten sollten der komplett lauffähig ist, auf der anderen Seite werden hier auch schon Implementierungsdetails oder Strategien verraten (was ich nicht gut finde von Kapitn ;) ) - die man sich auch hätte knicken können.

Ich wollte allerdings, der Code ist ja so kopiert nicht direkt lauffähig ohne Datenstrukturen, lediglich demonstrieren bzw. herausfinden - ob man wirklich auf das Ergebnis kommen kann, das hier im Raum steht und das wenn die Logik des Codes richtig ist, widerlegen bzw. bestätigen.

Ganze, lauffähige(!), Programme sollten aber wenn überhaupt erst nach dem Wettbewerb veröffentlicht werden, das sehe ich auch so, weil es sonst den anderen den Spaß nimmt, finde ich. Etwas Gedanken soll sich schließlich jeder selbst machen der daran teilnimmt.

Aber klar, irgendwie austauschen sollte man sich schon noch über Strategien oder Ideen oder über Algorithmen, Datenstrukturen oder ähnlichem... Code Snippets sind ja auch gut.
Oder Vergleichswerte sammeln über Implementierung, das finde ich schon ganz interessant, auch um zu sehen wo man steht mit seiner Lösung.

Nach einer Competition kann man ja auch gesamte Code-Blöcke / Programme posten und die dann besprechen oder versuchen zum besseren hin zu optimieren. Daran kann man auch lernen und interessant ist es bestimmt alle mal wie andere ein Problem gelöst haben oder angegangen sind. :T


PS: Ich kann den Code aber auch wieder rausnehmen, wenn das gewünscht ist! :)
Hab ihn jetzt in nen Spoiler gesetzt.
 
Zuletzt bearbeitet:
theSplit schrieb:
auf der anderen Seite werden hier auch schon Implementierungsdetails oder Strategien verraten (was ich nicht gut finde von Kapitn ;) ) - die man sich auch hätte knicken können..
Zum Vergrößern anklicken....

Wie bitte?
Ich habe doch geschrieben, daß ich weit davon entfernt bin, eine Strategie zu haben, daß ich noch nicht mal das Problem erkannt habe. Ich erahne es gerade mal.
Von Implementierung kann man auch nicht sprechen. Ich habe die Liste mit den 50k Dingen gesehen und war neugierig, was rauskommt, wenn man die einfach in den Sack packt.Also habe ich eine Schleife zum Lesen und eine zum Packen. Mehr nicht.

Daß man zuerst die wertvolleren Dinge nimmt, ist ja wohl keine Strategie, sondern selbstverständlich.
 
You do not have permission to view link please Anmelden or Registrieren
Es geht mir nur um den von dir genannten "Ratio" bzw. das Verhältnis, das hätte ich vielleicht einfach offengelassen. Nicht auf den Schlips getreten fühlen bitte ;)

Für mich, da ich mich nicht oft mit dem Problem auseinadergesetzt habe, war das zum Beispiel nicht so intuitiv.... ich mußte überlegen wie ich die beiden Werte in ein Verhältnis setze, um auf einen guten Nenner zu kommen.

Aber gut, vielleicht seh ich das gerade auch etwas zu eng.... fands nur schade das du es vorweggenommen hast ;)

Ach so und frage, soll ich den Code rausnehmen? Spoilert das irgendwas, verrät das zu viel?
Sollte eher Proof-of-concept sein. : /
 
Na gut.Aber daß die Dinge einen hohen Wert, aber wenig Gewicht haben, sollen, ist doch klar. Ob Du da jetzt ein Verhältnis bildest oder einfach 2 mal sortierst, ist ja gleich.

Wer aus Deinem Code etwas herauslesen will, der wird sich schon etwas Mühe machen müssen. Das klickt keiner mal eben auf und ärgert sich dann. ;)
 
Mal die Frage an euch, anschließend an den Kapitn auch, sollen wir hier ruhig Code posten (Stücke) oder Strategien kommunizieren - während einer Competition?

Oder sollte man sich, für die Dauer des Wettbewerbs, in Schweigen hüllen, das bearbeiten und sich über vorherige austauschen? - Hab da auch nicht recht so ne Idee was besser ist. Soll ja auch nicht alles spoilern, aber wenn man zusammen bzw. jeder für sich aber trotzdem zusammen was gutes erarbeiten kann, wäre das natürlich gut. ;)

Macht das Sinn? :unknown: Meinungen? :)
 
You do not have permission to view link please Anmelden or Registrieren


Muß man das streng reglementieren? Wenn das in Spoiler-Tags steht, vielleicht nochmal Rot dranschreiben, Spoilerwarnung, wenn es sein muß, dann sehe ich da kein Problem.
Wer sein Ding machen will, der kann das dennoch tun.

Ich will eigentlich gar nicht teilnehmen. Aber durch die Liste von @jamestop habe ich mal rumgespielt. Habe ich ja geschrieben, eine Sache von ein paar Minuten. Ich hatte eine Ahnung, warum er da noch ein besseres Ergebnis erzielen, bin aber nicht damit klar gekommen, das Problem zu formulieren.
Geholfen hat dann die Ergebnisdatei von @Roin, die ich analysiert habe, so daß ich nun meine, das soweit verstanden zu haben.
Jedenfalls kann ich jetzt die Ergebnisse für beide Listen aus meiner Sicht bestätigen. Das gilt für die 50000 Gegenstände natürlich nur für Gesamtgewicht und Gesamtwert, weil mehr nicht vorliegt. Bei den 10000 Gegenständen kann ich auch die Liste mit den Gegenständen bestätigen, allerdings nur als eine von mehreren Möglichkeiten, um auf das Gewicht und den Wert zu kommen.

Kurz: Hättet Ihr Euch nicht über das Thema unterhalten, wäre ich gar nicht eingestiegen.
 
Das mit der Spoilerwarnung kann ich gleich mal ergänzen. :)

@Kapitn, aber du beherrschst die Kunst viel und auch nicht viel zugleich zu sagen fast perfekt.... ;)

Kannst du ein paar Zahlen nennen aus deinen Versuchen und welche Zahlen kannst du Bestätigen? Das würde mich unter anderem auch brennend interessieren da ich für Vergleichswerte bin.... :)
Ansonsten werd ich gerade nicht so recht schlau aus deinem Post, ob du das Problem schon hast lösen können und auch für dich implementiert hast oder ob du nur irgendwie die Ergebnisse, Wert und Kilogramm, "überschlagen" hast um auf so ein Ergebnis zu kommen. ;)

Aber schön natürlich wenn dich die Problemstellung und Lösung auch anspornen! :cool:

Hier nochmal die letzten Zahlen meiner Ausgabe:

Für @Roins Gegenstandsliste:
[src=text]1000 kg , 2798 Euro / 998 kg[/src]

Mehr bekomme ich auch hier mit meiner Nach-Optimierung nicht.


Bei @jamestop Liste, auch mit Testweise absteigender Sortierung nach Wert, um keine "billigeren" Gegenstände fälschlicherweise einzupacken:
[src=text]10000 kg, 287388 Euro / 10000 kg[/src]

Mehr "pack" ich hier nicht, im wahrsten Sinne :p
 
Zuletzt bearbeitet:
jamestop 50.000 Artikel
[src=text] 10.000Kg Sack ; Gesamtgewicht 10.000Kg / Gesamtwert 287399 €
[/src]


Roin 10.000 Artikel
[src=text]10.000Kg Sack ; Gesamtgewicht 10.000Kg / Gesamtwert 793699 € [/src]

Roin 1000 Artikel
[src=text]1000Kg Sack ; Gesamtgewicht 998Kg / Gesamtwert 2798 € [/src]

Ich habe Code. Nicht schön. Nur das Nötigste und im Debugger.
 
You do not have permission to view link please Anmelden or Registrieren
Also den Wert und Gewicht für die 1000 Artikel von Roin, gehe ich voll konform mit dir. Die 10k Testdatei habe ich allerdings nicht getestet, weil nicht vorliegen.

Ich frage mich aber dennoch, wie du auf den Wert von 287399 € gekommen bist für die 50k Datei.... wurmt mich ein wenig das ich das mit meinem Ansätzen so nicht hinbekomme.... :D
 
You do not have permission to view link please Anmelden or Registrieren


Und ich frage Dich jetzt, ob ich die Antwort auf Deine Frage posten soll? :unknown:
 
Hm... also wenn du auch auf das gleiche Ergebnis kommst, muß der Wert ja stimmen, zwei oder drei gegen einen ;)

Ich frage mich nur gerade warum meine Optimierung, wenn es eindeutig etwas höherwertiges in der Liste gibt, nicht identifiziert und eingetauscht wird wenn es mindestens zwei andere Gegenstände preislich und innerhalb des Gewichts, ersetzen könnte. Rein von meiner Logik her ist die Optimierung "perfekt"... daher wundert es mich so sehr.
 
theSplit schrieb:
Ich frage mich nur gerade warum meine Optimierung, wenn es eindeutig etwas höherwertiges in der Liste gibt, nicht identifiziert und eingetauscht wird wenn es mindestens zwei andere Gegenstände preislich und innerhalb des Gewichts, ersetzen könnte.
Zum Vergrößern anklicken....

Der Artikel muß nicht jeweils höherwertiger sein, als die 2 anderen Gegenstände.

Das ist Quatsch. Habe die Spalten vertauscht. Er muß größer als die Summe sein, somit auch jeweils größer.
 
Zuletzt bearbeitet:
You do not have permission to view link please Anmelden or Registrieren
Das ist aber auch das Problem glaube ich, ich versuche ja einen Wertverlust bei einem gleichwertigen Tausch zu vermeiden... jetzt könnte man noch nach einer Toleranz gehen wenn der Tauschgegand zwar "etwas" weniger Wert hat, aber dafür auch weniger Gewicht zum Beispiel.

Hab gerade noch versucht das umzudrehen was ich bisher angedacht habe, das ich auf maximale Auslastung und nach Gesamtwert gehe - aber ist gar nicht so einfach das umzuschreiben bzw. den anderen Weg zu gehen.
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben