効率的なアルゴリズム、またはそれを実現するPHPライブラリがありましたら教えて下さい。


配列:arr
組み合わせ限界値:x

上記2つが与えられた時、
arrの組み合わせがxに最も近くなる組み合わせを計算するいい方法はないでしょうか?

arrには数値のみが格納されます。

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2013/12/11 18:44:33
  • 終了:2013/12/18 18:45:03
id:k-motoyan888

※組み合わせ限界値について、1つ抜けていたので補足します。
配列の組み合わせ<=組み合わせ限界値
となるような結果を求める計算になります。

例1:
配列
[1,2,3,4,5]
組み合わせ限界値
3

この時`1,2`の組み合わせと`3`2つの組み合わせを検索出来ればよい。

例2:
配列
[6,10,100,8,4]
組み合わせ限界値
111
この時`10,100`の組み合わせと`6,100,4`2つの組み合わせを検索出来ればよい。


可能であれば組み合わせに利用した値のキー(PHPなので)も保持出来ればより良いです。

回答(0件)

回答はまだありません

  • id:language_and_engineering
    「組み合わせ限界値」とはどういう意味でおっしゃっているのかを,捕捉で書いていただけないでしょうか。
    また,arrとxの具体例を書いて下されば,質問文の意味が理解されやすいと思います。
  • id:k-motoyan888
    すみません、補足を書きました。
    宜しくお願い致します。
  • id:tezcello
    > 配列の組み合わせ<=組み合わせ限界値
    要素の和が指定値(限界値)以下となる組合せという事なんですね。

    どのような業界(学界)で必要となるものかは知りませんが、ライブラリは該当の界隈でお尋ねの方が良いのではありませんか?
    あまり一般的なものだとは考え難いので。
    (ただの勉強不足かもしれませんが...)


    順列、組合せを求めるライブラリの改造で対応できるかもしれません。
    組合せの条件が決まっているので、総当たりではなく途中で走査を打ち切れると思いますが、・元の配列の要素数が多い
    ・配列の要素に小さい値が多く指定値が大きな値
    等の場合、かなり重い計算になるのは必至ですね。
  • id:language_and_engineering
    ようやくイメージがわきましたよ。

    「重量の異なる複数の商品を、特定のコンテナで運ぶとする。
    商品の重量は配列arrに格納されている。
    コンテナの最大積載容量はxであり、一度に運ぶ貨物の合計重量がこの値を超えてはならない。
    この時、コンテナ内をできるだけ満杯にするような商品の選び方をアルゴリズムとして実装せよ。」

    こういう処理要件であれば、キャパシティが関係する場合は、いつでも必要になりますよね。
    テーブルや部屋に団体客を効率的に案内する場合とか…。

    という事ですね?

    (※PHPが出てくる時点で、まず学術系の話では無いなと…。)
  • id:language_and_engineering
    ということは、この程度の規模のプログラムなら、
    100~200ポイント付けて質問を投稿し直せば、
    すぐに回答がついて誰か実装してくれるでしょう。
    私が実装してもいいし。
    ただし質問文の内容は、コメント欄で突っ込まれている通り、分かりやすく書き換えて投稿する必要がありますけど。

この質問への反応(ブックマークコメント)

トラックバック

  • 効率的なアルゴリズム >http://q.hatena.ne.jp/1386755073>ある整数を要素に持つ配列の部分配列を考えたときに、その部分配列の要素の合計値が、ある値以下で且つ、最大になるような部分配列
「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません