質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.62%

  • C#

    6827questions

    C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

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

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 306

-shu-

score 23

 実現したいこと

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

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

 例

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

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • -shu-

    2018/05/31 11:38

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

    キャンセル

  • -shu-

    2018/05/31 11:38

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

    キャンセル

  • ponpu1601

    2018/05/31 11:57

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

    キャンセル

回答 3

checkベストアンサー

+1

言うほど容易い問題ではないように思いますが、習作として書いてみました。
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<IEnumerable<int>> FindCombination(IEnumerable<int> items, int targets)
    {
        var cnt = items.Count();
        var val = targets + items.Max();
        var table = new List<IEnumerable<int>>[cnt + 1, val];//構築対象
        for (var i = 0; i <= cnt; i++) //初期化
        {
            for (var j = 0; j < val; j++)
            {
                table[i, j] = new List<IEnumerable<int>> { };
            }
        }
        table[0, 0] = new List<IEnumerable<int>> { 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<int> haystack, int needle) => haystack.Aggregate((n, next) => Math.Abs(needle - n) > Math.Abs(needle - next) ? next : n);
}
// Distinct用の比較関数
class EnumerableIntEqualityComparer : IEqualityComparer<IEnumerable<int>>
{
    public bool Equals(IEnumerable<int> x, IEnumerable<int> y)
    {
        if (x == null && y == null)
            return true;
        if (x == null || y == null)
            return false;
        return x.SequenceEqual(y);
    }

    public int GetHashCode(IEnumerable<int> p)
        => string.Join("",p.OrderBy(x=>x)).GetHashCode();
}


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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

別言語ですが、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]

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

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 15:55

    tamina様 回答ありがとうございます。
    早速試してみようと思いましたが、「数値リスト[].add(数値tmp);」は
    宣言がされておりませんが、どのように処理したら良いのでしょうか?

    キャンセル

  • 2018/05/30 15:57

    数値リストAでした。失礼しました。

    キャンセル

  • 2018/05/30 16:48

    再帰チェック関数の
    elseifの条件で、例えば
    数値リストAの総和=410,数値TT=200,目的値=600だった時、
    数値リストにはAAには総和が410の数値リストAが登録されませんか?

    キャンセル

  • 2018/05/30 16:51

    あ、確かに。。。
    上回るケースを許してなかった^^;

    キャンセル

  • 2018/05/30 16:54

    結局、全パターンの数列出して、一番近い値を出すしかなさそうですね

    キャンセル

  • 2018/05/30 17:01

    else句で数値リスト追加前に
    目的値-数値リストAの総和の絶対値と目的値-数値リストAの総和+数値TTの絶対値を比較して
    前者が低いなら登録、後者が低いなら数値TTを数値リストAにAddして登録、イコールなら両方登録とすればなんとか回避できる・・・?

    キャンセル

  • 2018/05/30 17:06

    確かに絶対値を使ったら、無駄なく行けそうですね。


    elseの中で超えちゃうパターンも一回だけ許して登録しておいて、
    解を絞るところに任せてもいいかも。

    キャンセル

  • 2018/05/30 17:15

    その方がすっきりしそうですね

    数値リストAAをDictionary<数値リスト,int>にして
    addするときに目的値に対する絶対値をValueに一緒に記録しておくと解チェックが楽になりそうです。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.62%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • C#

    6827questions

    C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。