Schreibe ein Pseudocode der wahr/falsch zurückgibt wenn die Teilmenge T die Eigenschaft erfüllt/ nicht erfüllt

Question

Aufgabe:

Seien \( n, k \in \mathbb{N} \) und eine Menge \( S=\left\{s_{1}, \ldots, s_{k}\right\} \) mit \( s_{i} \in\{0,1,2,3, \ldots\} \) gegeben. In dieser Aufgabe gilt es herauszufinden, ob es eine Teilmenge \( T \subset S \) gibt, sodass \( \sum \limits_{t \in T} t=n \).
Schreiben Sie einen Pseudocode, der Wahr zurückgibt, falls es eine solche Menge \( T \) gibt, und sonst Falsch.

Problem/Ansatz:

Welche Blöcke müssen benutzt werden? Ich verstehe generell den Ansatz hier nicht. Kann mir das jemand erklären und dabei die Blöcke 1 bis 15 nutzen?

Comments

Hallo,

also der 'Ansatz' oben gibt keinen Sinn. Es ist nur eine zusammenhanglose Abfolge von Programmstatements. Und das Problem ist eher schwierig zu lösen. Es ist identisch mit der Aufgabe aus einer vorgegenen Menge von Münzen und Scheinen einen bestimmten Betrag zusammen zu stellen.

Das macht u.a. der Greedy-Algorithmus.

---

Hallo, ein Teil der Blöcke (nicht unbedingt alle) können so angeordnet werden, dass wahr zurückgegeben wird, wenn eine solche Menge existiert und falsch wenn es keine solche Menge gibt aber kenne die Blöcke und ihre Anordnung nicht, weil ich den Ansatz generell nicht verstehe

Answer 1

Okay, ich schildere dir mal ein paar Überlegungen, die dir helfen sollten, dein Problem zu lösen:

Ein kleines Beispiel dann wirds vielleicht schon deutlich
\(n = 6\) \( s_i =\{2,3,4\}\)
Ich möchte prüfen, ob es eine Summe von bestimmten \(s_i\), sodass \( s_3=4\)  letztes Glied dieser Summe ist und dass diese Summe 6 ergibt.
Und das kann ich prüfen, indem ich checke, ob es eine Summe gibt, mit der ich die Zahl \( 6  - 4 = 2\) abbilden kann.
Vorher muss ich also einmal gecheckt haben, ob ich die Zahl 2 darstellen kann. Das würde auch wieder nach dem selben Prinzip gehen

\( \rightarrow\) mit \(s_1=2\)  habe ich \(2-2=0\), also lässt gibt es die Summe mit der \(2 \) als letztes Glied(und einziges)

Also weiß ich, dass ich die ich die Zahl \(6\) als Summe meiner \(s_i\) darstellen kann.

Dafür definieren wir uns im Algorithmus eine zweidimensionale Datenstruktur \(d(i,j)\), die besagt, ob ich die Zahl \(i\) als Summe darstellen kann mit letztem Glied \(s_j\) .

Wichtig ist hier natürlich, dass wir, anders als im Beispiel, natürlich aufsteigend sowohl durch die Werte von n laufen.
Als Vereinfachung kann man sich mal ausdenken, ob man \(s_i \) überhaupt betrachten muss, wenn dieses echt größer als n ist.

Comments

Hey, danke für die Erklärung. Versuche seit Tagen etwas Sinnvolles herauszubekommen, aber habe es noch nicht ganz verstanden. Könntest du vielleicht die Blöcke anordnen (1-15)? Möchte den Algorithmus wenigstens einmal nachvollziehen können. Wäre echt nett

---

Wenn du explizite Fragen hast, kann ich dir gerne helfen.
Teile doch mal deine bisherigen Überlegungen.
Bin kein Fan von direkten Lösungen, sorry.

---

Kein Problem, kann ich verstehen. Ich verstehe die Datenstruktur nicht.

Zum Beispiel

d(i,j) <- d(i-1,j-s_i)

Warum dekrementiert man i und warum zieht man s_i von j ab? Ich verstehe generell nicht, wie man mithilfe dieser Rechnung bestimmen kann, ob es eine Teilmenge T geben kann. Da ich die Datenstruktur, wie sie im Algorithmus definiert ist, nicht ganz verstehe und das der Kern des Algorithmus ist, bin ich auch nicht in der Lage, eine Reihenfolge zu finden. Ich glaube, ich werde das nicht nachvollziehen können

---

Glaube ich die Datenstruktur auch nicht ganz korrekt beschrieben und hab oben einen Indexdreher drin gehabt.

d(i,j) heißt, dass ich mit einer Summe von Kombinationen aus s_1 bis s_i die Zahl j darstellen kann.
Das heißt für das Beispiel oben schaue ich mir an:
mit s_3 = 4
d(3,6) => Ich habe nun zwei Variante, die mir bestätigen,dass ich die Zahl abbilden kann.

Variante 1:habe ich die 6 schon einmal darstellen können mit s_1 bis s_2

oder

Variante 2:
habe ich die 2 schonmal darstellen können mit s_1 bis s_2, weil dann kann ich die 4 draufaddieren.