【C#】多次元配列とLINQ
探索のメモ化と動的計画法を扱う上での基礎知識として。
配列
配列 - C# によるプログラミング入門 | ++C++; // 未確認飛行 C
2次元配列とLINQ
多次元配列をLINQで扱う
多次元配列を LINQ で簡単に扱おう - xin9le.net
拡張メソッドを扱う場合は、静的クラス中に、 第一引数に this キーワードを修飾子として付けた static メソッドを書く
必要がある。
参考:拡張メソッド - C# によるプログラミング入門 | ++C++; // 未確認飛行 C
蟻本/ナップサック問題の再帰を使用した例をC#で
using System; namespace Program { class Program { const int n = 4; const int W = 5; readonly int[,] data = { { 2, 3 }, { 1, 2 }, { 3, 4 }, { 2, 2 } }; static void Main(string[] arg) { var p = new Program(); var dp = new int[p.data.GetLength(0) + 1, W + 1]; var result = p.rec(0, W, ref dp); Console.WriteLine("{0}", result); } public int rec(int i, int j, ref int[,] dp) { var res = 0; if (i == n) { res = 0; } else if (j < data[i, 0]) { res = rec(i + 1, j, ref dp); } else { res = Math.Max(rec(i + 1, j, ref dp), rec(i + 1, j - data[i, 0], ref dp) + data[i, 1]); } return dp[i, j] = res; } } }
出力: 7
memset での初期化をC#でどう書けばいいのかは分からなかった...