ある数値に一致する複数の値の組み合わせ

実現したいこと

C#で、ある数値に一致、若しくは、一番近い値を
複数の値の組合せで取得したいと考えております。
※同じ値を複数回使用可
※ある数値を超える組合せは不可

計算するのに良い方法が御座いましたらご教示願います。

例

ある数値：600
複数の数値：480、410、240、180
答え：240, 180, 180

ある数値：900
複数の数値：480、410、240、180
答え：
480, 410
180, 180, 180, 180, 180

maisumakun

2018/05/30 04:58

後半の方は「180が5つ」でちょうど900になるのですが、それは間違いなのでしょうか。

shu

2018/05/30 05:19

maisumakun様、ご指摘の通りこちらでも間違いありませんので、内容を修正致しました。ありがとうございます。

ponpu1601

2018/05/30 07:39

ちょうど900があった場合、480,410は答えになるのでしょうか。

ozwk

2018/05/30 08:04

「ある数値」:5,「複数の数値」:{2}であった場合、答えは{2,2}ですか?{2,2,2}ですか?両方ですか?

shu

2018/05/31 02:38

ponpu1601様、記載頂いた通り、900で480,410は答えになります。

shu

2018/05/31 02:38

ozwk様、仕様が漏れておりました、ある数値を超える場合は不可となります。

ponpu1601

2018/05/31 02:57

2番目の例題は410+480=890ですが、180*5が900に最も近い値となるのではないでしょうか

行動規範の内容に同意します

回答3件

ベストアンサー

言うほど容易い問題ではないように思いますが、習作として書いてみました。
answersに答えになり得る組合せの配列の配列が入ります。

csharp
1class Program
2{
3    static void Main(string[] args)
4    {
5        var ns = new[] { 480, 410, 180, 240, };
6        var target = 900;
7        var answers = FindCombination(ns.OrderBy(x => x).SelectMany(n => Enumerable.Repeat(n, target/ n + 1)), target); //同じものを何度でも繰り返し使っていいとのこと。
8    }
9    public static IEnumerable<IEnumerable<int>> FindCombination(IEnumerable<int> items, int targets)
10    {
11        var cnt = items.Count();
12        var val = targets + items.Max();
13        var table = new List<IEnumerable<int>>[cnt + 1, val];//構築対象
14        for (var i = 0; i <= cnt; i++) //初期化
15        {
16            for (var j = 0; j < val; j++)
17            {
18                table[i, j] = new List<IEnumerable<int>> { };
19            }
20        }
21        table[0, 0] = new List<IEnumerable<int>> { new[] { 0 } }; //Count() > 0だったら構築可能と判定するための初期値
22        for (var i = 0; i < cnt; ++i) //利用可能な数値の1つずつを使って/使わないで作れる数値を構築していく
23        {
24            for (var j = 0; j < val; ++j)
25            {
26                foreach (var them in table[i, j])
27                {
28                    table[i + 1, j].Add(them);
29                }
30                var c = items.ElementAt(i);
31                if (j >= c)
32                {
33                    foreach (var them in table[i, j - c])
34                    {
35                        if (!them.Any()) { continue; }
36                        table[i + 1, j].Add(them.Concat(new int[] { c }));
37                    }
38                }
39            }
40        }
41        var idx = FindNearest(Enumerable.Range(0, val).Where(x => table[cnt, x].Any(y => y.Any())), targets); //構築済みのデータから作れる数値のうちで求める答えに近い1つを取る
42        return table[cnt, idx].Select(x => x.Where(y => y != 0)).Distinct(new EnumerableIntEqualityComparer()); //便宜的に入れた0をとり、重複を排除して返す
43    }
44    //近そうな数値を取る(絶対値の差分が同じ場合、より先にある1つだけを返す)
45    public static int FindNearest(IEnumerable<int> haystack, int needle) => haystack.Aggregate((n, next) => Math.Abs(needle - n) > Math.Abs(needle - next) ? next : n);
46}
47// Distinct用の比較関数
48class EnumerableIntEqualityComparer : IEqualityComparer<IEnumerable<int>>
49{
50    public bool Equals(IEnumerable<int> x, IEnumerable<int> y)
51    {
52        if (x == null && y == null)
53            return true;
54        if (x == null || y == null)
55            return false;
56        return x.SequenceEqual(y);
57    }
58
59    public int GetHashCode(IEnumerable<int> p)
60        => string.Join("",p.OrderBy(x=>x)).GetHashCode();
61}

これで試すと、900のとき180が5つのみならず、480,240,180や240,240,240,180が答えなことも分かりました。
質問で指摘された5のとき、2,2が答えなのか、2,2,2が答えなのかについては、対応していません。

投稿2018/05/30 14:22

