効率的なアルゴリズム、またはそれを実現するPHPライブラリがありましたら教えて下さい。
配列:arr
組み合わせ限界値:x
上記２つが与えられた時、
arrの組み合わせがxに最も近くなる組み合わせを計算するいい方法はないでしょうか？
arrには数値のみが格納されます。
ログインして回答する
みんなの回答
-
motoyan
※組み合わせ限界値について、１つ抜けていたので補足します。
配列の組み合わせ＜＝組み合わせ限界値
となるような結果を求める計算になります。
例１：
配列
[1,2,3,4,5]
組み合わせ限界値
3
この時`1,2`の組み合わせと`3`２つの組み合わせを検索出来ればよい。
例２：
配列
[6,10,100,8,4]
組み合わせ限界値
111
この時`10,100`の組み合わせと`6,100,4`２つの組み合わせを検索出来ればよい。
可能であれば組み合わせに利用した値のキー（PHPなので）も保持出来ればより良いです。
この質問へのコメント
質問の情報
- 登録日時
- 2013-12-11 18:44:33
- 終了日時
- 2013-12-18 18:45:03
- 回答条件
- 1人5回まで
この質問のカテゴリ
この質問に含まれるキーワード
人気の質問
-
友人が飲み会で勢いで浮気をしてしまったようで、非常に後悔している様子でした。 そして、その子が彼氏に…
匿名質問者
2
-
明色化粧品の社名の由来を教えてください。匿名質問者1
-
英語等の先生など外国語の指導者の方、また、帰国子女の方、お伺いさせてください。外国語は外国語として理…匿名質問者
-
平日と休日の夜５時から夜の10時まででアニメをやっていない局は テレビ朝日、日本テレビ、フジテレビ、tbs…匿名質問者2
-
音楽のドレミですが、ドイツでは、ABCです（アーベーツェー）。英米でも、ABC（エービーシー）です。イタリ…匿名質問者1
1
また，arrとxの具体例を書いて下されば，質問文の意味が理解されやすいと思います。
宜しくお願い致します。
要素の和が指定値（限界値）以下となる組合せという事なんですね。
どのような業界（学界）で必要となるものかは知りませんが、ライブラリは該当の界隈でお尋ねの方が良いのではありませんか？
あまり一般的なものだとは考え難いので。
（ただの勉強不足かもしれませんが...）
順列、組合せを求めるライブラリの改造で対応できるかもしれません。
組合せの条件が決まっているので、総当たりではなく途中で走査を打ち切れると思いますが、・元の配列の要素数が多い
・配列の要素に小さい値が多く指定値が大きな値
等の場合、かなり重い計算になるのは必至ですね。
「重量の異なる複数の商品を、特定のコンテナで運ぶとする。
商品の重量は配列arrに格納されている。
コンテナの最大積載容量はｘであり、一度に運ぶ貨物の合計重量がこの値を超えてはならない。
この時、コンテナ内をできるだけ満杯にするような商品の選び方をアルゴリズムとして実装せよ。」
こういう処理要件であれば、キャパシティが関係する場合は、いつでも必要になりますよね。
テーブルや部屋に団体客を効率的に案内する場合とか…。
という事ですね？
（※PHPが出てくる時点で、まず学術系の話では無いなと…。）
100～200ポイント付けて質問を投稿し直せば、
すぐに回答がついて誰か実装してくれるでしょう。
私が実装してもいいし。
ただし質問文の内容は、コメント欄で突っ込まれている通り、分かりやすく書き換えて投稿する必要がありますけど。