AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Rucksackproblem

Ein Thema von buff222 · begonnen am 19. Okt 2006 · letzter Beitrag vom 2. Nov 2006
Antwort Antwort
Benutzerbild von Gausi
Gausi

Registriert seit: 17. Jul 2005
900 Beiträge
 
Delphi 11 Alexandria
 
#1

Re: Rucksackproblem

  Alt 19. Okt 2006, 15:40
Zitat von Luckie:
Man könnte einfach einen BruteForce Algorithmus auf das Problem los lassen und alle Möglichkeiten durchprobieren. Wäre natürlich so ziemlich das uneleganteste was es gibt, dafür aber ziemlich sicher und robust.
Da das Rucksackproblem NP-vollständig ist, bleibt einem nicht wirklich was anderes übrig, wenn man die exakte Lösung haben will. (Ich gehe davon aus, dass bei "alle Möglichkeiten durchprobieren" schon gewisse Abbruchkriterein dabei sind, sodass nicht mehr dazu gepackt wird, wenn der Rucksack eh schon zu schwer ist.)

Man könnte zwar mit diversen Heuristiken rangehen, die evtl. eine Lösung finden, die (beweisbar) nur um einen gewissen Prozentsatz von der richtigen Lösung abweicht, aber das ist hier sicherlich nicht verlangt.
  Mit Zitat antworten Zitat
Antwort Antwort


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 02:15 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz