Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » * Das Waukerl Eusebius packt den Rucksack für die Bergwanderung
Thema eröffnet 2021-03-31 12:20 von gonz
Druckversion
Druckversion
Antworten
Antworten
Seite 3   [1 2 3 4]   4 Seiten
Autor
Kein bestimmter Bereich * Das Waukerl Eusebius packt den Rucksack für die Bergwanderung
haegar90
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.03.2019
Mitteilungen: 659
Wohnort: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.80, eingetragen 2021-04-16


Hallo gonz, da war ein Tippfehler 😃, ist nun korrigiert und die Sachen sind noch im Sack. EDIT: Muss korrigieren... leider Doppelte 🙄😴


Somit nach Korrektur: g: 20080        ml:28314  P:8276 (Tabelle in #78)


-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2965
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.81, eingetragen 2021-04-16


19.918            28.353            8.212  
 methode wie gehabt als summe von zwei rängen

[Die Antwort wurde nach Beitrag No.77 begonnen.]

 20.060            28.383            8.223  
excel händisch nachoptimiert

 20.099            28.343            8.254  


 20.094            28.390            8.290  
dichter komm ich nicht an haegar, oh möglcherweise hab ich ihn nach seiner korrektur doch überboten?




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 975
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.82, eingetragen 2021-04-16


🤗🤗🤗
haribo und haegar90, Ihr seid meine Helden!

"Händisch Excel ca. halbe Stunde"
Genau so [!!!] mach ich's auch. Weil's Spaß macht!

Seid Ihr bitte so lieb und führt irgendwie ein... Log...
über Euere verwendeten Formeln zur "Rangermittlung".
Auch über die verworfenen!? Dann können wir uns darüber
austauschen. Sobald auch ich Werte am Start habe. 😉


-----------------

ADMIRATIONIS  SUI  SATISFACTIONIS  SACRA  SITIS




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haegar90
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.03.2019
Mitteilungen: 659
Wohnort: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.83, eingetragen 2021-04-16


2021-04-16 14:49 - haribo in Beitrag No. 81 schreibt:
 ...

 20.094            28.390            8.290  
dichter komm ich nicht an haegar, oh möglcherweise hab ich ihn nach seiner korrektur doch überboten?

😂👍 ...sehr gut !!

Dann warten wir mal auf die Ergebnisse von cramilu 😃
...solange noch Zeit ist und der Kindernachmittag noch nicht
durch das Vorliegen wirklich optimaler Lösungen beendet wird.



-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 975
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.84, eingetragen 2021-04-16


"[...] ...solange noch Zeit ist und der Kindernachmittag noch nicht
durch das Vorliegen wirklich optimaler Lösungen beendet wird."

Köstlich formuliert!
Indes... wenn ich die Wahl habe zwischen "Kindernachmittag oder...?",
wähle ich meistens "Kindernachmittag!"
Ich suche noch meine jüngste "Verhältnispotenz"-Formel
von der letzten Liste, die ich in irgendeiner EXCEL-Instanz
verbummelt habe... Hilfe: Impotenzbefürchtungen...


-----------------

ADMIRATIONIS  SUI  SATISFACTIONIS  SACRA  SITIS




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2965
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.85, eingetragen 2021-04-16


(gewicht+0.6*volumen)/wert  aufsteigend sortiert,
plus minota... recht einfach also



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 975
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.86, eingetragen 2021-04-16


Ok... ich bin aktuell noch bei 8.211 Punkten[ct]...
... OHNE jegliches manuelles Nachklauben,
sondern allein durch Sortierung nach folgender "Scoring"-Formel:
\(val_{item}^r\:\cdot\:\left(\frac{val_{item}}{m_{item[g]}}\right)^{q_2}\:\cdot\:\left(\frac{val_{item}}{V_{item[ml]}}\right)^{q_1}\)   und hernach absteigend sortiert
\(r\,\in\,[\frac{1}{2};1]\)   ;   \(r=\Phi-1\) 😂 war... hoijoijoi...
\(\rho_{Packmenge}\,=\,\frac{m_{Packgrenze[g]}}{V_{Packgrenze[ml]}}\)   ;   \(\rho_{Packmenge}^x\,=\,\frac{q_1}{q_2}\:\land\:q_1+q_2=2\)   ;   \(x\,\in\,[0;3]\) ...
schon  \(x=0\:\Rightarrow\:q_1=q_2=1\)  war der "Bringer"...
Der 183. und letzte Gegenstand, bevor die Packgrenzen überschritten werden,
ist dann der "Wolkenfeger". Bis dahin 20.095 Gramm und 28.391 Milliliter.

EDIT
Angaben zu  \(x\)  korrigiert!

EDIT EDIT
Das zweitbeste, aber deutlich schlechtere "Scoring" habe ich
mit meinem allerältesten "Formelhüftschuss" erhalten:
\(\frac{val_{item}^2\:\cdot\:10.000}{m_{item[g]}\:\cdot\:V_{item[ml]}\:\cdot\:(m_{item[g]}+V_{item[ml]})}\)   und hernach absteigend sortiert
Ich bin gerade am Probieren, ob ich durch "milde" Erhöhung meines \(x\)
und entsprechende Anpassung von \(r\) noch besser "erstlanden" kann...



-----------------

ADMIRATIONIS  SUI  SATISFACTIONIS  SACRA  SITIS




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2965
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.87, eingetragen 2021-04-16


20.099            28.397            8.290  

gleiche punktzahl aber etwas näher an die grenze gepackt (also eigentlich ein nachteil für waukerl, aber er hat ein objekt mehr zur austeilung dabei)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 975
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.88, eingetragen 2021-04-16


haribo, Deine Formel ist stark!
Die habe ich mal zuerst beäugt, weil sie einfacher ist als meine.
Wenn Du Deinem "Wert" im Nenner eine Potenz von 1,05 oder 1,06
mitgibst, verbessert sich die "Erstlandung" VOR Nachklauben
jeweils auf 8.287 ; und dann noch'n paar...!?


-----------------

ADMIRATIONIS  SUI  SATISFACTIONIS  SACRA  SITIS




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2965
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.89, eingetragen 2021-04-16


tya, damit nimmst du mantaf(56) anstelle von katzen(23) + minota(36) macht minus 3 punkte
für alles andere ändert sich nur geringfügig die reihenfolge...

schätze aber andere tauschereien an der pack-grenze könnten irgendwie noch paar punkte bringen können

also meine obige sortierung hat 189 objekte eingepackt

dann nur die umliegenden evtl 40 objekte, also z.B. position 170 bis 210 durchspielen... das könnte evtl. etwas verbessern

das problem reduzierte sich damit prakmatisch auf folgendes kleineres:


bei max gewicht 2706 g; max volumen 4065 ml; >766 punkte erreichen

diese punkte werden hier mit lfnr. 189, minota erreicht

lfnr.        bez        gewicht        volumen        wert
170        Lenden         93        212        34
171        Latern         56        317        38
172        Quenge         91         66        20
173        Kosewo        137        350        53
174        Harpyi        202        124        42
175        Zysten        135        159        35
176        Scheus         83         60        18
177        Post-F        161        416        62
178        Rakete        108        430        55
179        Luminr        134        155        34
180        Pöbelk        121         55        23
181        Läster        206        104        40
182        Markow        215        235        53
183        Katzen         35        200        23
184        Wohlfü         91        165        28
185        Pascal        121        263        41
186        Boole-        217        161        46
187        Unhold        213         68        37
188        Lunger        145        315        48
189        Minota        136        200        36
190        Mantaf        159        387        56
191        Kraken        199        269        51
192        Chacha        164        138        35
193        Fistel        170        156        37
194        BIGPAC        181        365        55
195        Trapez          5        447        38
196        Hagelz        132        123        29
197        Lauerk        193        276        49
198        Blunns        139        139        31
199        Kladde         62        144        21
200        Pfaffe        175        313        49
201        Wolken        289        254        59
202        Dsibbf        161         94        30
203        Hexens        164        309        47
204        Sernfk         78        237        30
205        Tanzpo         35        207        22
206        Dollhe        182        225        42
207        Balrog        232         64        36
208        Klacke        193        209        42
209        Judodo        121        107        25
210        Coolto        200         54        31


evtl kommen noch wenige weitere kleine objekte zum restfüllen in frage






Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 975
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.90, eingetragen 2021-04-16


"[..] schätze aber andere tauschereien an der pack-grenze
könnten irgendwie noch paar punkte bringen [...]"

Genau darauf wollte ich doch hinaus!
"Wert" im Nenner mit Potenz "1" ergibt sortiert 8.254 OHNE Nachklauben.
Mit Potenz "1,05" oder "1,06" sind's schon 8.287, und das Nachklauben
könnte dann ergiebiger sein!


-----------------

ADMIRATIONIS  SUI  SATISFACTIONIS  SACRA  SITIS




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2965
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.91, eingetragen 2021-04-16


möglich schon, aber in diesem falle scheint es nicht geschickter zu werden

ich hab #89 nochmal erweitert...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 975
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.92, eingetragen 2021-04-16


Heut' Nacht ist hier bei uns Ausgangssperre.
Da hab' ich viel Zeit zum "Nachklauben"... 😉

EDIT

"Die Herrschaften, die auf Kartoffeln mit Speck gesetzt hatten,
zur Kasse bitte..."


haribo, besser als 8.290 krieg ich's auch nicht hin.
Allerdings hab' ich die über eine eigene Scoring-Formel geschafft.
Mein Bestwert dürfte seinen Begleitparametern 20.094 Gramm sowie
28.390 Millilitern nach deiner ersten Variante entsprechen.
Als "Ranglistenfunktion" habe ich meinen Ansatz der "durchschnittlichen
Heuer" herangezogen - er entspricht im wesentlichen Deiner Berechnung...
... wenn man sich denn nicht fehlerhaft selbst bescheißt und bei der
Feldformel die Kapazitätszahlen vertauscht. 🙄
\(\frac{{val_{item}}^p}{\frac{m_{item}[g]}{Packgrenze[g]}\:+\:\frac{V_{item}[ml]}{Packgrenze[ml]}}\)   und hernach absteigend sortiert
\(p\,\in\,[\frac{1}{2};3]\)   ;   \(p\,=\,1,25\)   war "zielführend"
"Rang" 183 nimmt nach Sortierung der "Luminrubin" ein - bei immerhin
schon 8.257 Punkten mit 20.086 Gramm und 28.264 Millilitern.
Danach war freilich mein "Gestochere" wohl aufwändiger als das Deine!
Rangmäßig rückwärts beäugt hatten mir "BIGPACK", "Wolkenfeger",
"Krakenkruge" und "Mantafuchsschwanz" zu hohe Packmaße, und ich habe
sie jeweils durch Pärchen ersetzt. Am Ende habe ich die "Nachklaubliste"
nach "Deinen" Rangwerten umsortiert, und schwupps...
mutmaßlich identisch mit der Deinen. Dann mochte ich nicht mehr. 😉

"Unterwegs" auf \(8.285\), \(8.286\) oder \(8.287\) zu kommen, gelingt in mehreren
verschiedenen Konstellationen. Darüber mir bloß in einer...

Punktsieger des "Kindernachmittags" damit:   haribo 🤗

haegar90, ich hoffe, Du bist da einverstanden!?
Deine EXCEL-Struktur sieht übrigens der meinen verblüffend ähnlich.
Zwei kranke Hirne, ein Gedanke! 😄

Und jeee-hetzt [am T-Shirt-Saum herumzupf] möcht' ich seh'n,
was die "Großen" so zustande bringen... tactac? AnnaKath?
Ohne irgend Jemandem sonst entsprechende "Größe" abzusprechen!

Meinen ausdrücklichen herzlichen Dank an gonz für diesen "Brocken"
von einer Instanz, samt ordentlich tückischer Verteilungen!
Den "Unhold" bitte "abhalten" anstatt "umholzen" - mein Versäumnis! 😉

Für ein allgemein problementschärftes Parsing der ASCII-Liste
würde ich als Zeilenstruktur vorschlagen:

[Packkandidat mit Abschluss-LEERZEICHEN statt -Punkten]#ct# mg# ml
--------------------------------------------------------------
Hydrahauchzerstäuber [auf feste Zeichenlänge aufgefüllt]#36# 37#102
Zystenzyklotron [auf feste Zeichenlänge aufgefüllt]#35#135#159
...

Also feste Spaltenbreiten und eindeutiges Spaltentrennzeichen.


-----------------

ADMIRATIONIS  SUI  SATISFACTIONIS  SACRA  SITIS




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
AnnaKath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.12.2006
Mitteilungen: 3525
Wohnort: hier und dort (s. Beruf)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.93, eingetragen 2021-04-17


Huhu cramilu,

2021-04-16 18:41 - cramilu in Beitrag No. 86 schreibt:
\(val_{item}^r\:\cdot\:\left(\frac{val_{item}}{m_{item[g]}}\right)^{q_2}\:\cdot\:\left(\frac{val_{item}}{V_{item[ml]}}\right)^{q_1}\)

\(\frac{val_{item}^2\:\cdot\:10.000}{m_{item[g]}\:\cdot\:V_{item[ml]}\:\cdot\:(m_{item[g]}+V_{item[ml]})}\)

In beiden Score-Funktionen geht der Wert der Gegenstände superlinear ein (in der zweiten sogar exakt quadratisch). Das kann eigentlich nicht funktionieren: Betrachte die drei Gegenstände A(1,1,5), B(1,1,5) und C(2,2,10). Offenbar ist es gleich, ob man A und B oder C in den Rucksack packt, aber Dein Scoring bevorzugt Gegenstand C deutlich. Nun stell Dir statt C den Gegenstand C'(2,2,10-$\epsilon$) vor...

lg, AK



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 975
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.94, eingetragen 2021-04-17


So... zunächst:
Kay_S, nach nochmaliger Durchsicht aller bisherigen Beiträge
im Hinblick auf "Scoring"-Formeln habe ich verdutzt entdeckt,
dass Du in #48 so ziemlich genau das genannt hattest, was ich selber
unabhängig davon als "durchschnittliche Heuer" zusammengebastelt
hatte - bis auf den "Landungsassistenz"-Exponenten für den Punktewert.
Kein Formelklau beabsichtigt! 😎

AnnaKath, an Deiner Ausführung gibt es winziges zu bekritteln!
Scherzhaft könnte ich entgegnen, dass es für Eusebius freilich
vorteilhaft ist, C(2,2,10) einzupacken, denn dann braucht er bloß
einmal auf die wankerlige Regalleiter zu klettern.
Ob es sich weiters dann um einen Gegenstand C'(2,2,10-\(\epsilon\)) handelt,
oder gar um C''(2,2,10-\(\mu\)) könnte zu Katheterstreitigkeiten führen!
In die erstere Score-Funktion ging bei mir der Gegenstandswert
mit  \(r=\Phi-1\)  keineswegs super- sondern sublinear ein!
Aber du hast Recht: Selbst Ultra- oder Infralinearität wären denkbar.
Ich hatte darüber natürlich schon selber gebrütet. So abwegig es jedoch
algebraisch scheinen mag, so deutlich ist es praktisch vorteilhaft! 😉


-----------------

ADMIRATIONIS  SUI  SATISFACTIONIS  SACRA  SITIS




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2965
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.95, eingetragen 2021-04-17


ich hab auch nochmal an der packgrenze herumexperimentiert, und kann es nicht verbessern, aber auch nicht abschliessend behaupten das optimum gefunden zu haben

unbeweisbar für mich

es wäre nett wenn mal jemand die 40 positionen aus #89 durchspielen könnte

haribo



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
LernFee
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2021
Mitteilungen: 19
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.96, eingetragen 2021-04-18


@Haribo,

#89: das gehe ich gerne mal an. Ob es heute schon was wird hängt davon ab, was sonst so zu tun ist...

@all als kleiner erster Beitrag, der Suchraum wird durch diese Vorsortierung um ca. 10% verkleinert, ohne dass es Rechenzeit aus dem NP Koningent kostet:

Minimalista 1.0 by Lea
 
Motzmotte geht nicht mit, dom. von ges. G= 40441  V= 43028
minigonz geht nicht mit, dom. von ges. G= 22072  V= 25879
Zerberuszähmer geht nicht mit, dom. von ges. G= 24862  V= 23844
Mammutfellmantel geht nicht mit, dom. von ges. G= 23462  V= 18139
PengPinguin geht nicht mit, dom. von ges. G= 30378  V= 35604
Schwofschwan geht nicht mit, dom. von ges. G= 21381  V= 43539
Fehlerteufel geht nicht mit, dom. von ges. G= 32264  V= 27908
Erinnyenentfessler geht nicht mit, dom. von ges. G= 24666  V= 20285
Schneckenschnatz geht nicht mit, dom. von ges. G= 21565  V= 21378
Gottfridelle geht nicht mit, dom. von ges. G= 20644  V= 21156
Badesalzbeutel geht nicht mit, dom. von ges. G= 27926  V= 48768
Bahkauvtatze geht nicht mit, dom. von ges. G= 25269  V= 48833
Phlegmafliege geht nicht mit, dom. von ges. G= 15139  V= 31925
Faselhase geht nicht mit, dom. von ges. G= 35512  V= 53212
Saltofloh geht nicht mit, dom. von ges. G= 34957  V= 31185
Griesgramkitzler geht nicht mit, dom. von ges. G= 22140  V= 35418
Wahrsagerwaran geht nicht mit, dom. von ges. G= 14404  V= 34944
Kasperlmütze geht nicht mit, dom. von ges. G= 39702  V= 61467
Schlemmerschlamm geht nicht mit, dom. von ges. G= 18798  V= 28556
Magmaschleuder geht nicht mit, dom. von ges. G= 14264  V= 28489
Allgassenhansdampf geht nicht mit, dom. von ges. G= 39360  V= 70855
Prophetenpapagei geht nicht mit, dom. von ges. G= 30686  V= 46565
Dschinngin geht nicht mit, dom. von ges. G= 18218  V= 38679
Schrödinger-Maus geht nicht mit, dom. von ges. G= 14172  V= 31822
Taekwondotarantel geht nicht mit, dom. von ges. G= 18704  V= 43664
Nixe geht nicht mit, dom. von ges. G= 23397  V= 32069
Allzweckpott geht nicht mit, dom. von ges. G= 38435  V= 66589
Mumpitzmousse geht nicht mit, dom. von ges. G= 45472  V= 47977
Lustrogologium geht nicht mit, dom. von ges. G= 16514  V= 31849
Kräuterkrambambuli geht nicht mit, dom. von ges. G= 20658  V= 27940
Saurierknochenmehl geht nicht mit, dom. von ges. G= 26576  V= 24655
Goblingabel geht nicht mit, dom. von ges. G= 26464  V= 19168
Klein Stowasser geht nicht mit, dom. von ges. G= 21144  V= 22949
Donnergurgler geht nicht mit, dom. von ges. G= 28452  V= 34880
Noether-Harke geht nicht mit, dom. von ges. G= 13980  V= 34271
Gilbmilbe geht nicht mit, dom. von ges. G= 14218  V= 30566
Quietscheentchen geht nicht mit, dom. von ges. G= 22947  V= 17968
Mammaladamala geht nicht mit, dom. von ges. G= 37449  V= 65565
Duplolutschium geht nicht mit, dom. von ges. G= 39845  V= 43077
Stirnbandana geht nicht mit, dom. von ges. G= 35077  V= 29935
Wanderkarte geht nicht mit, dom. von ges. G= 21077  V= 18923
Mops Vicco geht nicht mit, dom. von ges. G= 19825  V= 40290
Schimpfpimpf geht nicht mit, dom. von ges. G= 16933  V= 37311
Flunkerflunder geht nicht mit, dom. von ges. G= 17346  V= 28861
Ambraamphore geht nicht mit, dom. von ges. G= 16173  V= 30718
Insgesamt 45 Dinge identifiziert, die daheim bleiben
 
Eisenpfännchen geht mit, nicht dom. verbleibt G= 7416  V= 18379
Hoppelhelfer geht mit, nicht dom. verbleibt G= 9382  V= 22046
Schatzschatüllchen geht mit, nicht dom. verbleibt G= 17326  V= 25759
Yogakissen geht mit, nicht dom. verbleibt G= 16395  V= 25421
Siebenmeilenstiefel geht mit, nicht dom. verbleibt G= 11875  V= 20082
Bronzebottich geht mit, nicht dom. verbleibt G= 10689  V= 15215
MEGAPACK geht mit, nicht dom. verbleibt G= 15395  V= 24184
Insgesamt 7 Dinge identifiziert, die mit müssen.
 


Have fun!

PS.: Die modifizierte Liste kann im Wunschformat beim Büro der Obertugendboldine bezogen werden - Anfrage per PN an die dortige Zettelzofe.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2965
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.97, eingetragen 2021-04-18


ja mach mal irgendwann, dass wäre schön

deine sieben sicher mitgenommen objekte sind auch bei mir unter den ersten acht...

also insofern ist meine ein- und ausschluss-liste in #89 einfach erheblich länger

169 fest mitgenommene und 293 ausgeschlossenen belassen dort eben die 40 vakanten

haribo



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 975
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.98, eingetragen 2021-04-18


LernFee, MACHEN ist stark! 😉
Ich hab' mir nochmal 'ne Stunde erfolglos die Griffel
wundgefummelt, um doch noch über die 8.290-Latte...


-----------------

ADMIRATIONIS  SUI  SATISFACTIONIS  SACRA  SITIS




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
LernFee
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2021
Mitteilungen: 19
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.99, eingetragen 2021-04-19


Zwischenstand:

Keine Treffer beim Durchgehen aller möglichen Vertauschungen innerhalb der plus/minus 20 an der "Packgrenze" nach den Daten von Haribo.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2965
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.100, eingetragen 2021-04-20


ungefähr welche vertauschungsarten hast du probiert?
haribo



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
LernFee
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2021
Mitteilungen: 19
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.101, eingetragen 2021-04-20


Hi Haribo,

ich habe gem. deiner Liste die Items bis einschließlich 169 fest genommen, und dann alle möglichen Kombinationen der Items 170-209 dazugenommen. Das dauert auf einem Kern 20 Minuten (sicher deutlich optimierbar). Ich kann jetzt folgendes machen ("brute force" verliert):

- die Breite soweit erhöhen, wie es eine verbesserte Version auf X Kernen z.B über Nacht eben schafft (oder dann ad infinitum weiterrechnen immer mehr in die Breite), oder

- Für jede geprüfte Kombination, die nicht allzu schlecht ist, noch schauen, ob sie aus einer Liste "besonders kleiner/leichter Objekte" geringfügig verbessert werden kann.

Natürlich gibt es da noch viele weitere Ideen - Hinweise gerne angenommen.

Soweit zum Stand der Dinge -
Lea



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2965
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.102, eingetragen 2021-04-20


ok, du hast also in dem bereich alle (?) ca 40! varianten durchgetestet?

ich hatte gestern in zufälliger reihenfolge aus dem bereich dazugepackt, und kam bei ca.50T durchläufen nur einmal auf 8275... hätte also damit nicht so schnell ein gutes ergebnis gefunden, alles mit excel und optischer kontrolle, also eher langsam in zwo stunden

bereich nach oben ausweiten kann kaum was bringen, die sind einfach alle absolut besser, das erscheint mir sehr sicher da letztlich keine extremen gewichts oder volumen unterschiede existieren, man also immer nahe am limit packen kann

nach unten könnte man evtl erweitern oder eben unterhalb der grenze strikt nach wert sortieren und genau die davon durchspielen die wertiger sind als die differenz zu summe wert 8290, naja warscheinlich ist es mit deinem rechner schneller dort jeweils alle einzeln dazuzuaddieren

also davon ausgehend dass nur noch ein einziges dazukommen würde

ausgeben würde ich mal alle sets die besser als evtl. 8280(?) sind... und auf diese liste nochmal einen händischen blick werfen (grenze könnte auch ggfls noch näher an 8290 liegen...)

fals wir wirklich nichts besseres finden dann spricht das für meine score idee, also bei [ score = (g + 0,6*v) / w ] den faktor 0.6 derartig anzupassen dass beide limiten (gewicht+volumen) beim gleichen objekt erreicht werden, was ich auch nur durchgespielt hatte

aber bei den alten sets immer nur nahe ans optimum herankam... es nie exakt fand,
hier scheint es halt zufällig zu passen

haribo



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6855
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.103, eingetragen 2021-04-20


Ich denke, die 8290 ist optimal.

Was habe ich gemacht? Ich verwende dynamische Optimierung über einem zweidimensionalen Feld Masse/Volumen.
Das hat den Vorteil, dass die _Zahl der Gegenstände_ nicht exponentiell in den Aufwand eingeht, sondern nur linear. Dafür hängt der Aufwand linear von den Kapazitäten des Rucksacks ab(*) und funktioniert nur, wenn alle Massen und Volumina ganzzahlig sind.
(*) Dieses Laufzeit-Verhalten nennt man "Pseudopolynomial", weil die Laufzeit nicht polynomial von der Eingabelänge abhängt, sondern von den absoluten Werten..

Mit den Werten 20100g und 28400ml stoße ich aber langsam an meine Grenzen, was den Arbeitsspeicher anbelangt. Das kann man etwas abmildern, indem man die Rolle von Volumen und Wert vertauscht. Man sucht also bei gegebener Masse und gegebenem Wert eine Lösung mit möglichst kleinem Volumen. Am Ende schaut man dann nach, für welche Werte man eine Lösung findet, die die Volumenschranke einhällt.

[Die Antwort wurde nach Beitrag No.100 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 975
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.104, eingetragen 2021-04-20


Ja... gonz' Werte sind diesmal "ordentlich fies" gewählt!.
Ich hatte mir inzwischen Gedanken zu einem "Pruning"-Ansatz gemacht...
Das "von Hand" per EXCEL zu modellieren ufert jedoch schnell aus.

Man bestimme zunächst für die Gesamtanforderung und für jeden
von drei "Bestscores" die erforderlichen Beiparameter, um dann,
bevor der erste zusätzliche Gegenstand die Packgrenzen sprengt,
möglichst viele Punkte mit der Art des jeweiligen "Scores"
erreicht zu haben. Die Schnittmenge der jeweils mitgenommenen
Gegenstände wird notiert.
Dann wiederholt man selbiges für die halbierten Packgrenzen!
Die Gesamtschnittmenge wird isoliert und schon einmal FIX eingepackt.
Ihre Packmasse und Packvolumen zieht man von der Gesamtkapazität ab
und erhält ein vermindertes "Restproblem".
Dort hat sich nun das Verhältnis von verbleibender Packmasse
und verbleibendem Packvolumen womöglich geändert...
Man wiederhole obige Schritte für das "Restproblem"...
Hat man das zwei- oder dreimal gemacht, ist man wohl deutlich
näher an den Bereich herangekommen, der als "Restmüllproblem"
via "close to brute force" objektiv zu schaffen ist[?].
Selbstredend kann man dazu begleitend auch stets gemeinsame
"Worstscorer" rausschmeißen...

Den Zeitaufwand, das algorithmisch umzusetzen, kann ich jedoch
noch nicht abschätzen. Und leider fehlen mir für solches derzeit
auch Zeit wie Muße.
Gespannt warte ich schon auf das Ende des "Kindernachmittags",
sprich: "global" verlässliche Resultate von tactac, AnnaKath
oder anderen ;)

p.s.
Das mit der "Ultra-", "Super-", "Sub-" oder "Infralinearität"
meiner Exponenten verblüfft mich natürlich selber!
Die   \(\phi-1\)   etwa sind auch mir erstaunlich weit weg von der  \(1\) .


-----------------

ADMIRATIONIS  SUI  SATISFACTIONIS  SACRA  SITIS




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6855
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.105, eingetragen 2021-04-20


2021-04-16 14:49 - haribo in Beitrag No. 81 schreibt:
...
 20.094            28.390            8.290  
Yep. Wenn ich mich nicht vertan habe, ist das optimal.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2965
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.106, eingetragen 2021-04-20


2021-04-20 20:40 - Kitaktus in Beitrag No. 105 schreibt:
2021-04-16 14:49 - haribo in Beitrag No. 81 schreibt:
...
 20.094            28.390            8.290  
Yep. Wenn ich mich nicht vertan habe, ist das optimal.

danke schön fürs überprüfen
haribo



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 975
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.107, eingetragen 2021-04-20


Danke, Kitaktus!
Aber hat Dein Algorithmus die andere 8.290-Lösung
von haribo aus #87 auch gefunden?


-----------------

ADMIRATIONIS  SUI  SATISFACTIONIS  SACRA  SITIS




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6855
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.108, eingetragen 2021-04-20


Interessante Frage.
Bei einer "normalen" Umsetzung würde Dynamische Optimierung zu jeder Kombination aus Masse und Volumen _eine_ Lösung mit maximalem Wert ermitteln. Da die andere Lösung tatsächlich andere Massen und Volumen hat, würde man sie also finden.
Ich überlege gerade, wie viel zusätzlicher Aufwand nötig wäre, um _alle_ Lösungen zu finden, die zum gleichen Optimalwert führen (also auch die, bei denen Masse _und_ Volumen übereinstimmen). Wenn man den Speicher um den Faktor N (N=Anzahl der Gegenstände) vergrößern kann, dann wäre der Zusatz-Aufwand linear mit der Anzahl der Lösungen und mit der Anzahl der möglichen Gegenstände.
Ohne den Extraspeicher könnte der Aufwand explodieren, da müsste ich mal drüber nachdenken.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
LernFee
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2021
Mitteilungen: 19
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.109, eingetragen 2021-04-21


Danke für die Anregung, Kitaktus! Wieder ein "Puzzlestein" für die Lernfee.

Ist damit alles erledigt - oder "spielen" wir weiter?




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2965
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.110, eingetragen 2021-04-21


kitaktus, was ist denn das dynamische an der dynamischen methode? was wird dabei wann dynamisch verändert beim suchen?

wenn wir einen schacht xyz hätten mit den grundmassen des rucksacks, also x=20100[g] und y=28400[v] und die 503 päckchen mit jeweils ihrem xyz,
packen das erste päckchen bei xyz 0/0/0 in die ecke und das nächste startet an der diagonalen ecke des ersten, dann suchen wir eine raumdiagonale päckchenreihe welche möglichst hoch sein soll, (ungefähr wie bei der idee "kisten aufeinander zu stapeln und hochklettern bis zum mond")

diese raumdiagonale erinnert übrigens an die kleinen quadrate bei einer binomischen formel... jedes päckchen blockiert einen sehr viel grösseren anteil des endschachtes als sein volumenanteil

man kann die gefundene lösung aus der einen richtung anschauen und hat ein  einwertiges packproblem, z.B. von vorne dann spielen die volumen keine rolle (volumen hätten also den faktor 0 und die gewichte hätten faktor 1) visa versa von der seite betrachtet spielte nur das volumen eine rolle und das gewicht wäre eliminiert...

jedenfals gibt es 3D betrachtet den lückenlosen einzelpäckchen-raum-diagonalen-polygonzug diagonal durch den schacht bis fast genau zur oberen ecke, und die frage des scores scheint zu sein aus welcher richtung man diesen polygonzug betrachtet

man kann ja die päckchen hinterher (oder eben aus jeder betrachtungsrichtung...) so sortieren dass dieser polygonzug steil anfängt und immer flacher wird... ungefähr dass war die idee zu meinem score... aber eben nicht genau, sonst hätte ich ((wurzel (g²+v²))/w) nehmen müssen... das führte aber zu nem schlechteren ergebniss

ich weiss nicht wiso mein score besser funktioniert, möglicherweise entscheide ich mit dem faktor 0,6 aus welcher richtung ich auf die einzel-päckchen-raumdiagonalen schaue? und reduziere damit das problem von einem mit zwei werten zu einem einwertigen? welches ja immer noch das packgrenzen-problem hat, und so gesehen sind die ausgewählten packmasse hier eben nicht sonderlich tricky gewesen weil ich ja schnell die lösung gefunden habe??? mit nur einem nachgesuchten restpäckchen, ohne komplexe tauschvarianten

offenbar war das set eben nicht wirklich tricky sondern nur viele päckchen, derart viele dass "alle varianten durchsuchen" niemand mehr leisten konnte

bei keinem der älteren packsets hatte ich mit meiner methode die beste packung gefunden,

wiso genau funktionierte es hier?

@cramilu, ehrlich ich wüsste auch nicht ob ich die zweite variante nochmal finden würde... schon gleich gar nicht ob es weitere lösungen mit 8290 gibt

@gonz, wie hast du die zufallszahlen generiert? (z.B. wiso gibt es dabei keine ganz kleinen in beiden werten...) was evtl. hattest du ausgeschlossen?

also ick bin noch nicht fertig damit
haribo



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3864
Wohnort: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.111, vom Themenstarter, eingetragen 2021-04-21


Hallo Haribo,

Zur Frage der Verteilung kurz folgendes:

Die Verteilung von Gewicht, Volumen und Wert sind unabhängig voneinander, ich habe jeweils Gamma-Verteilungen gewählt (die Parameter müsste ich nachschauen, ich wollte etwas "unsymmetrisches" haben), sie sind einfach am Ende des jeweiligen Wertebereichs abgeschnitten (also zB. 1..450 für das Volumen). Die Werte habe ich anschließend gerundet auf ganze Zahlen. Es kam mir ja nicht darauf an, was es genau ist, sondern nur, ungefähr das gewünschte "Bild" zu erreichen. Entsprechend habe ich mir am Ende ein Histogramm der jeweiligen Verteilungen angeguckt, bis ich halbwegs "zufrieden war".

Wenn es also keine "kleinen _und_ leichten" Dinge gibt, ist das dem Zufall geschuldet.

Wie gesagt, auf Wunsch genaueres.


-----------------
LEG XXI RAP LEGATUS



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6855
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.112, eingetragen 2021-04-21


Zum Einstieg hilft vielleicht diese Wiki-Seite hier. Das vorletzte Beispiel ist das Rucksackproblem.

Das Prinzip ist folgendes:
Es seien $M$ die zulässige Gesamtmasse, $V$ das zulässige Gesamtvolumen und $n$ die Anzahl der Gegenstände.
Betrachte ich den letzten Gegenstand $(m_n,v_n,w_n)$, so gibt es zwei Möglichkeiten: Entweder er ist in der optimalen Lösung enthalten, oder er ist eben nicht enthalten.
Würde ich wissen, welchen Gesamt-Wert man mit den ersten $n-1$ Gegenständen hinbekommt, wenn man
a) die Masse $M$ und das Volumen $V$ zur Verfügung hat, oder
b) die Masse $M-m_n$ und das Volumen $V-v_n$ zur Verfügung hat,
dann könnte man leicht beantworten, ob man den n-ten Gegenstand einpackt: Ist der Wert aus a) größer als der Wert aus b) plus $w_n$, dann bleibt es draußen, ansonsten kommt es mit rein.

