私は動的プログラミングに苦労しており、必然的に助けが必要です!私はとても感謝しています。何時間も私は再帰的メソッドを非再帰的メソッドに変換しようとしていましたが、それを行うことはできませんでした。私の最初の仕事は、反復方程式の2つのアルゴリズムを書くことでした。最初の方法は再帰的方法であり、もう1つはループを使用してデータを保存する方法です。再帰的メソッドを非再帰的Cに変換する
は二つの整数、NおよびW、および2つの整数列S [N]及びp [N]があります。再帰的メソッドG1(n、w)の戻り値を見つけ、同じタスクを完了するメソッドG2(n、w)を作成する必要がありますが、再帰の代わりにループを使用する必要があります。
private static int G1(int k, int r)
{
if (k == 0 || r == 0)
{
return 0;
}
if (s[k - 1] > r)
{
return G1(k - 1, r);
}
return Max(G1(k - 1, r), p[k - 1] + G1(k - 1, r - s[k - 1]));
}
私はC#のための可能な解決策を見つけたが、私は私の式のためにそれを適用することができませんでした:
これは私のコードと初期データであり、私はそれを働かせることができません:
n = 3;
w = 3;
s = new List<int>{ 2, 3, 8 };
p = new List<int> { 1, 3, 5 };
private static int G2(int k, int r)
{
List<Tuple<int, int, int>> data = new List<Tuple<int, int, int>>();
data.Add(new Tuple<int, int, int>(0, 0, 0));
do
{
if (data[0].Item1 == 0 || data[0].Item2 == 0)
{
data[0] = new Tuple<int, int, int>(data[0].Item1, data[0].Item2, 0);
}
else
{
if (s[data[0].Item1 - 1] > data[0].Item2)
{
data.Add(new Tuple<int, int, int>(data[0].Item1 - 1, data[0].Item2, data[0].Item3));
}
if (data[0].Item1 + 1 >= k)
{
data.Add(new Tuple<int, int, int>(data[0].Item1 - 1, data[0].Item2, data[0].Item3));
}
if (data[0].Item2 + 1 >= r)
{
data.Add(new Tuple<int, int, int>(data[0].Item1 - 1, data[0].Item2 - s[data[0].Item1 - 1], data[0].Item3 + p[data[0].Item1 - 1]));
}
}
Console.WriteLine($"DEBUG: current k: {data[0].Item1} current r: {data[0].Item2} current result: {data[0].Item3}");
data.RemoveAt(0);
} while (data.Count > 0 && data.Count(entry => entry.Item1 == k && entry.Item2 == r) <= 0);
return data.First(entry => entry.Item1 == k && entry.Item2 == r).Item3;
}
こんにちは。私はあなたのアルゴリズムの複雑さに入ることはできません - 非常に痛い片頭痛を誘発するのに十分に見えます!しかし、一般的に言えば、実際に再帰せずに再帰的な振る舞いをする必要があるときは、スタックを使用してデータをプッシュし、終了するまでそれをポップし続けることになります。 https://msdn.microsoft.com/en-us/library/3278tedw(v=vs.110).aspx –
投稿したコードの2番目の部分では、** data **コレクションを**で初期化します0,0,0)のエントリ**を返すので、ループに入るとすぐに最初の** If **条件の中に入り、後で** Console.WriteLine(**)命令にジャンプします。最初のエントリ**したがって、** while **ループ条件を終了させる原因となるコレクション** empty **を残します。フェッチするための** First()**項目がないので、戻りコードは例外を与えます。これは意図されていますか? – Innat3
なぜこの「ダイナミックプログラミング」と呼ばれましたか? – Enigmativity