IT-Talents.de Code Competitions

Jump to last post
Ich würde Dir gerne das Problem erklären. Nicht die Lösung.
Aber halt nicht ungefragt.
 
@Kapitn: Also wenn es nicht zu viel vorwegnimmt, dann von mir aus gern. Programmieren wollen würde ich es ja dann trotzdem noch - aber bevor ich mich zu sehr mit meinen Ansätzen festbohre, wäre ich für neue Ideen bzw. Herangehensweisen oder Hinweise natürlich mehr als offen. ;)

Kann also dein Angebot schwer ablehnen! :T
 
You do not have permission to view link please Anmelden or Registrieren


Ich habe #119 editiert. Das war falsch.



evtl. Spoilergefahr

Das man den Sack mit den möglichst kleinen, aber möglichst wertvollen Gegenständen füllen muß, liegt ja auf der Hand.Das wäre dann ein OrderbyDescend für den Wert und dann ein Orderby für das Gewicht. Oder aber ein OderByDescend für den Quotienten Wert/Gewicht

Jetzt passen die Gegenstände aber evtl nicht perfekt in den Sack, man kommt also zu einem Gegenstand, der nicht mehr reinpaßt. Also läßt man ihn weg und der Sack ist nicht ganz voll. Verschenkte Kapazität.

Mir ist keine Methode bekannt, wie man das frühzeitig erkennen könnte. Somit gehe ich momentan von einer Lösung in 2. Schritten aus.

Einen 2 Gegenstände rauszunehmen und einen anderen reinsetzen hast Du ja, wenn ich das richtig verstanden habe, schon selber ins Auge gefaßt.
Welche Verbindung zwischen den 3 Elementen bestehen müssen, lasse ich erst mal offen
 
Also du hast jetzt wirklich nicht viel vorweggenommen, denke ich. :)

So 100% nachvollziehen kann ich es dann aber doch nicht in welcher Beziehung die getauschten Gegenstände zueinander stehen. Wert, Gewicht, Quotient?

Der Großteil ist auch schon so implementiert. Ich beziehe mich nochmal auf meinen Code.

Aber da scheidet sich auch meine Logik, wenn ich keinen Gegenstand habe - deßhalb die penetrante Frage nach den Werten ;) - der mehr Wert ist als ein Einzelner oder mehrere Gegenstände und oder genauso viel oder weniger wiegt... kann ich doch auch nicht optimaler packen. Heißt keiner der nicht eingepackten Gegenstände ist wertvoller als einer bzw. zwei, drei... usw. in der Liste und besitzt weniger oder das gleiche Gewicht als das wir in tauschen könnten um in der Kapazität zu bleiben.

Also ist die Optimierung doch theoretisch abgeschlossen wenn wir nichts mehr tauschen können was minderwertiger ist und oder gleich schwer bzw. schwerer?

Ich muss mir dein Posting glaube ich später noch einmal in Ruhe durchlesen, aber ich sehe da jetzt nicht den Hinweis direkt der mir wirklich auf die Sprünge hilft :p

Edit:
Wobei, halt, eigentlich müsste der Algorithmus ja weiterpacken, auch außerhalb des Gewichts mit Toleranz von Maximalgewicht des schwersten Gegenstands, um dann andere Teile auszubalancieren.... irgendwie sowas.... bis man unter/auf das Maximalgewicht kommt. Wären aber ziemlich viele Versuche dann.... :o
 
Zuletzt bearbeitet:
Ich bin so vorsichtig, weil ich Dir nicht den Spaß verderben will.

Tip. Nimm mal die Daten von @Roin aus #99.
Dann fülle damit den Rucksack, wie ich beschrieben habe. Also entweder geordnet nach Quotient oder 2 mal geordnet nach Wert und Gewicht.
Dann hat @Roin da ja noch seine Ausgabe zugepackt. Wenn Du die jetzt vergleichst, mit dem, was rauskommt, der sortierten Füllung, die ich gerade beschrieben habe, dann siehst Du ja, was da anders ist.
Da hast Du dann Deine Zahlen, aus denen Du die Gesetzmäßigkeit erkennen kannst.
 