Die Frage ist: Woher bekomme ich diese Information a) und b)?
Die Lösung ist sehr brutal: Ich ermittle einfach für _alle_ Kombinationen aus Massen $M'\leq M$ und Volumen $V'\leq V$ den maximal erreichbaren Wert unter Verwendung der Gegenstände 1 bis n-1.
Jede dieser Aufgaben ist wiederum leicht, wenn ich die maximal erreichbaren Werte unter Verwendung der Gegenstände 1 bis n-2 kennen usw.
Das ganze drösele ich auf, bis ich bei einem (bzw. keinem) Gegenstand bin.

Algorithmisch gehe ich dann genau andersrum vor.
Ich initialisiere eine Matrix mit den Zeilen 0 bis M und den Spalten 0 bis V. Schreibe überall $-\infty$ rein, außer bei (0,0), dort schreibe ich eine 0 rein.
Das bedeutet: Mit den ersten null Gegenständen gibt es keine Kombination mit Gesamtmasse m und Gesamtvolumen v (daher der Wert $-\infty$), außer für m=v=0.
Danach gehe ich, bei $k=1$ beginnend für jeden Gegenstand $k$ die Matrix einmal durch und berechne, ob sich bessere Kombinationen ergeben, wenn man $k$ verwendet.
Der Gesamtaufwand dafür ist O(nMV). Das hat den Vorteil, dass n hier nicht exponentiell eingeht, sondern nur linear. Dafür gehen M und V linear ein und nicht nur logarithmisch wie bei den meisten anderen hier genannten Ansätzen.
Würden die Massen nicht in Gramm, sondern in Milligramm angegeben (und wären weiterhin ganzzahlig), so vergrößert sich bei mir der Aufwand um den Faktor 1000, mal abgesehen davon, dass das alles dann nicht mehr in den Arbeitsspeicher passt.

