Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Rucksackproblem mit Speicherplatz linear zur Gegenstandsanzahl
Druckversion
Druckversion
Autor
Universität/Hochschule J Rucksackproblem mit Speicherplatz linear zur Gegenstandsanzahl
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 140
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-05-05


Hallo,

Gegeben ist das Knapsack-Problem (de.wikipedia.org/wiki/Rucksackproblem) wobei in diesem Fall die Gewichte jedes Gegenstandes gleich seinem Wert sind.
Nun ist die Aufgabe, einen Algorithmus zu schreiben, der mit höchstens \(O(n)\) Speicherplatz auskommt, wobei \(n\) die Anzahl der Gegenstände ist.
Ich habe es eine ganze Weile mit top-down und bottom-up Ansätzen probiert aber kriege es nicht gelöst aber finde nicht die richtige rekursive Abhängigkeitsformel.
Über Hilfe würde ich mich sehr freuen!

EDIT: Ebenfalls keine gültige Lösung ist ein Brute-Force Ansatz, der alle möglichkeiten durchprobiert.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6938
Wohnort: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-05-05


Hallo dvdlly,

ich verstehe nicht ganz, wo das Problem ist. Man kann doch alle Möglichkeiten einfach durchprobieren. Das ist dann nicht ein Problem des Platzes sondern der Zeit.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 140
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2021-05-05


Hallo,

Ja da hast du natürlich Recht. Aber die Aufgabenstellung sieht eine zusätzliche zeitliche Einschränkung vor. Das habe ich vergessen zu erwähnen (danke). Also muss es ein Ansatz sein, der dynamische Programmierung verwendet.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6938
Wohnort: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2021-05-05


Wie lautet denn diese zeitliche Einschränkung? Schreib doch die Aufgabenstellung mal auf.



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: 6852
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2021-05-06


2021-05-05 20:42 - StrgAltEntf in Beitrag No. 3 schreibt:
Wie lautet denn diese zeitliche Einschränkung? Schreib doch die Aufgabenstellung mal auf.
Das wäre sehr hilfreich. Dynamische Programmierung kommt ja eben nicht mit einem Speicher aus, der nur von der _Anzahl_ der Gegenstände abhängt.

Hinweis: Auch mit der Einschränkung Wert=Gewicht ist das Rucksack-Problem NP-vollständig.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 140
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2021-05-06


Die Eingabe besteht aus einem einzigen Testfall.
Der Testfall besteht aus Zwei Zeilen. Die erste Zeile enthält Zwei natürliche Zahlen \(n\) und \(M\) wobei \(1 \leq n, M \leq 2 \cdot 10^5\) gilt. \(n\) beschreibt die Anzahl der Gegenstände im Rucksack und \(M\) die Kapazität. Die nächste Zeile enthält \(n\) natürliche Zahlen \(m_1,...,m_n\)wobei \(1 \leq m_i \leq 3\). Die \(m_i\) geben sowohl das Gewicht als auch den Wert der Gegenstände an.
Eine weitere Einschränkung ist, dass dem Algorithmus höchstens Eine Sekunde Laufzeit zur Verfügung steht, aufgrund der Größe der Eingabe ist es nicht möglich das Problem mit einem gewöhnlichen DP-Ansatz zu lösen, denn dieser bräuchte zu viel Speicherplatz.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2865
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2021-05-06


Das Problem kann durch dynamische Programmierung effizient und mit O(n) Speicherplatzbedarf gelöst werden, da nur maximal 3n verschiedene Gewichte auftreten können.

Man könnte also ein Array der Kapazität 3n erstellen und dieses dann in O(n^2) bei O(n) Speicherbedarf mit den Gegenständen füllen.

Es geht sogar noch effizienter, wenn man die Gegenstände in ihre 3 Klassen aufteilt und dann schaut, ob man eine passende Zerlegung M=x+2y+3z findet.
Dann hat man sogar O(n) Laufzeit UND Speicherbedarf.


Es handelt sich im beschriebenen Fall eher um das Wechselgeldproblem als um ein echtes Rucksackproblem.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 140
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2021-05-06


Danke für deine Antwort.
Die Frage ist vielleicht etwas dumm, aber wieso kommt man auf maximal \(3n\) verschiedene Gewichte? Es ist doch gegeben, dass es höchstens \(3\) verschiedene Gewichte gibt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2865
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2021-05-06


Die Aussage war richtig, die Begründung jedoch nicht.

Natürliche Summanden ergeben natürliche Summen.
Die maximal erreichbare Summe ist hier 3n, die minimale ist 0.
Es gibt also nur 3n+1 verschiedene Werte, die unabhängig von den konkreten Gewichten überhaupt angenommen werden können.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 140
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2021-05-06


Ah so meinst du das, okay danke!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly hat die Antworten auf ihre/seine Frage gesehen.
dvdlly hat selbst das Ok-Häkchen gesetzt.
dvdlly wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema]  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]