Ich denke, ich werde im Laufe der Woche mal meinen Code dahingehend erweitern, dass ich auch Testdaten von hier einlesen kann und entsprechend verwenden.
Dann kann ich ja auch mal 50.000 Gegenstände durchlaufen lassen.
Mutmaßlich dauert das zwar einige Minuten, besonders da Firefox gerne etwas sperrt, wenn das JS mal etwas rechenaufwändiger wird...
Apropos: Gibt es ein kleines Programm, dass JS ausführt und etwaige Consolenausgaben ausgibt? Also das das vielleicht etwas schneller kann als wenn ein Browser mit all seinen Features rundrum dahinterhängt?
 
Electron und oder Node.js auch mal antesten? :)

Hab übrigens gestern nicht weiter über das Problem nachgedacht..., aber ich glaub irgendwie fehlt mir aktuell die Fantasie dafür... oder ich muss wirklich Brute-Forcen um ein "perfektes" Ergebnis zu erzielen.
Aber gut, ich hab mich mit Roins Ausgabe auch bisher nicht direkt beschäftigt, aber vielleicht fällt mir ja etwas auf wenn ich mir die Zahlen mal genau ansehe. ;)

Ansonsten muß ich meine Lösung so abgeben wie sie aktuell ist und dann darauf bauen das wir uns nach dem aktuellen Wettbewerb nochmal dem Thema widmen... vielleicht aber auch ein kleines Trostpflaster, es wird ja nicht nach dem "perfekten" Ergebnis gefragt in der Aufgabe auch aufgrund der Länge der Laufzeit, aber ich verstehe es natürlich auch so. das wäre trotzdem anzupeilen. :)
 
Ich habe jetzt mein Programm dahingehend umgeschrieben, dass ich auch Daten einlesen kann, solange sie in CSV-Format:
Name;Weight;Value
Zum Vergrößern anklicken....
vorliegen. Das Einlesen der 50.000 Element-Datei dauert entsprechend lange (habe ich vorher angepasst, ist etwa 1MB groß).
Optimieren auf 1000kg ist machbar. Komme ich auf irgendwas ~ 80.000 Wert in etwa einer Sekunde.
Die 10.000kg Backpack-Challenge kann ich leider nicht machen. Out of Memory. Firefox läd sich da volle 2GB RAM und hört dann auf.
Das liegt allerdings daran, das mein Bruteforce-Ähnlicher Algorithmus richtig Speicher frisst, sobald es mehr elemente im Rucksack werden.

Daher hier mal das Ergebnis zu einer Liste aus 25.000 Elementen mit Rucksack-Gewicht von 5000
Ergebnis:
5000 86057
Datei:Anhang anzeigen Testset_25000.rar
 
You do not have permission to view link please Anmelden or Registrieren


Währst Du vielleicht so freundlich, die Ergebnisausgabe anzuhängen?
Ich hatte vermutet, wir würden ähnlich vorgehen, aber ich komme auf 2 mögliche Ergebnisse, die jeweils 4 Euro unter Deinem liegen.
 
You do not have permission to view link please Anmelden or Registrieren

