Dynamische Programmierung

Wissenschaft Informatik
#1

Hallo,
ich suche jemanden, der/die sich in dynamischer Programmierung auskennt und mir schreiben kann, ob mein Lösungsvorschlag richtig oder falsch ist . Es geht um eine die erste Teilaufgabe einer Klausur. Bin mir aber nicht sicher, ob dass wirklich zu dem Thema dynamische Programmierung gehört. Jedenfalls bezog sich die der zweite Teil auf dynamische Programmierung.
Es geht um einen Menge von Beträgen v1, v2, v3, …vn und einen Betrag B. Es sollen alle möglichen Kombinationen aus den Beträgen gebildet werden, um B darzustellen. Z.B. B= 12 v1=2 und v2=5
12=6*2=2*5+1*2
Hoffe, dass sich jemand meldet.

Felix

#2

Laesst sich mit dyn. Programmierung machen.
Einfacher Fall: wir wollen nur rausbekommen, was wir alles an Zahlen erzeugen koennen, wobei wir fuer jede Zahl einen Ausdruck wissen wollen (andere Varianten gehen aehnlich).

Denk Dir ein Array A von Ausdruecken (z.B. als String gespeichert)
In A[v1] schreiben wir „v1“ ind A[v2] „v2“ usw.

Nun brauchen wir zwei Schleifen In der aeuesseren zaehlen wir i
von 1 bis zur groessten Zahl, die uns interessiert, hoch.

Sollte A[i] nicht leer sein, so starten wir eine zweite
innere schleife dir e von 1 bis i hochzaehlt.
Ist A[e] nicht leer so setzen wir
A[e+i] auf A[e] + „+“ + A[i] (+ fuer Stringconkatenation)
und
A[e*i] auf A[e] + „*“ + A[i]

Ende Innere Schleife
Ende aeussere Schleife

Da e+i und e*i (da wir das ganze mit natuerlichen Zahlen spielen)
immer groesser als i sind, koennen wir fuer jeden Wert von i wissen, dass wir alle kleineren Werte, die sich darstellen lassen schon „erschlagen“ haben.

Das Dynamische daran ist, dass wir die gefundenen Teilloesungen immer wieder verwenden.

MfG
Martin

#3

Hallo,
ich habe das ganz anders gemacht. Moechte es mit einem Beispiel zeigen. Gegeben sind 2- und 5-DM Muenzen und ein Betrag, sagen wir mal 12 DM. Dann koennte man folgende Produkte bilden: 12=6*2DM=2*5 DM +1*2 DM. Den Algorithmus wuerde ich folgendermassen beschreiben:

  1. Tue folgendes bei fuer jeden Muenzbetrag
    1.1 Subtrahiere den Muenzbetrag v vom Betrag, bis der Betrag[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
#4

Hallo,
ich habe das ganz anders gemacht. Moechte es mit einem
Beispiel zeigen. Gegeben sind 2- und 5-DM Muenzen und ein
Betrag, sagen wir mal 12 DM. Dann koennte man folgende
Produkte bilden: 12=6*2DM=2*5 DM +1*2 DM. Den Algorithmus
wuerde ich folgendermassen beschreiben:

  1. Tue folgendes bei fuer jeden Muenzbetrag
    1.1 Subtrahiere den Muenzbetrag v vom Betrag, bis der
    Betrag
#5

Hi,
es gab den Hinweis mit der dynamischen Programmierung in der zweiten Teilaufgabe(der Klausur). Bei der ersten Teilaufgabe(das war die Aufgabe, die ich hier hin gepostet habe) gab es dazu kein Hinweis. Ich habe die Aufgabe so geloest, wie ich sie vor einigen Tagen hier beschrieben habe, weil ich den ganzen Kram mit der dynamischen Programmierung so gut wie gar nicht verstanden habe. Ausserdem bin ich nicht in der Lage sowas(z.B. meine vorschlagene Loesung) zu implementieren. Einige Sachen aus der Vorlesung kann ich nicht implementieren(Algorithmen und Datenstrukturen), sondern nur beschreiben, wie z.B. Graphenalgorithmen, Algorithmen in (a,b)-Baeume und Skip-Listen, etc…
Es geht fuer mich bei dieser Klausur nur um Bestehen(4.0) oder 5.0. Ich habe die Vorlesung „Datenstrukturen und Algorithmen?nur widerwillig gemacht und habe da auch die groessten Schwierigkeiten im Studium. Also, ich habe aus dem ganzen dazugelernt, dass nicht Mathe die Schwierigkeiten in einem Informatistudium sind, sondern die ganzen Vorlesungen aus der theoretischen Informatik

Felix

Hallo,
ich habe das ganz anders gemacht. Moechte es mit einem
Beispiel zeigen. Gegeben sind 2- und 5-DM Muenzen und ein
Betrag, sagen wir mal 12 DM. Dann koennte man folgende
Produkte bilden: 12=6*2DM=2*5 DM +1*2 DM. Den Algorithmus
wuerde ich folgendermassen beschreiben:

  1. Tue folgendes bei fuer jeden Muenzbetrag
    1.1 Subtrahiere den Muenzbetrag v vom Betrag, bis der
    Betrag