質問: ### 実現したいこと C#で、ある数値に一致、若しくは、一番近い値を 複数の値の組合せで取得したいと考えております。 ※同じ値を複数回使用可 ※ある数値を超える組合せは不可 計算するのに良い方法が御座いましたらご教示願います。 ### 例 ある数値:600 複数の数値:480、410、240、180 答え:240, 180, 180 ある数値:900 複数の数値:480、410、240、180 答え: 480, 410 180, 180, 180, 180, 180
回答: 言うほど容易い問題ではないように思いますが、習作として書いてみました。 answersに答えになり得る組合せの配列の配列が入ります。 ``` class Program { static void Main(string[] args) { var ns = new[] { 480, 410, 180, 240, }; var target = 900; var answers = FindCombination(ns.OrderBy(x => x).SelectMany(n => Enumerable.Repeat(n, target/ n + 1)), target); //同じものを何度でも繰り返し使っていいとのこと。 } public static IEnumerable> FindCombination(IEnumerable items, int targets) { var cnt = items.Count(); var val = targets + items.Max(); var table = new List>[cnt + 1, val];//構築対象 for (var i = 0; i <= cnt; i++) //初期化 { for (var j = 0; j < val; j++) { table[i, j] = new List> { }; } } table[0, 0] = new List> { new[] { 0 } }; //Count() > 0だったら構築可能と判定するための初期値 for (var i = 0; i < cnt; ++i) //利用可能な数値の1つずつを使って/使わないで作れる数値を構築していく { for (var j = 0; j < val; ++j) { foreach (var them in table[i, j]) { table[i + 1, j].Add(them); } var c = items.ElementAt(i); if (j >= c) { foreach (var them in table[i, j - c]) { if (!them.Any()) { continue; } table[i + 1, j].Add(them.Concat(new int[] { c })); } } } } var idx = FindNearest(Enumerable.Range(0, val).Where(x => table[cnt, x].Any(y => y.Any())), targets); //構築済みのデータから作れる数値のうちで求める答えに近い1つを取る return table[cnt, idx].Select(x => x.Where(y => y != 0)).Distinct(new EnumerableIntEqualityComparer()); //便宜的に入れた0をとり、重複を排除して返す } //近そうな数値を取る(絶対値の差分が同じ場合、より先にある1つだけを返す) public static int FindNearest(IEnumerable haystack, int needle) => haystack.Aggregate((n, next) => Math.Abs(needle - n) > Math.Abs(needle - next) ? next : n); } // Distinct用の比較関数 class EnumerableIntEqualityComparer : IEqualityComparer> { public bool Equals(IEnumerable x, IEnumerable y) { if (x == null && y == null) return true; if (x == null || y == null) return false; return x.SequenceEqual(y); } public int GetHashCode(IEnumerable p) => string.Join("",p.OrderBy(x=>x)).GetHashCode(); } ``` これで試すと、900のとき180が5つのみならず、480,240,180や240,240,240,180が答えなことも分かりました。 質問で指摘された5のとき、2,2が答えなのか、2,2,2が答えなのかについては、対応していません。