ich hab's jetzt mit Jonas' hilfe verbessert - es gibt ne zweite Tabelle, die loggt, welche Werte nicht mehr berücksichtigt zu werden brauchen. - ich hab jetzt nicht mehr die Konzentration, um zu beurteilen, ob's wirklich stimmt, aber so geb ich's ab..
Kritik natürlich trotzdem willkommen... cu alex Alexander Nutz schrieb:
andererseits: im negativen Fall könnte ich sogar noch schlechter rauskommen, als der brute force-algo von unten, fürchte ich, dann berechnet man ja die ganzen Summen auch noch mehrfach... - vielleciht reicht's trotzdem für die AufgabeAlexander Nutz schrieb:ich hab ein bisschen drüber nachgedacht:es berechnet tatsächlich ziemlich viel mehrfach, aber es ist trotzdem besser als brute-force, würde ich sagen und nutzt die bereits bekannten Ergebnisse schon insofern aus, als dass auf diese drauf addiert wird.bei brute force würde ja jedes mal von null angefangen - bei Münzen 4,7 und zu erreichen 21 würde man ausprobieren 4+4+4+4 4+4+4+7 4+4+7+7 usw ca 16 Möglichkeiten wären Worst Case zu prüfen bei mir wären die Durchläufe: 4, 7 4,7, 8,11, 11,14 4,7,8,11,11,14, 8,11,12,15,18 11,14,15,18,21 jetzt hält er- das ist wohl auch kein Beweis über die asymptotische Worst-Case Laufzeit, der Punkt ist aber, dass er trotz vieler Mehrfachberechnungen die alten Ergebnisse durchaus ausnutzt. Natürlich ist es schicker, wenn man in dem Baum immer nur die relevanten Knoten betrachtet - das geht wohl gut per Rekursion, aber ich glaube schon noch, dass der Algorithmus dynamische Programmierung ausnutzt.Grüße alex Alexander Nutz schrieb:hm ist'n punkt.. ich denk drüber nach, danke. Jonas Gehring wrote:Nachtrag: Ich überlege gerade, ob dein Programm nicht trotz der Tabelle exponentielle Laufzeit hat und damit ja nicht wirklich dynamische Programmierung nutzt.Betrachtet man die sich ändernden Werte pro Runde, so werden doch in der gleichen Runde alle Schritte, die zu ihnen hingeführt haben, auch berechnet. Ein kleines Beispiel mit deinen Münzen:Runde 1: Tabelle: 4 und 7 Berechnet: 8, 11, 11, 14 Runde 2: Tabelle: 4, 7, 8, 11 und 14 Berechnet: 8, 11, 11, 14, 12, 15, 15, 18, 18, 21 Runde 3: Tabelle: 4, 7, 8, 11, 12, 14, 15, 18 und 21Berechnet: 8, 11, 11, 14, 12, 15, 15, 18, 16, 19, 18, 21, 19, 22, 22, 25, 25, 28Runde 4: Tabelle: 4, 7, 8, 11, 12, 14, 15, 16, 18, 19, 21, 22, 25, 28 Berechnet: ...Das sieht mir irgendwie stark nach dem Baum für die Fibonacci-Berechnung aus, aber genau begründen kann ich es aus zeitlichen Gründen gerade nicht. Intuitiv wird aber wie oben bereits gesagt in jeder Runde jeder Wert praktisch komplett neu berechnet (da alle vorherigen Rechnungen wiederholt werden).Wie dem auch sei, sobald du dir die Werte merkst, die sich ändern und im nächsten Durchlauf nur von diesen aus neue Werte berechnest, geht's natürlich.Gruß, Jonas On Sunday 21 December 2008 22:38:28 you wrote:Hi,Bitte sag falls ich mich irre, aber nach einem kurzen Blick sieht es für mich so aus als ob du einfach alle möglichen auszahlbaren Beträge aufzählst und sobald du den gegeben gefunden hast aufhörst. Allerdings generierst du die Werte in der Tabelle ständig neu, obwohl sich ja nur wenige ändern. Andererseits ist es meiner Meinung nach mit dynamischer Programmierung gelöst und deshalb auch richtig. Den Vorteil dynamischer Programmierungkann man hier allerdings etwas besser ausnutzen. Hier ist ein Vorschlag von mir, der genau andersrum rechnet, also den auszuzahlenden Betrag rekursiv zerlegt. Der Pseudocode im PDF sollte reichen, zur Sicherheit aber auch nochmal in C. Gruß, Jonas On Sunday 21 December 2008 22:17:47 Alexander Nutz wrote:Hallo,im Anhang ist ein Mini-Programm, dass ich zur 2 geschrieben habe - ist recht simpel, tut aber glaub ich schon, was es soll und verwendet auchdie Tabelle, wie vorgeschlagen.(ist C-Sharp Code, der eigentliche Code müsste aber fast identisch unterJava laufen..) Die Idee: Lege eine Bool-Tabelle der Größe Zahlbetrag+1 an mit der Bedeutung table[i]=true gdw ich kann betrag i bezahlen initialisiere mit den vorgegebenen Werten so lange sich noch was ändert addiere auf jeden true-Eintrag in der Tabelle jeden Münzwert drauf und trage das Ergebnis wieder in der Tabelle ein. gib den x-ten Eintrag aus Was denkt ihr? Grüße alex SilSie@xxxxxx schrieb:Hi,wenn du zuerst die große Münze "abfragst", findest du vielleicht nichtimmer eine Lösung, obwohl man den Betrag auszahlen könnte... siehe dazu Vorlesung über Greedy Algorithmen. Das schwere ist ja, dass wirklich jede Kombination von Münzen denBetrag ergeben könnte. Wenn man gleich den Betrag der größten abzieht,lässt man schon viele Möglichkeiten aus. Gruß, Silvan Jonas Gehring schrieb:Hi,Ich würde mal so anfangen: Für den Betrag testen ob er größer als eineMünze ist (am besten mit der größten anfangen). Falls ja, dannrekursiv die Methode für Betrag-Münze aufrufen. Wenn "ja" zurückkommt,"ja" zurückgeben, ansonsten es mit der nächstkleineren Münze versuchen. Wenn der Betrag gleich ist, dann nat. sofort "ja" zurückgeben. "Dynamisch" kann man das Ganze z.B. so machen, indem man vor jederRückgabe den Wert in einer Tabelle bzw. in einem Array speichert unddieses bei jedem Aufruf zuerst abfragt. Gruß, Jonas On Wednesday 17 December 2008 22:25:18 Silvan S. wrote:Hi,ich finde die Aufgabe keineswegs trivial. Wenn du dort "Ist dem nichtso probieren wir der Reihe nach den ganzen Array mit Münzwertendurch. " bist, was genau willst du dann machen? Nur auf Teilbarkeit überprüfen? Das reicht doch überhaupt nicht... Es könnte doch -jede- beliebige Kombination von Münzen den gewünschten Betrag x ergeben...Gruß, Silvan don.vito.c@xxxxxx schrieb:Hallo Lista,ich habe mir jetzt eine Menge Gedanken gemacht zu der Aufgabe, aberich komme nicht dahinter, warum wir das mit einem Array machensollen. Die Aufgabe ist ja eigentlich Erstsemester-mäßig. Ich finde es ist nämlich viel einfacher, einfach die kleinste Zahl im Array mit den Münzwerten zu nehmen und zu testen ob sie die andere Zahl teilt. Ist dem so, so sind wir fertig. Ist dem nicht so probierenwir der Reihe nach den ganzen Array mit Münzwerten durch.Vielleicht kann mir ja mal einer von euch sagen wozu man hier einen Array von Wahrheitswerten bilden soll. Ich finde da keinen wirklichguten rekursiven Ansatz. Gruß, Cornelius--- Sent through the Infostudents Mailinglist List Archive: //www.freelists.org/archives/infostudents/ Subscribe / Unsubscribe: //www.freelists.org/list/infostudents--- Sent through the Infostudents Mailinglist List Archive: //www.freelists.org/archives/infostudents/ Subscribe / Unsubscribe: //www.freelists.org/list/infostudents--- Sent through the Infostudents Mailinglist List Archive: //www.freelists.org/archives/infostudents/ Subscribe / Unsubscribe: //www.freelists.org/list/infostudents--- Sent through the Infostudents Mailinglist List Archive: //www.freelists.org/archives/infostudents/ Subscribe / Unsubscribe: //www.freelists.org/list/infostudents--- Sent through the Infostudents Mailinglist List Archive: //www.freelists.org/archives/infostudents/ Subscribe / Unsubscribe: //www.freelists.org/list/infostudents
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ATDynProg1
{
class Program
{
static void Main(string[] args)
{
bool[] table;
bool[] finalTable;
int[] coins;
int toBePaid = 1707; //(der zu zahlende wert)
int numberOfCoins = 2; //Anzahl der verschiedenen Münzwerte
coins = new int[numberOfCoins];
table = new bool[toBePaid+1];
//Tabelle, die verhindert, dass Werte (zu oft) mehrfach berechnet
werden
//- auf werte, die hier true sind, wurden bereits einmal alle
Münzwerte addiert
//final ist vielleicht nicht ganz das richtige Wort..
finalTable = new bool[toBePaid + 1];
coins[0] = 10;
coins[1] = 4;
//coins[2] = 15;
//Tabelle initialisieren (mit den Münzwerten)
for (int i = 0; i < numberOfCoins; i++)
{
table[coins[i]] = true;
}
//für jeden true-Eintrag in table und für jeden Münzwert,
addiere beide,
//mache Eintrag an der Stelle -Ergebnis- true, halte, wenn sich
nichts mehr ändert
bool changed = true;
while (changed && (table[toBePaid]==false))
{
changed = false;
for (int i = 1; i < table.Length; i++)
{
if (table[i]&&!finalTable[i])
{
for (int j = 0; j < numberOfCoins; j++)
{
int z = i + coins[j];
if (z <= toBePaid)
{
if (!table[z])
changed = true;
table[z] = true;
}
}
finalTable[i] = true;
}
}
}
//gibt das Ergebnis aus, also ob der Betrag toBePaid mit den
Münzwerten im coins-Array bezahlt werden kann
Console.WriteLine(table[toBePaid]);
Console.ReadLine();
}
}
}
