nach bereits längeren Planungen und Vorbereitungen sind wir nun von vBulletin auf Xenforo umgestiegen. Die Umstellung musste leider aufgrund der Serverprobleme der letzten Tage notgedrungen vorverlegt werden. Das neue Forum ist soweit voll funktionsfähig, allerdings sind noch nicht alle der gewohnten Funktionen vorhanden. Nach Möglichkeit werden wir sie in den nächsten Wochen nachrüsten. Dafür sollte es nun einige der Probleme lösen, die wir in den letzten Tagen, Wochen und Monaten hatten. Auch der Server ist nun potenter als bei unserem alten Hoster, wodurch wir nun langfristig den Tank mit Bytes vollgetankt haben.
Anfangs mag die neue Boardsoftware etwas ungewohnt sein, aber man findet sich recht schnell ein. Wir wissen, dass ihr alle Gewohnheitstiere seid, aber gebt dem neuen Board eine Chance. Sollte etwas der neuen oder auch gewohnten Funktionen unklar sein, könnt ihr den "Wo issn da der Button zu"-Thread im Feedback nutzen. Bugs meldet ihr bitte im Bugtracker, es wird sicher welche geben die uns noch nicht aufgefallen sind. Ich werde das dann versuchen, halbwegs im Startbeitrag übersichtlich zu halten, was an Arbeit noch aussteht.
Neu ist, dass die Boardsoftware deutlich besser für Mobiltelefone und diverse Endgeräte geeignet ist und nun auch im mobilen Style alle Funktionen verfügbar sind. Am Desktop findet ihr oben rechts sowohl den Umschalter zwischen hellem und dunklem Style. Am Handy ist der Hell-/Dunkelschalter am Ende der Seite. Damit sollte zukünftig jeder sein Board so konfigurieren können, wie es ihm am liebsten ist.
Die restlichen Funktionen sollten eigentlich soweit wie gewohnt funktionieren. Einfach mal ein wenig damit spielen oder bei Unklarheiten im Thread nachfragen. Viel Spaß im ngb 2.0.
Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder einen alternativen Browser verwenden.
Muss ehrlich sagen, ist schwer das auszubalancieren...
Sample output:
[src=text]---- Reading possible backpack contents ---
Reading values from file.
---- Listing possible backpack contents ----
[ 2 kg / 15 Euro] der hohe weiße Kamm
[ 4 kg / 14 Euro] der eckige schwarze Stadtplan
[ 1 kg / 3 Euro] der eckige weiße Gürtel
[ 2 kg / 6 Euro] der runde braune Schaal
[ 4 kg / 12 Euro] die handliche violette Halskette
[ 5 kg / 58 Euro] die große weiße Nagelschere
[ 6 kg / 103 Euro] das sperrige gelbe Cap
[ 7 kg / 11 Euro] das große blaue T-Shirt
[ 8 kg / 11 Euro] die mittelgroße violette Boxershorts
[ 9 kg / 19 Euro] die sperrige braune Kopfhörer
[ 10 kg / 115 Euro] das hohe braune Cap
[ 12 kg / 16 Euro] der eckige weiße Kamm
[ 16 kg / 203 Euro] der flache violette Sonnenschutz
---- Overall stats for possible contents ----
Total value / weight: 586 Euro / 86 kg
Average value / weight: 46 Euro / 7 kg
---- Packed stats ----
Capacity of backpack: 16 kg
Total value / weight: 185 Euro / 16 kg
---- Packaged contents ----
[ 15 Euro / 2 kg ] der hohe weiße Kamm
[ 3 Euro / 1 kg ] der eckige weiße Gürtel
[ 6 Euro / 2 kg ] der runde braune Schaal
[ 58 Euro / 5 kg ] die große weiße Nagelschere
[ 103 Euro / 6 kg ] das sperrige gelbe Cap
---- Alternative ----
[ 203 Euro / 16 kg ] der flache violette Sonnenschutz
bin per Zufall auf den Thread hier gestoßen und finde es gut sich ein wenig zu den challenges auszutauschen!
Habe auch schon zwei mal etwas eingereicht (Mühle-Brettspiel KI und Gesichtserkennung) und mache bei der aktuellen challenge wieder mit.
Ich finde das Problem wirklich interessant, nur etwas schade, dass man eine gute Lösung auf Grundlage von dynamischer Programmierung in sehr, sehr wenigen Zeilen Code auf die Beine stellen kann und dazu Beispiele wie Sand am Meer im Internet findet...
Man muss da wohl irgendwie anders punkten!
Hatte eigentlich vor, mit einem dynamischen Programmier-Ansatz zu beginnen und dann auf etwas ambitionierteres (genetischer Algorithmus o.Ä.) umzusteigen, allerdings sind die Ergebnisse jetzt schon so überzeugend, dass ein Wechsel kaum nötig ist.. (N=10000 und max-W: 10000 in 1s)
Welchen Lösungsweg hast du denn eingeschlagen, @theSplit?
Ich kann zur technischen Seite eher weniger sagen, aber ich habe mich auch an der dynamischen Programmierung orientiert.
Im Grunde läuft mein Code in zwei while schleifen, die innere iteriert über alle Gegenstände, die äußere so lange, bis folgende Kriterien erfüllt sind bzw. die Schleife stoppen:
a) wir können keinen Gegenstand aus der Liste mehr unterbringen
b) das Gesamtgewicht wurde erreicht
Ich komme auf folgende Laufzeiten, gemessen mit dem "time" Befehl unter Linux:
Bei N 10.000 Gegenständen, deren Gewicht maximal 1 bis 2500 kg beträgt und ein Maximalgewicht des Koffers von 10.000 kg (W):
Zur Laufzeit mit hinzuziehen sind das generieren der Eigenschaften/Namen, eine Sortierung (eventuell kann diese auch komplett wegfallen) was ein Versuch gewesen ist die Laufzeit zu optimieren (ähnlich wie bei einem Greedy-Algorithmus)
[src=text]real 0m0,434s
user 0m0,408s
sys 0m0,012s
real 0m0,464s
user 0m0,428s
sys 0m0,004s
real 0m0,347s
user 0m0,312s
sys 0m0,004s
[/src]
Die Zeiten kann man wie folgt deuten:
Real is wall clock time - time from start to finish of the call. This is all elapsed time including time slices used by other processes and time the process spends blocked (for example if it is waiting for I/O to complete).
User is the amount of CPU time spent in user-mode code (outside the kernel) within the process. This is only actual CPU time used in executing the process. Other processes and time the process spends blocked do not count towards this figure.
Sys is the amount of CPU time spent in the kernel within the process. This means executing CPU time spent in system calls within the kernel, as opposed to library code, which is still running in user-space. Like 'user', this is only CPU time used by the process. See below for a brief description of kernel mode (also known as 'supervisor' mode) and the system call mechanism.
Das klingt ja schon einmal interessant!
Du hast gesagt, dass du auch einen Ansatz aus der dynamischen Programmierung angehst, aber in der Kurzbeschreibung klingt es so als würden einfach Gegenstände hinzugefügt werden bis eines der beiden Kriterien erfüllt ist.
Nach welchen Kriterien wählst du denn die Gegenstände?
Bei mir wird zur Laufzeit die Tabelle generiert aus der anschließend die gewählten Gegenstände entnommen werden.
Die Tabelle ist jedoch N Zeilen und W Spalten groß und führt deswegen bei zu hohen Werten, wie bei deinen Tests, zu einer java.lang.OutOfMemoryError: Java heap space Exception
Das Problem wirst du wohl bei C nicht haben, deswegen wird es bei dir sowieso ein wenig knackiger laufen!
Dafür kann ich relativ stressfrei eine hübsche GUI bauen, vielleicht überzeugt das ja...
@jamestop: Im Grunde wird gesucht bis nichts mehr passt bzw. es keine alternativen mehr gibt, das ist richtig. Die Laufzeit ist daher nicht direkt konstant. Es macht ja auch einen Unterschied ob wir viele kleine Dinge einpacken und somit öfter vergleichen müssen oder ob wir größere "Pakete" haben. Also nur 4 Stück statt 200 "kleine" einpacken. Also viermal iterieren versus 200 mal... bei N Gegenständen. Jedenfalls bei meiner Lösung.
Aber ich will an dieser Stelle nicht genau vorweg nehmen wie ausgewählt wird. - Darüber sollte sich jeder selbst Gedanken machen
Ich weiß allerdings nicht ob mein Ansatz wirklich perfekt ist, er scheint erst mal nur "sinnvolle" Ergebnisse zu liefern, ob das genug ist, steht ja auf einem anderen Blatt.
Ob man die Laufzeit nicht mit einem ausgeklügelteren Algorithmus verbessern kann, sei auch mal dahingestellt.
----
Bezüglich Java können die andere bestimmt eher Tips geben als ich.
Keine Ahnung wie man da gute Datenstrukturen erzeugt. Aber ich hab es zum Beispiel so gemacht, das die Bezeichnung des Namens nur maximal 64 Zeichen beinhalten darf, 50 hätten wohl auch gereicht....
Ist vielleicht leichter wenn man nicht zu viel "overhead" hat bzw. das etwas detaillierter steuern kann, aber wie gesagt, für Java muß mal jemand anderes hier hineinhopsen.
PS: Und wenn du mal deine Laufzeiten posten kannst, wäre das auch interessant! - So zum Vergleich.
Klar, jeder sollte irgendwo sein eigenes Rezept benutzen, verstehe ich schon
war auch nur neugierig, ich bin mit meiner Lösung eigentlich schon zufrieden und mach die nächsten 20 Tage höchstes Finetuning, wenn überhaupt!
Wie gut der Ansatz von dir oder mir ist können wir ja gerne mit einem Testdaten-Beispiel testen, wenn du willst?
Dein Programm kann ja anscheinend eine Datei auslesen, in der die Gegenstände und das Maximalgewicht definiert sind. Das klappt bei mir auch schon.
Kann also gerne ein Testdatei hochladen. (Erste Zeile ist das Maximalgewicht und die Anzahl der Gegenstände - getrennt durch ein Leerzeichen, restlichen Zeilen sind Gewicht und Wert, wieder getrennt durch ein Leerzeichen)
Was die Java-Sache angeht:
Ich hab extra schon relativ schlanke Datenstrukturen benutzt und zB auf den "Namen" eines Gegenstands verzichtet.
Man hat leider trotzdem keinen großen Einfluss auf die tatsächliche Größe des Objects in der JVM.
Ich kann das Programm jedoch mit einem JVM-Parameter starten um mehr Speicher zu bekommen und jetzt läuft's auch mit 50000 Gegenständen!
Ich lasse jetzt auch mal die Rechenzeit ausgeben - aber wie gesagt Java + GUI, dadurch geht sicher etwas verloren:
N:10000 (1-2000kg), W:10000: 732ms
N:20000 (1-2000kg), W:10000: 1774ms
N:50000 (1-2000kg), W:10000: 5690ms
Mein "Greedy-Solver" braucht beim letzten Test übrigens 50ms Das Ergbnis ist natürlich schlechter...
@jamestop: Also, du kannst gerne eine Testdatei posten oder hier als zip anfügen, kein Problem.
Allerdings hab ich pro Zeile 2 Werte die mit "," oder ";" oder was auch immer getrennt sein sollten, also falls du das irgendwie so anpassen kannst, quasi CSV?
Ist die Frage wie viel Zeit für den Aufbau der GUI dazukommt, wenn du das noch rausrechnest, also Startzeit bis zur Anzeige und abzüglich der Spin-Up Zeit von Java allgemein.
Vielleicht kann man das auch noch genauer Profilieren, mit einer integrierten Zeiterfassung und dann auch Anzeige in der GUI - so als Idee.
Die Laufzeit bei N von 50k findet ich dagegen wieder sehr schnell... vielleicht muß ich auch noch einmal dabei ran , aber die meisten Sachen habe ich schon versucht durch Pre-Calculations vorweg zu nehmen... mal schauen.
Im übrigen, kannst du eventuell auch ein Beispiel/Screenshot (Ausschnitt) deiner Ausgabe, falls vorhanden, zeigen? - Also mal mit 20 Gegenständen, zwischen 1-16 kg, Maximalgewicht des Koffers 16 kg.... in wie weit das "optimal" läuft?
Hab einfach kurz mit sed die Leerzeichen durch ein ; ersetzt.
In der ersten Zeile ist noch Maximalgewicht und Anzahl der Gegenstände, musst du eventuell für dein Programm entfernen.
Die Anzeige und Zeitberechnung finden bei mir schon innerhalb der GUI statt, aber durch Garbage Collection etc. kann ich mir vorstellen, dass ein kleiner Overhead entsteht.
Hab vor purem C leider zu viel Angst um sonderlich produktiv zu sein
Allerdings habe ich das Programm jetzt mal Abseits der IDE durchlaufen lassen und komme bei dem Testversuch (im Anhang) auf 3324ms
Klar, ich hab hier mal die Ausgabe für das Beispiel:
_______________________
Berechne 20 Gegenstände und 16kg Maximalgewicht mit Dynamic Solver...
@jamestop: Ich gib dir morgen mal ein Ergebnis mit deinen Testdaten.
Allerdings logisch, weil ist ja mit GUI.... sieht man ja nicht nach welcher Strategie dein Code die Gegenstände auswählt, also für ein Beispiel ob die "optimale" Lösung gefunden wird, wäre natürlich auch noch gut als Proof-of-concept das vergleichen zu können.
Moin Leute,
ich überlege mir gerade in den kommenden Tagen vielleicht auch mal ein paar Zeilen zu schreiben. Klingt nach einem lösbaren Problem. Und da ich keine Lust habe nur irgendwas nachzubauen, werde ich auch Google möglichst wenig befragen und mal ganz "dumm" an das Problem rangehen und verschiedene Ansätze ausprobieren und vielleicht finde ich ja einen recht guten.
Ich habe mir die aktuellen Bedingungen noch nicht angeguckt, aber ich überlege mir noch, ob ich in C++ oder in JavaScript (p5/processing) was zusammenkloppe.
In C++ tue ich mich allerdings immer ein wenig schwer mit den Programmen - besonders, weil ich immer Probleme habe entsprechende Compiler zu installieren usw. Aber das ist ja auch ein überwindbares Problem.
Wenn nichts mehr geht, schreibe ich einfach irgendwas in Python - sehr einfach zu implementieren - etwas zu einfache Syntax und entsprechend langsam aber hey. Erstmal etwas Code erschaffen
@theSplit: Derzeit habe ich Cygwin mit gcc bzw g++ installiert.
Für aktuelle Sachen komme ich damit einigermaßen klar. Aber ist alles auch noch etwas Gewöhnungssache ;-)
@Roin: Was auch nicht verkehrt ist, Msys2 - welches, soweit ich im Bilde bin, auf Cygwin aufbaut/davon abgeleitet wurde.
Habs allerdings noch nicht mit g++ getestet - aber glaube das nimmt sich nicht viel.
Man muß sich dabei nur an "pacman" gewöhnen, aber dafür gibt es ein paar nette Guides auf der Msys Seite und auf Github.
Also falls du das mal testen willst
@jamestop: Habe deine Testaufgabe mal durchlaufen lassen, auf einem anderen Rechner.
Habe eine Laufzeut von: circa 9,766 Sekunden (ich kann aber heute Abend nochmal einen Wert von meinem Rechner posten, da habe ich auch noch versucht etwas zu optimieren).
Ich komme auf folgendes Ergebnis des Packens:
[src=text]---- Packed stats ----
Capacity of backpack: 10000 kg
Total value / weight: 287384 Euro / 9999 kg[/src]
Auf was für ein Ergebnis kommst du denn mit deinem Pack-Algorithmus? Wenn du dir das ausgeben lässt? (Wert der Inhalte und Gewicht) ?
Update:
Hier nochmal die neusten Stats mit einer kleine Optimierung:
[src=text]---- Overall stats for possible contents ----
Total value / weight: 12785605 Euro / 24880788 kg
Average value / weight: 256 Euro / 498 kg
---- Packed stats ----
Capacity of backpack: 10000 kg
Total value / weight: 287384 Euro / 9999 kg
---- Packaged contents ----
[...]
------- Finished packaging -------
Laufzeit:
real 0m9,078s
user 0m8,804s
sys 0m0,076s[/src]
Ich konnte zwischen 300 und 600 ms noch wett machen durch eine Optimierung, bei der nur noch Elemente genutzt werden, die wirklich innerhalb des noch tragbaren Gewichts liegen, durch eine Sortierung aller Elemente, nach Gewicht und entsprechend Verzweigungen.
Ja, mit der "optimalen Lösung" für ein großen Test hast du schon Recht, ich habe leider keine großen Test-Probleme im Internet gefunden und damit nur bei kleinen Tests verifizieren können, dass auch wirklich das beste Ergebnis gefunden wurde.
Ich hab doch noch ein wenig rumgeschraubt und es mal mit beiden Verfahren durchlaufen lassen:
Berechne 50000 Gegenstände und 10000kg Maximalgewicht mit Greedy Solver...
Es sieht also so aus als hätte dein Programm zwar eine gute, aber nicht optimale Lösung gefunden!
Oder der Fehler liegt in meinem Programm, aber der Aufwand zum Überprüfen ist mir zu hoch, also gehe ich natürlich vom ersten aus
So - das Grundprogramm steht.
Jetzt muss ich lediglich noch sinnvolle Selections-Algorithmen schreiben.
Für die Tests habe ich derzeit noch keine echte "Auswertung" geschrieben. Mal sehen was mir da so einfällt.
Ich bin übrigens mit JavaScript unterwegs. C++ wollte nach einigen Minuten noch nicht so richtig - da habe ich Kurzerhand umgeschwenkt.
Vielleicht schreibe ich auch noch was in der Richtung ein, dass ich die oben genannte Testdatei nutzen kann... Derzeit erzeuge ich mir meine Gegenstände per Zufall selbst. Das war ja auch nach Aufgabenstellung mehr oder minder so gewünscht/erlaubt.
So
Ich habe jetzt insgesamt 8 verschiedene Algorithmen reingehämmert. (Darf man auch keinem erzählen, wie schwer man sich damit tun kann, mit den Datentypen vernünftig umzugehen, wenn man es schon ne ganze Weile nicht mehr gemacht hat. Überall stand ständig undefinied und ich habe gesucht ohne Ende...)
4 Algorithmen sind sehr "dumm" aber dafür auch entsprechend fix. Einer ist leider nicht zielführend, da das Verfahren offensichtlich nicht für diese Art von Problemen gedacht ist - ich hatte da eine Idee aus meiner Schulzeit - hat leider nicht das gebracht, was ich gehofft habe.
Und zwei meiner Algorithmen sind schon nicht schlecht, denke ich.
Einer behilft sich mit einer kleinen Berechnung und entsprechender Sortierung (ich sortiere in jedem meiner Algorithmen... Keine Ahnung, ob das überhaupt überall sinnvoll ist, aber so konnte ich es mir dann irgendwie einfacher vorstellen).
Der andere kommt mir schon fast wie Brute-Force vor - bringt mir allerdings auch die besten Ergebnisse - da muss ich vielleicht doch mal Google anwerfen, ob ich da nicht sogar irgendso einen komischen Algorithmus nachgebaut habe, den sich wer vor x Jahrhunderten mal überlegt hat.
Wie weit wollen wir unsere Lösungsmethoden hier besprechen?
Lasst ihr mehrere Algorithmen durchlaufen und prüft dann, bei welchem das bessere Ergebnis rauskam?
Ich werde in den nächsten Tagen irgendwann noch etwas zum Daten einlesen bauen.
Aber so als Vergleich:
1000 Testdatensätze in 200ms +- 20ms berechnet (ohne Anzeige) mit JavaScript auf einem i7 4x3,1GHz allerdings auch nur mit Prozessorauslastung von wenigen Prozenten. (Firefox in Benutzung)
1000 Gegenstände mit Gewicht bis 1,1*1000 und Wert bis 100
[src=text]Name;Gewicht;Wert
Thing number 1;47;70
Thing number 2;403;29
Thing number 3;36;98
Thing number 4;345;21
Thing number 5;958;37
Thing number 6;398;8
Thing number 7;75;42
Thing number 8;29;7
Thing number 9;345;46
Thing number 10;683;45
Thing number 11;1069;29
Thing number 12;34;77
Thing number 13;71;12
Thing number 14;657;69
Thing number 15;764;85
Thing number 16;933;14
Thing number 17;116;95
Thing number 18;309;87
Thing number 19;59;91
Thing number 20;377;93
Thing number 21;1036;91
Thing number 22;850;41
Thing number 23;995;98
Thing number 24;1022;12
Thing number 25;878;69
Thing number 26;407;81
Thing number 27;629;45
Thing number 28;425;56
Thing number 29;1024;66
Thing number 30;270;40
Thing number 31;272;25
Thing number 32;701;44
Thing number 33;1016;10
Thing number 34;991;43
Thing number 35;767;41
Thing number 36;423;73
Thing number 37;708;28
Thing number 38;349;20
Thing number 39;99;15
Thing number 40;113;44
Thing number 41;928;72
Thing number 42;841;17
Thing number 43;962;76
Thing number 44;208;43
Thing number 45;690;64
Thing number 46;995;42
Thing number 47;61;97
Thing number 48;1083;42
Thing number 49;1092;24
Thing number 50;572;38
Thing number 51;396;45
Thing number 52;943;31
Thing number 53;781;27
Thing number 54;44;70
Thing number 55;862;91
Thing number 56;302;86
Thing number 57;146;58
Thing number 58;498;80
Thing number 59;908;98
Thing number 60;158;65
Thing number 61;838;94
Thing number 62;1024;7
Thing number 63;718;54
Thing number 64;1091;11
Thing number 65;34;39
Thing number 66;125;74
Thing number 67;587;95
Thing number 68;436;12
Thing number 69;141;73
Thing number 70;779;95
Thing number 71;61;44
Thing number 72;529;21
Thing number 73;964;39
Thing number 74;543;85
Thing number 75;383;37
Thing number 76;775;25
Thing number 77;675;36
Thing number 78;850;45
Thing number 79;107;10
Thing number 80;403;49
Thing number 81;557;61
Thing number 82;270;51
Thing number 83;152;83
Thing number 84;378;54
Thing number 85;1027;41
Thing number 86;230;8
Thing number 87;237;79
Thing number 88;651;29
Thing number 89;209;34
Thing number 90;810;53
Thing number 91;166;86
Thing number 92;14;95
Thing number 93;368;17
Thing number 94;799;28
Thing number 95;399;37
Thing number 96;395;32
Thing number 97;978;82
Thing number 98;1089;55
Thing number 99;159;4
Thing number 100;674;50
Thing number 101;843;96
Thing number 102;356;72
Thing number 103;34;70
Thing number 104;453;14
Thing number 105;758;70
Thing number 106;1014;20
Thing number 107;284;83
Thing number 108;1093;58
Thing number 109;77;53
Thing number 110;920;42
Thing number 111;485;50
Thing number 112;177;84
Thing number 113;74;43
Thing number 114;518;53
Thing number 115;475;67
Thing number 116;888;80
Thing number 117;620;45
Thing number 118;646;94
Thing number 119;1000;78
Thing number 120;28;99
Thing number 121;339;5
Thing number 122;295;63
Thing number 123;556;58
Thing number 124;140;95
Thing number 125;747;13
Thing number 126;1047;23
Thing number 127;117;12
Thing number 128;519;55
Thing number 129;156;7
Thing number 130;984;55
Thing number 131;979;60
Thing number 132;868;35
Thing number 133;389;42
Thing number 134;477;17
Thing number 135;1065;9
Thing number 136;960;36
Thing number 137;589;91
Thing number 138;643;76
Thing number 139;176;49
Thing number 140;35;21
Thing number 141;981;58
Thing number 142;874;88
Thing number 143;388;5
Thing number 144;596;22
Thing number 145;1050;87
Thing number 146;456;9
Thing number 147;379;6
Thing number 148;549;79
Thing number 149;755;89
Thing number 150;216;69
Thing number 151;489;81
Thing number 152;796;1
Thing number 153;202;73
Thing number 154;457;59
Thing number 155;434;41
Thing number 156;998;89
Thing number 157;364;89
Thing number 158;392;42
Thing number 159;684;51
Thing number 160;200;74
Thing number 161;982;18
Thing number 162;768;5
Thing number 163;98;37
Thing number 164;140;51
Thing number 165;334;99
Thing number 166;318;16
Thing number 167;685;72
Thing number 168;362;70
Thing number 169;1036;100
Thing number 170;1019;59
Thing number 171;942;47
Thing number 172;281;9
Thing number 173;862;35
Thing number 174;270;40
Thing number 175;656;27
Thing number 176;120;60
Thing number 177;49;61
Thing number 178;1073;98
Thing number 179;1026;79
Thing number 180;732;21
Thing number 181;817;94
Thing number 182;57;21
Thing number 183;265;31
Thing number 184;707;69
Thing number 185;918;56
Thing number 186;667;81
Thing number 187;490;12
Thing number 188;45;64
Thing number 189;343;25
Thing number 190;300;96
Thing number 191;105;44
Thing number 192;182;76
Thing number 193;6;53
Thing number 194;454;2
Thing number 195;447;88
Thing number 196;334;71
Thing number 197;947;85
Thing number 198;1066;21
Thing number 199;450;38
Thing number 200;1086;33
Thing number 201;866;91
Thing number 202;1054;31
Thing number 203;311;66
Thing number 204;882;31
Thing number 205;6;81
Thing number 206;326;50
Thing number 207;26;95
Thing number 208;11;28
Thing number 209;737;89
Thing number 210;80;72
Thing number 211;26;47
Thing number 212;471;23
Thing number 213;401;90
Thing number 214;1018;30
Thing number 215;862;21
Thing number 216;303;28
Thing number 217;573;34
Thing number 218;370;88
Thing number 219;642;38
Thing number 220;772;14
Thing number 221;12;81
Thing number 222;379;48
Thing number 223;173;11
Thing number 224;1085;45
Thing number 225;1027;84
Thing number 226;48;36
Thing number 227;303;67
Thing number 228;1030;43
Thing number 229;998;72
Thing number 230;774;95
Thing number 231;716;61
Thing number 232;531;92
Thing number 233;611;61
Thing number 234;588;44
Thing number 235;579;75
Thing number 236;48;34
Thing number 237;617;48
Thing number 238;785;98
Thing number 239;1100;49
Thing number 240;320;89
Thing number 241;1025;45
Thing number 242;46;92
Thing number 243;185;83
Thing number 244;820;87
Thing number 245;361;96
Thing number 246;162;27
Thing number 247;233;93
Thing number 248;881;19
Thing number 249;67;90
Thing number 250;635;92
Thing number 251;168;34
Thing number 252;862;92
Thing number 253;218;30
Thing number 254;480;44
Thing number 255;710;13
Thing number 256;658;85
Thing number 257;487;85
Thing number 258;526;41
Thing number 259;197;6
Thing number 260;218;27
Thing number 261;25;45
Thing number 262;76;9
Thing number 263;267;51
Thing number 264;430;40
Thing number 265;46;90
Thing number 266;773;40
Thing number 267;190;39
Thing number 268;1062;89
Thing number 269;800;42
Thing number 270;437;85
Thing number 271;827;96
Thing number 272;329;16
Thing number 273;315;33
Thing number 274;794;63
Thing number 275;269;3
Thing number 276;44;100
Thing number 277;906;20
Thing number 278;753;86
Thing number 279;1006;63
Thing number 280;944;50
Thing number 281;912;39
Thing number 282;269;90
Thing number 283;772;18
Thing number 284;1040;22
Thing number 285;983;40
Thing number 286;1074;51
Thing number 287;873;44
Thing number 288;89;9
Thing number 289;841;21
Thing number 290;792;46
Thing number 291;414;85
Thing number 292;92;92
Thing number 293;452;27
Thing number 294;853;68
Thing number 295;257;94
Thing number 296;386;14
Thing number 297;722;63
Thing number 298;244;22
Thing number 299;711;96
Thing number 300;610;28
Thing number 301;470;18
Thing number 302;177;53
Thing number 303;790;22
Thing number 304;258;86
Thing number 305;1000;83
Thing number 306;159;9
Thing number 307;265;36
Thing number 308;395;95
Thing number 309;424;44
Thing number 310;769;39
Thing number 311;297;77
Thing number 312;266;64
Thing number 313;23;83
Thing number 314;417;9
Thing number 315;991;33
Thing number 316;553;89
Thing number 317;170;13
Thing number 318;1025;92
Thing number 319;47;12
Thing number 320;732;95
Thing number 321;27;10
Thing number 322;897;6
Thing number 323;499;29
Thing number 324;480;82
Thing number 325;1074;23
Thing number 326;166;55
Thing number 327;765;95
Thing number 328;641;70
Thing number 329;799;9
Thing number 330;603;20
Thing number 331;453;96
Thing number 332;613;23
Thing number 333;1092;43
Thing number 334;540;14
Thing number 335;823;22
Thing number 336;973;44
Thing number 337;31;68
Thing number 338;866;100
Thing number 339;325;89
Thing number 340;798;80
Thing number 341;904;71
Thing number 342;414;90
Thing number 343;263;6
Thing number 344;75;36
Thing number 345;889;74
Thing number 346;135;1
Thing number 347;101;8
Thing number 348;530;49
Thing number 349;735;65
Thing number 350;889;77
Thing number 351;939;25
Thing number 352;302;96
Thing number 353;994;21
Thing number 354;149;87
Thing number 355;209;19
Thing number 356;26;79
Thing number 357;1090;86
Thing number 358;166;27
Thing number 359;400;24
Thing number 360;549;46
Thing number 361;1004;51
Thing number 362;1079;66
Thing number 363;313;85
Thing number 364;713;6
Thing number 365;59;62
Thing number 366;618;6
Thing number 367;960;66
Thing number 368;998;56
Thing number 369;869;7
Thing number 370;993;57
Thing number 371;659;57
Thing number 372;829;13
Thing number 373;466;49
Thing number 374;384;10
Thing number 375;309;9
Thing number 376;81;27
Thing number 377;719;17
Thing number 378;130;17
Thing number 379;669;20
Thing number 380;262;60
Thing number 381;635;31
Thing number 382;408;58
Thing number 383;539;28
Thing number 384;912;36
Thing number 385;117;67
Thing number 386;407;85
Thing number 387;687;68
Thing number 388;233;7
Thing number 389;900;96
Thing number 390;433;68
Thing number 391;405;40
Thing number 392;874;38
Thing number 393;576;29
Thing number 394;481;18
Thing number 395;660;10
Thing number 396;895;4
Thing number 397;671;70
Thing number 398;661;68
Thing number 399;874;4
Thing number 400;716;80
Thing number 401;22;72
Thing number 402;947;1
Thing number 403;785;94
Thing number 404;775;98
Thing number 405;397;4
Thing number 406;832;77
Thing number 407;283;14
Thing number 408;649;64
Thing number 409;459;59
Thing number 410;67;18
Thing number 411;435;24
Thing number 412;631;44
Thing number 413;459;15
Thing number 414;970;70
Thing number 415;37;2
Thing number 416;800;54
Thing number 417;847;40
Thing number 418;418;74
Thing number 419;640;14
Thing number 420;233;35
Thing number 421;330;73
Thing number 422;869;50
Thing number 423;177;10
Thing number 424;754;8
Thing number 425;495;86
Thing number 426;845;92
Thing number 427;790;81
Thing number 428;670;9
Thing number 429;806;76
Thing number 430;349;39
Thing number 431;679;34
Thing number 432;638;18
Thing number 433;768;56
Thing number 434;230;38
Thing number 435;423;57
Thing number 436;191;4
Thing number 437;101;68
Thing number 438;98;68
Thing number 439;97;1
Thing number 440;806;31
Thing number 441;900;48
Thing number 442;213;67
Thing number 443;669;12
Thing number 444;245;54
Thing number 445;976;96
Thing number 446;350;51
Thing number 447;172;91
Thing number 448;607;88
Thing number 449;925;81
Thing number 450;422;27
Thing number 451;818;50
Thing number 452;273;76
Thing number 453;268;78
Thing number 454;940;96
Thing number 455;1082;98
Thing number 456;406;100
Thing number 457;52;35
Thing number 458;993;10
Thing number 459;538;52
Thing number 460;164;40
Thing number 461;773;76
Thing number 462;381;69
Thing number 463;452;12
Thing number 464;505;5
Thing number 465;145;76
Thing number 466;315;8
Thing number 467;164;92
Thing number 468;632;38
Thing number 469;581;9
Thing number 470;1035;77
Thing number 471;67;27
Thing number 472;942;25
Thing number 473;895;71
Thing number 474;580;58
Thing number 475;278;53
Thing number 476;850;52
Thing number 477;181;15
Thing number 478;678;34
Thing number 479;713;55
Thing number 480;35;96
Thing number 481;562;5
Thing number 482;829;61
Thing number 483;171;25
Thing number 484;197;17
Thing number 485;296;12
Thing number 486;787;41
Thing number 487;756;89
Thing number 488;10;36
Thing number 489;944;9
Thing number 490;645;50
Thing number 491;619;1
Thing number 492;730;56
Thing number 493;806;71
Thing number 494;882;66
Thing number 495;503;51
Thing number 496;841;32
Thing number 497;634;35
Thing number 498;142;38
Thing number 499;195;28
Thing number 500;829;30
Thing number 501;432;40
Thing number 502;1003;66
Thing number 503;846;47
Thing number 504;569;59
Thing number 505;730;89
Thing number 506;206;24
Thing number 507;884;91
Thing number 508;610;13
Thing number 509;1061;45
Thing number 510;952;20
Thing number 511;922;86
Thing number 512;118;76
Thing number 513;807;75
Thing number 514;532;41
Thing number 515;1024;44
Thing number 516;392;36
Thing number 517;259;84
Thing number 518;1091;1
Thing number 519;971;18
Thing number 520;329;87
Thing number 521;51;1
Thing number 522;390;75
Thing number 523;496;65
Thing number 524;317;65
Thing number 525;242;34
Thing number 526;475;86
Thing number 527;715;63
Thing number 528;568;57
Thing number 529;472;94
Thing number 530;761;47
Thing number 531;545;32
Thing number 532;865;31
Thing number 533;423;35
Thing number 534;766;86
Thing number 535;844;54
Thing number 536;854;49
Thing number 537;7;30
Thing number 538;357;70
Thing number 539;1015;93
Thing number 540;73;29
Thing number 541;94;2
Thing number 542;1054;23
Thing number 543;717;84
Thing number 544;595;65
Thing number 545;77;90
Thing number 546;762;86
Thing number 547;848;31
Thing number 548;34;90
Thing number 549;754;85
Thing number 550;972;96
Thing number 551;382;86
Thing number 552;15;48
Thing number 553;425;88
Thing number 554;387;67
Thing number 555;637;80
Thing number 556;421;55
Thing number 557;623;92
Thing number 558;1068;34
Thing number 559;252;28
Thing number 560;24;24
Thing number 561;348;97
Thing number 562;246;38
Thing number 563;21;44
Thing number 564;777;18
Thing number 565;1014;85
Thing number 566;306;1
Thing number 567;863;23
Thing number 568;669;6
Thing number 569;102;69
Thing number 570;344;44
Thing number 571;24;67
Thing number 572;310;65
Thing number 573;257;99
Thing number 574;248;98
Thing number 575;508;6
Thing number 576;1029;31
Thing number 577;560;41
Thing number 578;202;80
Thing number 579;380;72
Thing number 580;691;40
Thing number 581;324;61
Thing number 582;918;31
Thing number 583;338;35
Thing number 584;272;72
Thing number 585;1020;64
Thing number 586;713;82
Thing number 587;413;31
Thing number 588;102;35
Thing number 589;389;16
Thing number 590;606;68
Thing number 591;872;70
Thing number 592;696;85
Thing number 593;770;63
Thing number 594;93;35
Thing number 595;474;20
Thing number 596;709;58
Thing number 597;336;48
Thing number 598;771;6
Thing number 599;117;73
Thing number 600;768;90
Thing number 601;67;71
Thing number 602;350;51
Thing number 603;298;80
Thing number 604;450;87
Thing number 605;834;28
Thing number 606;763;95
Thing number 607;366;52
Thing number 608;1039;66
Thing number 609;153;82
Thing number 610;743;59
Thing number 611;1071;11
Thing number 612;649;75
Thing number 613;330;69
Thing number 614;180;75
Thing number 615;764;2
Thing number 616;76;75
Thing number 617;761;46
Thing number 618;416;95
Thing number 619;135;78
Thing number 620;720;43
Thing number 621;41;72
Thing number 622;37;84
Thing number 623;818;62
Thing number 624;908;87
Thing number 625;79;62
Thing number 626;454;15
Thing number 627;292;77
Thing number 628;409;17
Thing number 629;324;93
Thing number 630;801;83
Thing number 631;794;67
Thing number 632;658;40
Thing number 633;711;45
Thing number 634;121;18
Thing number 635;767;54
Thing number 636;906;96
Thing number 637;867;66
Thing number 638;239;23
Thing number 639;858;75
Thing number 640;912;88
Thing number 641;1100;29
Thing number 642;1030;37
Thing number 643;1091;19
Thing number 644;776;85
Thing number 645;605;62
Thing number 646;535;20
Thing number 647;843;11
Thing number 648;307;51
Thing number 649;262;49
Thing number 650;1053;25
Thing number 651;165;94
Thing number 652;30;40
Thing number 653;918;6
Thing number 654;119;37
Thing number 655;206;81
Thing number 656;437;14
Thing number 657;625;4
Thing number 658;294;49
Thing number 659;935;61
Thing number 660;177;89
Thing number 661;374;76
Thing number 662;156;63
Thing number 663;371;69
Thing number 664;809;14
Thing number 665;228;97
Thing number 666;533;60
Thing number 667;732;11
Thing number 668;930;43
Thing number 669;962;75
Thing number 670;926;87
Thing number 671;926;39
Thing number 672;822;2
Thing number 673;745;88
Thing number 674;641;22
Thing number 675;729;11
Thing number 676;24;2
Thing number 677;811;27
Thing number 678;939;13
Thing number 679;42;11
Thing number 680;719;82
Thing number 681;309;100
Thing number 682;948;36
Thing number 683;994;44
Thing number 684;44;57
Thing number 685;720;88
Thing number 686;540;51
Thing number 687;546;33
Thing number 688;962;4
Thing number 689;430;21
Thing number 690;975;82
Thing number 691;397;77
Thing number 692;920;29
Thing number 693;381;91
Thing number 694;447;30
Thing number 695;112;83
Thing number 696;902;5
Thing number 697;422;47
Thing number 698;916;28
Thing number 699;531;64
Thing number 700;1073;52
Thing number 701;1018;39
Thing number 702;891;61
Thing number 703;979;32
Thing number 704;946;68
Thing number 705;446;41
Thing number 706;177;99
Thing number 707;1043;6
Thing number 708;1016;59
Thing number 709;53;52
Thing number 710;156;40
Thing number 711;698;33
Thing number 712;986;97
Thing number 713;1079;37
Thing number 714;945;48
Thing number 715;33;24
Thing number 716;12;100
Thing number 717;818;49
Thing number 718;447;94
Thing number 719;902;88
Thing number 720;305;32
Thing number 721;47;56
Thing number 722;941;11
Thing number 723;923;82
Thing number 724;1078;100
Thing number 725;505;93
Thing number 726;283;6
Thing number 727;751;45
Thing number 728;1015;70
Thing number 729;986;28
Thing number 730;716;74
Thing number 731;540;7
Thing number 732;1039;6
Thing number 733;155;88
Thing number 734;222;6
Thing number 735;602;18
Thing number 736;610;82
Thing number 737;777;73
Thing number 738;838;75
Thing number 739;274;44
Thing number 740;880;94
Thing number 741;601;37
Thing number 742;873;70
Thing number 743;917;58
Thing number 744;640;98
Thing number 745;495;91
Thing number 746;116;93
Thing number 747;653;13
Thing number 748;609;98
Thing number 749;55;8
Thing number 750;38;56
Thing number 751;922;46
Thing number 752;625;94
Thing number 753;372;21
Thing number 754;36;47
Thing number 755;393;96
Thing number 756;17;10
Thing number 757;684;45
Thing number 758;734;67
Thing number 759;407;46
Thing number 760;152;1
Thing number 761;813;87
Thing number 762;678;87
Thing number 763;223;40
Thing number 764;98;80
Thing number 765;161;76
Thing number 766;53;23
Thing number 767;640;57
Thing number 768;315;49
Thing number 769;80;21
Thing number 770;224;61
Thing number 771;305;26
Thing number 772;541;23
Thing number 773;282;48
Thing number 774;118;96
Thing number 775;578;74
Thing number 776;497;90
Thing number 777;31;85
Thing number 778;418;24
Thing number 779;321;46
Thing number 780;614;3
Thing number 781;153;83
Thing number 782;645;94
Thing number 783;777;82
Thing number 784;960;69
Thing number 785;862;46
Thing number 786;162;55
Thing number 787;476;26
Thing number 788;88;75
Thing number 789;474;85
Thing number 790;878;76
Thing number 791;529;9
Thing number 792;575;18
Thing number 793;303;13
Thing number 794;627;29
Thing number 795;406;64
Thing number 796;1039;91
Thing number 797;791;64
Thing number 798;600;75
Thing number 799;577;20
Thing number 800;120;36
Thing number 801;445;50
Thing number 802;988;14
Thing number 803;587;23
Thing number 804;571;77
Thing number 805;730;14
Thing number 806;530;72
Thing number 807;310;17
Thing number 808;688;57
Thing number 809;500;54
Thing number 810;974;10
Thing number 811;656;63
Thing number 812;912;73
Thing number 813;172;78
Thing number 814;960;83
Thing number 815;23;5
Thing number 816;656;14
Thing number 817;232;56
Thing number 818;538;75
Thing number 819;688;44
Thing number 820;1059;24
Thing number 821;386;100
Thing number 822;457;78
Thing number 823;759;82
Thing number 824;732;40
Thing number 825;166;15
Thing number 826;482;97
Thing number 827;240;100
Thing number 828;267;70
Thing number 829;224;70
Thing number 830;15;58
Thing number 831;203;79
Thing number 832;915;87
Thing number 833;389;35
Thing number 834;37;74
Thing number 835;309;26
Thing number 836;1025;55
Thing number 837;963;17
Thing number 838;671;73
Thing number 839;303;10
Thing number 840;138;75
Thing number 841;255;9
Thing number 842;577;60
Thing number 843;226;87
Thing number 844;143;73
Thing number 845;286;52
Thing number 846;490;53
Thing number 847;783;11
Thing number 848;57;51
Thing number 849;240;59
Thing number 850;741;67
Thing number 851;523;91
Thing number 852;41;86
Thing number 853;16;36
Thing number 854;217;32
Thing number 855;139;62
Thing number 856;1004;33
Thing number 857;861;35
Thing number 858;249;37
Thing number 859;585;71
Thing number 860;293;94
Thing number 861;181;20
Thing number 862;572;81
Thing number 863;41;91
Thing number 864;560;67
Thing number 865;270;23
Thing number 866;91;70
Thing number 867;163;24
Thing number 868;989;96
Thing number 869;511;59
Thing number 870;232;62
Thing number 871;195;92
Thing number 872;122;80
Thing number 873;59;1
Thing number 874;72;93
Thing number 875;268;61
Thing number 876;622;80
Thing number 877;913;34
Thing number 878;30;33
Thing number 879;418;12
Thing number 880;110;10
Thing number 881;418;86
Thing number 882;398;78
Thing number 883;182;28
Thing number 884;415;86
Thing number 885;561;13
Thing number 886;16;76
Thing number 887;347;66
Thing number 888;333;39
Thing number 889;876;1
Thing number 890;783;92
Thing number 891;467;76
Thing number 892;1058;34
Thing number 893;498;95
Thing number 894;111;63
Thing number 895;945;40
Thing number 896;958;28
Thing number 897;208;18
Thing number 898;285;74
Thing number 899;733;76
Thing number 900;121;1
Thing number 901;340;73
Thing number 902;320;57
Thing number 903;376;65
Thing number 904;482;82
Thing number 905;539;80
Thing number 906;436;80
Thing number 907;78;76
Thing number 908;607;100
Thing number 909;138;40
Thing number 910;1074;30
Thing number 911;224;27
Thing number 912;530;1
Thing number 913;904;85
Thing number 914;558;94
Thing number 915;414;71
Thing number 916;1047;36
Thing number 917;94;23
Thing number 918;609;34
Thing number 919;737;43
Thing number 920;754;68
Thing number 921;475;19
Thing number 922;431;97
Thing number 923;382;67
Thing number 924;590;52
Thing number 925;237;77
Thing number 926;831;7
Thing number 927;875;34
Thing number 928;183;88
Thing number 929;187;31
Thing number 930;1010;67
Thing number 931;942;61
Thing number 932;785;5
Thing number 933;381;30
Thing number 934;95;58
Thing number 935;306;65
Thing number 936;1065;29
Thing number 937;949;70
Thing number 938;472;30
Thing number 939;89;96
Thing number 940;248;79
Thing number 941;125;44
Thing number 942;781;17
Thing number 943;419;28
Thing number 944;585;27
Thing number 945;687;71
Thing number 946;996;56
Thing number 947;695;68
Thing number 948;632;13
Thing number 949;694;89
Thing number 950;772;9
Thing number 951;942;100
Thing number 952;549;99
Thing number 953;473;13
Thing number 954;222;71
Thing number 955;750;95
Thing number 956;145;97
Thing number 957;788;61
Thing number 958;4;33
Thing number 959;449;92
Thing number 960;149;90
Thing number 961;791;64
Thing number 962;962;34
Thing number 963;936;48
Thing number 964;162;83
Thing number 965;566;37
Thing number 966;202;73
Thing number 967;982;51
Thing number 968;680;10
Thing number 969;772;87
Thing number 970;860;1
Thing number 971;785;18
Thing number 972;105;64
Thing number 973;488;23
Thing number 974;35;99
Thing number 975;517;2
Thing number 976;1063;75
Thing number 977;893;86
Thing number 978;114;64
Thing number 979;261;66
Thing number 980;672;71
Thing number 981;1008;31
Thing number 982;455;43
Thing number 983;353;47
Thing number 984;211;12
Thing number 985;803;62
Thing number 986;408;47
Thing number 987;534;10
Thing number 988;105;30
Thing number 989;824;24
Thing number 990;734;86
Thing number 991;1086;1
Thing number 992;722;28
Thing number 993;483;32
Thing number 994;600;23
Thing number 995;940;26
Thing number 996;495;18
Thing number 997;171;85
Thing number 998;91;11
Thing number 999;604;63
Thing number 1000;850;26
Gesamtgewicht: 535032
Gesamtwert: 51953
[/src]
Ergebnis:
[src=text]Thing number 242;46;92
Thing number 265;46;90
Thing number 276;44;100
Thing number 863;41;91
Thing number 852;41;86
Thing number 621;41;72
Thing number 622;37;84
Thing number 834;37;74
Thing number 3;36;98
Thing number 974;35;99
Thing number 480;35;96
Thing number 548;34;90
Thing number 12;34;77
Thing number 103;34;70
Thing number 777;31;85
Thing number 337;31;68
Thing number 652;30;40
Thing number 120;28;99
Thing number 207;26;95
Thing number 356;26;79
Thing number 211;26;47
Thing number 261;25;45
Thing number 571;24;67
Thing number 313;23;83
Thing number 401;22;72
Thing number 563;21;44
Thing number 886;16;76
Thing number 853;16;36
Thing number 830;15;58
Thing number 552;15;48
Thing number 92;14;95
Thing number 716;12;100
Thing number 221;12;81
Thing number 208;11;28
Thing number 488;10;36
Thing number 537;7;30
Thing number 205;6;81
Thing number 193;6;53
Thing number 958;4;33
Gesamtgewicht: 998
Gesamtwert: 2798
[/src]
Noch ein weiterer Test:
10000 kg, Gegenstände und maximaler Wert pro Gegenstand.
~30 Sekunden für einen Durchlauf.
Damit ist klar zu sehen. JavaScript nutzt nur sehr beschränkte Ressourcen des Browsers. Dennoch gar nicht mal so schlecht.
EDIT: Nocheinmal einen anderen Datensatz mit je 10.000 Ausprobiert - in Ausnahmen sogar nur 14 Sekunden!
@Roin: Ich habe mal mit deinen Zahlen durchlaufen lassen:
Da bekomme ich aber ein ganz anderes Ergebnis....
"Capacity of backpack: 10000 kg
Total value / weight: 8868 Euro / 10000 kg"
Aber 8 Algorithmen so schnell zu implementieren, das ist schon hart
@jamestop:
Also dein Greedy Solver scheint das gleiche Ergebnis zu liefern, aber bei viel geringerer Laufzeit....
Ich müsste echt mal schauen ob ich bei mir nicht doch irgendwie anders optimieren kann.
---
Aktuell mache ich es so, das ich nach einem fixen Kriterium einen einzigen Kandidaten herauspicke und schaue ob wir nicht eine bessere Alternative finden können innerhalb der ganzen Liste.... bis der beste herausgepickt ist.
Grundlegend zwei Sachen die ich aktuell noch irgendwie drin haben bzw. b) auflösen will:
a) Die Sortierung nach Gewicht statt nach den Kriterien zur Auswahl, hier war der Gedanke immer dort in die Liste zu springen bei einer Iteration, wo wirklich nur noch Gegenstände zu finden sind, die sich definitiv auch noch einpacken lassen
b) Durch die Sortierung nach Gewicht erstelle ich eine verkettete Liste zum nächstkleineren Nachbarn (absteigend), das heißt ich kann nicht mehr direkt über "Indexe" und "halbieren" schnell ermitteln - sondern ich muß alle Elemente einzeln, in der Reihe durchgehen, hier wäre es gut die Liste zu kopieren, auch wenn dadurch der Speicherverbrauch eventuell "fast" verdoppelt wird, wobei ich nur zwei drei Werte und den Index/Adresse brauche an dem das Elternobjekt liegt
c) das Kriterium optimieren?
@theSplit: Ich glaube da passt was mit den Daten nicht.
Ich habe 1000 Gegenstände, diese wiegen zwischen 1 und 1100kg. In den Rucksack passen 1000kg rein und die Werte der Gegenstände liegen ebenfalls zwischen 1 und 100.
Du hast was mit 10.000 gemacht (?)
---
Ich lasse gleich einmal ein Beispielset für 10.000 erzeugen und gucke mal, ob ich das hier posten kann.
---
Randdaten:
10.000 Gegenstände
10.000 Gesamtkapazität des Rucksacks
1-11.000 Gewicht pro Gegenstand
1-10.000 Maximalwert pro Gegenstand
Algorithmus: Something_like_Bruteforce_with_some_optimations
@Roin: Ah... mein Fehler, das hab ich heute morgen nicht abgeändert bzw. berücksichtigt, hatte die Werte aus der Datei einlesen lassen und dabei die Rucksgröße nicht angepasst
Ich editiere hier in ein paar Stunden die korrekte Ausagbe rein....
Ich wollte das Ergebnis nur posten, damit man einen Vergleichsbetrag hat auf was die Lösungen kommen, aber das kann ja dann auch nicht hinkommen.
Update: So sollte es passen:
Total value / weight: 2798 Euro / 998 kg
Ist aber wohl der gleiche Wert wenn mich nicht alles täuscht
Update2: Ich habe jetzt den Grund gefunden warum mein Algorithmus so langsam gewesen ist... durch das Sortieren, ich hätte es mir auch sparen können.
Folgendes Resultat mit der 50.000 Gegenstände Datei von jamestop:
[src=text]---- Packed stats ----
Capacity of backpack: 10000 kg
Total value / weight: 287384 Euro / 9999 kg
------- Finished packaging algorithm in 108.836000 milliseconds... -------
real 0m0,130s
user 0m0,128s
sys 0m0,000s[/src]
Die Zeit für die Konsolenausgabe, Startup und anderes habe ich für die Zeit beim Algorithmus rausgerechnet, so liege ich jetzt bei etwas zwischen 105 und 130 Millisekunden.
