0 Daumen
55 Aufrufe

Frage: Wie finde ich eine Lösung für das Rucksack-Problem mit einem Orakel?

Moin Leute, die Aufgabe könnt ihr unten lesen.


Text erkannt:

Aufgabe 3 (Such- und Optimierungsvarianten)
(12 Punkte)
Betrachten Sie folgende, aus der Vorlesung bekannte, Sprache.
\( \text { RuCKSACK }=\left\{\begin{array}{l|l} \langle G, W, g, w\rangle & \begin{array}{c} G=\left\{g_{1}, \ldots, g_{n}\right\}, W=\left\{w_{1}, \ldots, w_{n}\right\}, g, w \in \mathbb{N}, \\ \text { für } 1 \leq i \leq n \text { ist } g_{i}, w_{i} \in \mathbb{N}, \text { und es } \end{array} \\ \text { gibt } S \subseteq\{1, \ldots, n\} \text { mit } \sum \limits_{i \in S} g_{i} \leq g \text { und } \sum \limits_{i \in S} w_{i} \geq w . \end{array}\right\} \)

Gehen Sie im folgenden davon aus, dass Sie Zugriff auf ein Orakel \( \mathfrak{O}_{\mathrm{RS}} \) haben. Gegeben eine Instanz \( I=\langle G, W, g, w\rangle \) kann Ihnen dieses Orakel in einem Zeitschritt beantworten, ob \( I \) in RuCKSACK liegt, oder nicht.
Zeigen Sie: Eine DTM, die \( \mathfrak{O}_{\mathrm{RS}} \) verwenden darf, kann
1. gegeben \( \langle G, W, g, w\rangle \in \) RuCKSACK in polynomieller Zeit ein \( S \subseteq\{1, \ldots, n\} \) berechnen, sodass \( \sum \limits_{i \in S} g_{i} \leq g \) und \( \sum \limits_{i \in S} w_{i} \geq w \).
2. gegeben \( \langle G, W, g\rangle \) in polynomieller Zeit ein \( w \in \mathbb{N} \) berechnen, sodass \( \langle G, W, g, w\rangle \in \) Rucksack, aber \( \langle G, W, g,(w+1)\rangle \notin \) Rucksack. Hierbei können Sie den Algorithmus aus Teilaufgabe 1 benutzen, müssen sich aber klar machen, was polynomiell in Bezug auf die Eingaben bedeutet.

Ich bin mir ziemlich sicher, dass ich dynamische Programmierung verwenden muss, weil ich mir nicht vorstellen kann wie man sonst in polynomieller Zeit die Elemente in S betrachten kann. Weiß allerdings nicht, wie genau ich das anstellen soll. Bin für jeden Tipp dankbar,

Aufgabe:

blob.png

Text erkannt:

Aufgabe 3 (Such- und Optimierungsvarianten)
(12 Punkte)
Betrachten Sie folgende, aus der Vorlesung bekannte, Sprache.
\( \text { RuCKSACK }=\left\{\begin{array}{l|l} \langle G, W, g, w\rangle & \begin{array}{c} G=\left\{g_{1}, \ldots, g_{n}\right\}, W=\left\{w_{1}, \ldots, w_{n}\right\}, g, w \in \mathbb{N}, \\ \text { für } 1 \leq i \leq n \text { ist } g_{i}, w_{i} \in \mathbb{N}, \text { und es } \end{array} \\ \text { gibt } S \subseteq\{1, \ldots, n\} \text { mit } \sum \limits_{i \in S} g_{i} \leq g \text { und } \sum \limits_{i \in S} w_{i} \geq w . \end{array}\right\} \)

Gehen Sie im folgenden davon aus, dass Sie Zugriff auf ein Orakel \( \mathfrak{O}_{\mathrm{RS}} \) haben. Gegeben eine Instanz \( I=\langle G, W, g, w\rangle \) kann Ihnen dieses Orakel in einem Zeitschritt beantworten, ob \( I \) in RuCKSACK liegt, oder nicht.
Zeigen Sie: Eine DTM, die \( \mathfrak{O}_{\mathrm{RS}} \) verwenden darf, kann
1. gegeben \( \langle G, W, g, w\rangle \in \) RuCKSACK in polynomieller Zeit ein \( S \subseteq\{1, \ldots, n\} \) berechnen, sodass \( \sum \limits_{i \in S} g_{i} \leq g \) und \( \sum \limits_{i \in S} w_{i} \geq w \).
2. gegeben \( \langle G, W, g\rangle \) in polynomieller Zeit ein \( w \in \mathbb{N} \) berechnen, sodass \( \langle G, W, g, w\rangle \in \) Rucksack, aber \( \langle G, W, g,(w+1)\rangle \notin \) Rucksack. Hierbei können Sie den Algorithmus aus Teilaufgabe 1 benutzen, müssen sich aber klar machen, was polynomiell in Bezug auf die Eingaben bedeutet.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community