[src=text]Name Gewicht Wert
5000 86057
Thing_number_4129 97 906
Thing_number_2244 92 969
Thing_number_15260 87 928
Thing_number_5236 86 957
Thing_number_17584 86 953
Thing_number_18416 85 877
Thing_number_4380 85 856
Thing_number_21799 80 981
Thing_number_9290 80 856
Thing_number_16318 80 768
Thing_number_10143 79 832
Thing_number_9801 78 676
Thing_number_14776 77 799
Thing_number_17061 76 868
Thing_number_1060 75 925
Thing_number_12478 74 939
Thing_number_2341 74 749
Thing_number_13804 74 713
Thing_number_8300 74 666
Thing_number_21650 73 961
Thing_number_5652 72 954
Thing_number_4220 72 865
Thing_number_22556 71 905
Thing_number_7321 71 667
Thing_number_7121 70 718
Thing_number_5309 69 986
Thing_number_11463 68 690
Thing_number_20038 67 746
Thing_number_23853 63 927
Thing_number_531 63 808
Thing_number_14521 62 840
Thing_number_22029 62 811
Thing_number_1735 61 995
Thing_number_3499 61 836
Thing_number_12450 59 760
Thing_number_8649 58 786
Thing_number_8091 55 827
Thing_number_20793 54 802
Thing_number_19557 54 605
Thing_number_23852 54 568
Thing_number_14498 53 976
Thing_number_23312 53 843
Thing_number_13735 53 509
Thing_number_18660 51 928
Thing_number_10578 51 531
Thing_number_21493 49 948
Thing_number_13145 49 838
Thing_number_23467 48 565
Thing_number_12197 48 446
Thing_number_14371 47 929
Thing_number_10625 46 802
Thing_number_8886 46 798
Thing_number_14564 46 779
Thing_number_8035 46 730
Thing_number_8055 46 507
Thing_number_19330 46 397
Thing_number_11179 44 833
Thing_number_11432 42 795
Thing_number_12210 42 450
Thing_number_10652 41 896
Thing_number_10050 40 825
Thing_number_24415 40 380
Thing_number_457 39 358
Thing_number_24688 37 442
Thing_number_20124 36 752
Thing_number_9678 34 358
Thing_number_17267 32 897
Thing_number_2909 32 428
Thing_number_11075 31 975
Thing_number_11479 31 791
Thing_number_23445 31 345
Thing_number_21580 30 541
Thing_number_18933 29 322
Thing_number_10948 28 297
Thing_number_14067 26 525
Thing_number_14443 25 801
Thing_number_16682 25 553
Thing_number_518 24 903
Thing_number_54 24 533
Thing_number_5313 24 523
Thing_number_14326 23 702
Thing_number_3596 22 797
Thing_number_19540 22 529
Thing_number_19194 22 406
Thing_number_24906 21 722
Thing_number_3909 20 952
Thing_number_3180 20 535
Thing_number_19732 19 681
Thing_number_23966 19 248
Thing_number_8904 18 457
Thing_number_16016 18 270
Thing_number_11907 18 237
Thing_number_12930 17 816
Thing_number_22643 17 659
Thing_number_16500 16 533
Thing_number_18532 15 683
Thing_number_16715 15 550
Thing_number_24980 14 944
Thing_number_2534 14 792
Thing_number_22504 14 307
Thing_number_14966 13 848
Thing_number_3388 13 490
Thing_number_16677 12 655
Thing_number_801 12 213
Thing_number_10162 11 601
Thing_number_5223 11 518
Thing_number_8487 10 991
Thing_number_8149 10 530
Thing_number_2782 10 436
Thing_number_12264 8 938
Thing_number_13719 8 625
Thing_number_8438 8 476
Thing_number_19884 8 322
Thing_number_4311 7 978
Thing_number_10584 7 555
Thing_number_2258 7 93
Thing_number_14391 6 676
Thing_number_8060 5 696
Thing_number_12991 5 500
Thing_number_13160 5 76
Thing_number_593 4 747
Thing_number_11577 4 589
Thing_number_9447 4 379
Thing_number_9527 2 961
Thing_number_22223 2 630
Thing_number_18664 1 390[/src]
 
Ich gestehe, ich habe keine Ahnung wie ihr auf diese Zahlen kommen könnt.... ich erkenne zwar ein Muster aus den Lösungen - aber wo es mich Gedanklich verlässt, wie entscheide ich ob ich lieber 2 x 7 kg Gegenstände einpacken anstatt von 1x8 und ein mal 1x6 ? Nur am Wert. Aber woran macht man fest ob man jetzt lieber einen großen oder doch nen kleineren Gegestand einpacke bzw. was sinnvoller ist?

Keine Ahnung wie man das Problem sinnvoll in Code wickelt.....

Ich hab das Gefühl die Lösung ist nicht so schwer, aber irgendwie alles was kleiner ist, noch einbauen als ein ersetzter plus freien Platz... fruchtete (oder ich habs falsch/nicht richtig gemacht) nicht bei mir. Aber dann weiß ich ja noch nicht ob ich auf dem richtigen Weg bin oder genug kleinere "Füllobjekte" habe...
 
Zuletzt bearbeitet:
Du kannst an der Stelle zum Beispiel prüfen, welche mehreren Gegenstände das erforderliche Gewicht aufweisen und dann prüfen, welche von den Kombinationen den höchsten Nutzen (=Wert) bringt.