papinianus

総合スコア12705

別言語ですが、TreeNodeを利用して算出する方式で書いてみました。

ある数値：600
複数の数値：480、410、240、180

「ある数値」をgoalとし、「複数の数値」をnumbersとしています。

1.numbersを降順に並べ替え
2.numbersの各要素で( goal <= number * n )となる最初のn(n>0)までの組み合わせを保持するNodeを作成
3.( goal > number * n )となるNodeだけ、「goal = goal - number * n」「 numbers = [2で使った要素よりも小さい数で再構成したnumbers]」として、1-3を再帰的に実行
4.rootNodeから各Nodeまでで保持する数値の組み合わせをすべてリスト化
5.4のリストの各要素の合計値とgoalを比較し、差分が最小のものを解として出力

…のようにしています。

追記：

仕様が漏れておりました、ある数値を超える場合は不可となります。

↑こちらを反映

// javascriptで実装

/** Node生成 */
let newNode = (arr)=>{
  let o = {
    sum : arr.reduce((a,b)=>{return a+b;}),
    arr : arr,
    children : []
  };
  return o;
};

/** Nodeを作りつつTree構造を構築 */
let createTree = (goal, numbers)=>{
  let nodelist = [];
  numbers = numbers.sort((a,b)=>{ return b-a; });
  // 重複する値を削除
  numbers = numbers.filter((n,i,arr)=>{return (i==0)||(arr[i-1]!=n);});
  
  numbers.forEach((n)=>{
    let div = Math.floor(goal / n);
    //for(let i = 1; i < div + 2; i++){ // goalよりも大きい和を含む場合
    for(let i = 1; i < div + 1; i++){ // goalよりも大きい和を含まない場合
      let arr = Array(i).fill(n);
      let o = newNode(arr);
      if(o.sum < goal){
        o.children = createTree(
          (goal - o.sum),
          numbers.filter(n=>{
            return n<o.arr[o.arr.length - 1];
          })
        );
      }
      nodelist.push(o);
    }
  });
  return nodelist;
};

/** Rootから各Nodeまでの組み合わせをリスト化 */
let extract = (nodelist)=>{
  let list = [];
  
  let exfunc = (path=[])=>{
    return (node)=>{
      let current = path.concat(node.arr);
      list.push(current);
      list.concat(node.children.forEach(exfunc(current)));
    };
  };
  
  nodelist.forEach(exfunc());
  
  return list;
};

/** 主処理 */
let testfunc = (goal, numbers)=>{
  let treelist = createTree(goal, numbers);
  let listOfList = extract(treelist);
  
  let max = goal;
  let candidates = [];
  
  listOfList.forEach(arr=>{
    let diff = Math.abs(goal - arr.reduce((a,b)=>{return a+b;}));
    if(max > diff){
      max = diff;
      candidates = [];
    }
    if(max >= diff){
      candidates.push(arr);
    }
  });
  
  candidates.forEach(arr=>{
    let line = "";
    let sep = "[";
    arr.forEach(n=>{
      line += sep + n;
      sep = ",";
    });
    line += "]";
    console.log(line);
  });
}

// 実行結果

testfunc(600,[480,410,240,180]);
// [240,180,180]

testfunc(900,[480,410,240,180]);
// [480,240,180]
// [240,240,240,180]
// [180,180,180,180,180]

投稿2018/05/30 14:14

編集2018/05/31 09:00

tkturbo

総合スコア5572

だいぶ愚直ですが、私だったら以下のような感じで。

main()
{
	複数の数値をソート　数値リストT[]
	ある数値を定義　数値A
	答えの数値リストを定義　数値リストAA[][]
	答えの数値リストを定義　数値リストA[]

	再帰チェック(目的値、int.max、数値リストT、数値リストAA、数値リストA)
	数値リストから最適な解を選択

}

----------------------------------------------------------------------------------

再帰チェック(目的値、数値T、数値リストT、数値リストAA、数値リストA)
{
    数値リストTから数値を順に取り出し(数値TT)ループ
    {
        if(数値TT>数値T)
        {何もしない}
        else if(数値リストAの総和+数値TT<目的値)
        {
            数値リストA.add(数値tmp)；
            再帰チェック(目的値、数値TT、数値リストT、数値リストAA、数値リストA)    
        }
        else
        {
			if(数値リストAAに数値リストAが登録済みでない)
			{
				数値リストAA.add(数値リストA)；
			}
			
			tmp数値リストA<==数値リストA
            tmp数値リストA.add(数値tmp)；
			if(数値リストAAにtmp数値リストAが登録済みでない)
			{
				数値リストAA.add(tmp数値リストA)；
			}

			
        }
    }
}

投稿2018/05/30 06:17

編集2018/05/30 08:15