Man könnte es vielleicht so formulieren: Der Aufwand verringert sich dadurch drastisch, dass man nicht mehr alle $2^k$ Kombinationen aus $k$ Gegenständen betrachtet, sondern nur die, die zu einer unterschiedlichen Kombination aus Anzahl der betrachteten Pakete, Masse und Volumen führen. Davon gibt es "nur" $k(M+1)(V+1)$ Stück. Bei den aktuellen Werten sind das $570888501 \cdot k$ Stück, ab $k=35$ lohnt sich das also.
Selbst wenn man durch Zusatzüberlegungen den Aufwand von $2^k$ auf $1.1^k$ runterschraubt (und das wäre sehr viel) gewinnt die dynamische Optimierung bei $k=271$ die Oberhand.

Der erste von mir verwendete Ansatz bestand im wesentlichen aus:
Matlab
Z=zeros(M+1,V+1);
for n=1:N
  Z(A(n,1)+1:M+1, A(n,2)+1:V+1)=max(Z(A(n,1)+1:M+1, A(n,2)+1:V+1), Z(1:M-A(n,1)+1, 1:V-A(n,2)+1)+A(n,3));
end
Dabei ist A eine Matrix, die je Zeile Masse, Volumen und Wert eines Gegenstands enthält. Diese komischen "+1" sind nötig, da Matlab bei der Nummerierung von Zeilen und Spalten bei 1 beginnt und nicht bei 0.
Um aus der fertig berechneten Matrix nicht nur den _Wert_ der optimalen Lösung, sondern eine optimale Lösung selbst abzulesen zu können, ist etwas mehr Code notwendig.