Andere Vorgehensweise:
Du nimmst eine sortierte Liste und guckst mal so nach und nach, von kleinem Gewicht zu großem Gewicht, was du so einpacken könntest. Dann muss du jedes Mal prüfen, ob du irgendwie auf einen höheren Wert kommst. Tust du es, nimmst du entsprechend die höherwerte Kombination. Und dann steigerst du langsam das Gewicht, bis du bei deinem Rucksackgewicht angekommen bist.

Wenn du dann noch geschickt Daten zwischenspeicherst, hast du da auch eine Methode, die etwas effektiver als echter Bruteforce ist.

Ich hoffe das ist jetzt nicht zu genau geworden - ein wenig Hirnschmalz musst du nun ja doch noch verwenden. Ich bin mal gespannt, ob es noch eine bessere / schnellere Methode gibt oder ich bereits bei der "Musterlösung" angekommen bin :D

War halt wie gesagt ein Prozess über 8 Weiterentwicklungen, wie ich zu dem Ergebnis gekommen bin :P
 
Ich hatte schon mit einem Versuch gespielt das Gewicht zu steigern, aber dann packe ich logischerweise alle 1 kg Gegenstände ein und übergehe dabei keinen, schon aus dem Blickwinkel, die könnten alle wichtig sein.

Im Grunde müsste man ja zuerst alle Gegenstände einer Gewichtsklasse zusammenfassen die im Bereich liegen, dann von unten nach oben - wie du sagst - einpacken, und schauen ob wir noch Platz haben, also wieder bei 1 kg anfangen, mit dem nächsten höherwertigen 1 kg Gegenstand (falls vorhanden), wenn nicht einen 2 kg Gegenstand usw....
Theoretisch müsste der letzte große, passende Gegenstand das Limit irgendwie vorgeben bis auf das wir versuchen zu erhöhen.

Ich les mir deinen Post irgendwann später nochmal durch, vielleicht hab ich dann eine bessere Idee - aber das mit dem dazupacken, könnte ja schon einmal ganz gut hinkommen.
 
Gerade habe ich das Problem, dass ich nicht vernünftig die Häufigkeit eines Gewichts zählen kann.
Das stört mich...
Ich wollte einen anderen Algorithmus ausprobieren, wofür ich das brauche. Aber ich habe meine Datenstruktur entweder zu kompliziert gewählt oder ich mache da einfach grundsätzlich was falsch...
Ärgerlich...
Naja - die Tage gucke ich weiter...
 
Mir hast du auf jeden Fall nen guten Ansatz verraten ;)

Werde ich auch mal ausprobieren, zumindest hab ich es für mich glaube ich so (hier) aufgeschrieben, dass ich es vielleicht auch umsetzen könnte :D

PS: Du kannst das Gewicht hoch bzw. runterzählen und dann alle Gewichte dieser Gewichtsklasse erfassen/zählen, die im gültigen Bereich liegen. Nicht? :)
Oder halt dynamisch, und dann auf ein Array legen für diesen Wert....
 
Zuletzt bearbeitet:
Ok. Algorithmus 9 fliegt in hohem Boden wieder raus. Der kann nichts. :D
Braucht lange für ein unfassbar schlechtes Ergebnis.
 
Feature(s)? :D - Wählen sie aus 20 verschiedenen Optimierungen die sich alle gegenseitig toppen und eigentlich sollten sie nur Algo19 oder 20 benutzen, je nachdem ob es eine Sekunde oder eine Stunde dauern soll.... :p
 
theSplit schrieb:
PS: Du kannst das Gewicht hoch bzw. runterzählen und dann alle Gewichte dieser Gewichtsklasse erfassen/zählen, die im gültigen Bereich liegen. Nicht? :)
Oder halt dynamisch, und dann auf ein Array legen für diesen Wert....
Zum Vergrößern anklicken....

Hört sich nach einem Plan an ...
 
You do not have permission to view link please Anmelden or Registrieren

Es scheint, als hätte ich es mir zu einfach gemacht und dann Glück mit den Daten gehabt.

Ich habe sortiert gepackt und dann -1/+2 umgepackt.
Du hast aber ein Ergebnis, wo die Abweichung von der Sortierten Liste -2/+4 Elemente beträgt.

Da muß ich noch mal nachdenken.
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben