nicht angemeldet
Hallo
Versuchen wir es mit einem Widerspruchsbeweis.
Mit dem obigen Verfahren erhältst du als Ergebnis eine Reihe von "gepackten" a-Stangen mit steigendem Verschnitt. Es kann niemals passieren, dass eine a-Stange in einem späteren Schritt des Verfahrens besser gepackt wird, als eine andere a-Stange in einem frühren Schritt des Verfahrens, denn in diesem früheren Schritt standen alle b-Stangen zur Verfügung, die bei dem späteren Schritt genutzt wurden. Also ist die letzte a-Stange am schlechtesten verpackt und auf die konzentrieren wir uns.
Angenommen das Verfahren sei nicht optimal. Dann existiert eine andere Verteilung der b-Stangen, sodass du eine b-Stange (nennen wir sie b*) aus der _letzten_ gepackten a-Stange rausholen und in irgendeine andere a-Stange legen kannst. Diese b*-Stange muss die _einzige_ b-Stange in der letzten gepackten a-Stange sein, sonst würde sich der Gesamtverschnitt ja nicht ändern und die Lösung hätte sich durch die Umverlagerung nicht verbessert. Nur wenn die letzte a-Stange dadurch wirklich überflüsig wird, können wir den Verschnitt reduzieren.
Wir bringen also b* irgendwie in den anderen a-Stangen unter und schmeissen die letzte a-Stange weg. Daruch hat sich der Gesamtverschnitt in den restlichen a-Stangen reduziert. Dafür ist es notwendig, dass mindestens eine a-Stange (a*) jetzt besser gepackt ist, als vorher. Beim packen von a* stand b* allerdings zur Verfügung, also hätte der Rucksack Packer b* mit in a* reinpacken müssen. Ergo kann b* in keine andere a-Stange verlagert werden und das Verfahren hat eine optimale Lösung gefunden.
Sieht jemand einen Denkfehler?
Cruz