Bemerkung: Die heuristischen Verfahren, die hier vorgeschlagen wurden funktionieren so gut, weil die Gegenstände sich relativ stark in ihrem Wert bezogen auf die "verbrauchte" Masse und das "verbrauchte" Volumen unterscheiden. Wären diese Werte ähnlicher, dann wäre es auch mit "Scoring"-Verfahren schwieriger das Optimum zu finden (zum Trost wären dann auch die Wertunterschiede zwischen verschiedenen Lösungen geringer).

[Die Antwort wurde nach Beitrag No.110 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
AnnaKath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.12.2006
Mitteilungen: 3525
Wohnort: hier und dort (s. Beruf)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.113, eingetragen 2021-04-21


Huhu zusammen,

zunächst hatte ich ja durchaus das Bedürfnis, auch an den Algorithmen herumzubasteln; tatsächlich finden sich aber genug ernst zu nehmende Betrachtungen im Netz. Danach habe ich mich auf eine hübsche Implementierung beschränkt und bin nun ganz zufrieden.

Meine Algorithmen habe ich zunächst an den einschlägigen, "offiziellen" Quellen getestet und danach an etwa 10 000 zufälligen Samples vertieft.

Viele meiner ursprünglichen Ideen (insbesondere alle "geschickten" vollständigen Lösungen) habe ich verworfen und auch Kitaktus` dynamische Programmierung scheint mir bei grossen Rucksäcken (mit ggf. auch mehr als 2-dimensionalen Beschränkungen, auch natürlich mit steigender Item-Zahl, obwohl der Algorithmus hier doch recht wenig anfällig ist) schlicht nicht mehr in akzeptabler Zeit zu berechnen.

Letztlich habe ich mich für einen generischen Scoring-Algorithmus entschieden, der noch durch ein Branch-And-Bound und eine "Core-Search" ergänzt wird. Alle darüber hinausgehenden Algorithmen der Literatur (ins. alle Varianten parallel laufender Algorithmen unterschiedlichen Typs) erscheinen mir dann - trotz aller Effizienz - als zu aufwändig.

Dieser Algorithmus schätzt im aktuellen Beispielproblem etwa nach 8 ms eine "Initiallösung" mit 8285 Punkten und findet die Lösung aus #87 nach 21 ms.
Auch Probleme mit über 10k Items, Probleme mit sehr "ähnlichen" Items und sehr "ungleichmässigen" Rucksäcken löst er in wenigen Sekunden bis Minuten.

Wen die Details interessieren, der kann dies gerne erfragen. Ansonsten würde ich mich (um neutral zu bleiben) über ein wirklich grosses Problem von dritter Seite freuen...

lg, AK



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 975
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.114, eingetragen 2021-04-21


Acknowledged! Die "Kinderstunde" ist vorbei ;)


-----------------

ADMIRATIONIS  SUI  SATISFACTIONIS  SACRA  SITIS




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3864
Wohnort: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.115, vom Themenstarter, eingetragen 2021-04-22


Guten Morgen allerseits,

dann hake ich dies offiziell ab - was natürlich nicht heißt, dass nicht über Details weiter geredet werden könnte/sollte. Es hat mir Spaß gemacht, und ich habe etwas gelernt über das hinaus, was ich mit der Themenstellung im Sinn hatte. Das ist immer gut.

Alles Gute für die zweite Wochenhälfte,
Gerhard/Gonz


-----------------
LEG XXI RAP LEGATUS



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2965
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.116, eingetragen 2021-04-22


2021-04-21 13:30 - Kitaktus in Beitrag No. 112 schreibt:
Danach gehe ich, bei $k=1$ beginnend für jeden Gegenstand $k$ die Matrix einmal durch und berechne, ob sich bessere Kombinationen ergeben, wenn man $k$ verwendet.

versuche zu verstehen:

also bei k=1 wählst du vorerst den wertigsten alleine reinpassenden aus, dann bei k=2 die wertigste kombination aus zweien... usw bis du bei k=n letztlich prüfst ob der wertloseseste (?) immer noch dazu kommen kann und diese entscheidung ist dann die erste finale

danach den ganzen durchgang nochmal um für den zweitunwertigsten die entscheidung zu treffen

muss man in dem moment schon die anzahl der im besten fall mitgenommenen objekte kennen ? (oder annehmen)




wäre es nicht viel schneller erstmal beliebig vollpacken und dann n mal(oder so oft bis keine verbessereung mehr vorkommt) auch mit einer matrix alle gegen alle restlichen schauen welcher einzel tausch den besten zuwachs bringt...

und dann erst mit deiner methode alle nachprüfen, also genau genommen nicht exakt zu wissen ob bei n-1 schon ein absolutes optimum vorlag aber zu wissen es lag eine sehr gute packung vor... und trotzdem eine sagen wir dann also "empfehlung" für jedes objekt auszusprechen

na, ich muss das wohl mit wenigen objekten selber probieren, um das prinzip zu betrachten, evtl bin ich im gedanken des optimierenden tausches gefangen ohne seine grenzen zu erkennen
haribo



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6855
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.117, eingetragen 2021-04-22


@haribo: Es gibt sicher bessere/ausführlichere Darstellung von "Dynamischer Programmierung(*)"
Stell Dir vor, Du kennst alle optimalen Kombinationen, die nur die ersten k-1 Gegenstände verwenden und sollst daraus alle optimalen Kombinationen berechnen, die die ersten _k_ Gegenstände verwenden.
Dazu musst Du für jede Masse-Volumen-Kombination nur prüfen, ob es besser ist, den Gegenstand dazuzunehmen und den Rest mit einer optimalen Kombination der ersten k-1 Gegenstände zu befüllen, oder ob es besser ist, den k-ten Gegenstand nicht dazuzunehmen und direkt die optimale k-1-Lösung zu übernehmen.
Das Ganze machst Du für jede Masse-Volumen-Kombination (im Code werden alle diese Kombinationen mit einem Schlag berechnet) und dann iterativ für k=1,2,...,n.

Die Reihenfolge in der man die Gegenstände betrachtet, spielt keine Rolle. Nimmt man die "wertigen" Gegenstände zuerst, erreicht man vielleicht schneller die optimale Lösung.


(*) Aus historischen Gründen heißt das "Programmierung" und nicht "Optimierung".



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2965
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.118, eingetragen 2021-04-22


schon klar, das die reihenfolge egal ist,

aber, nur für mein verständniss, bei k=1 kommt doch immer der wertigste noch passende heraus? er hat ja eben als einzelner die meisten punkte...

warum also nicht vorsortieren, fals nicht perfekt dann eben ungefähr
und jeweils abbrechen wenns nur noch schlecheter wird, bei unperfekter sortierung eben einige positionen später...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6855
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.119, eingetragen 2021-04-22


Man ermittelt im ersten Schritt nicht alle Kombinationen aus (irgend-) _einem_ Gegenstand, sondern alle Kombinationen aus dem _ersten_ Gegenstand.
Im k-ten Schritt sind es entsprechend alle Kombinationen, die nur die _ersten_ k Gegenstände verwenden.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
-->> Fortsetzung auf der nächsten Seite -->>
Seite 3Gehe zur Seite: 1 | 2 | 3 | 4  
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]