合計の合計値がXとYの間で最も小さいオブジェクトの集合を見つけるアルゴリズム

Question

私はオブジェクト（約100）を持っていて、それぞれフロート値を持っています（現実的に-10000〜10000ですが、制限はありません）。

私の目標は、私はいくつかの進化的アルゴリズムで、このタスクに取り組むことができ信じて合計した値は、変数XとY

の間だろうそのうち（できるだけ少ないなど）、それらのオブジェクトの最小セットを見つけることですしかし、私はこれに簡単な数学的な解決策があるかどうか疑問に思っていましたか？

私はPHPでプログラミングしていますが、それは関連しているとは思えず、アルゴリズム/擬似コードに関するアイディアを使用することができます。

ありがとうございました！

Answer 1

あなたの問題はknapsack problemの変種のように見えます。この問題をスケールで解決する簡単な方法はありません - ブルートフォースは最小のインスタンスで動作します。適度に大きな問題についてはdynamic programmingを使用できます。一般に、mixed integer programming、さまざまなmetaheuristicsまたはconstraint satisfactionを使用している可能性があります。

私の意見では、最後のものがあなたに最適なはずです。たとえば、Minizincと考えてください。それは本当に使いやすく、ランタイム/メモリ消費量に関しては非常に効率的です。たとえば、ナップザック問題を解決する例を考えてみましょう。this

問題のテキスト表現を生成し、それをMinizincにフィードし、ソリューションを再度読むことができます。

Answer 2

Pythonを使用すると、安全に組み合わせのルートに行くことができます。

組み合わせは反復可能です：組み合わせを反復処理するたびに、一意のオブジェクトセットが返されます。

非常に低いサイズのセット（2,3,4個のオブジェクトなど）から始めて、値の合計を実行して確認することができます。

値の合計を実行するには、numpy.arraysを見てみることをお勧めします。それらは処理をスピードアップします。

背後では、組み合わせは階乗演算を使用します。これは、可能な組み合わせが指数関数的に多いことを意味します。

さらに詳しい情報：

Numpy Array

Itertools Combinations

これは、秒あたりの組み合わせの数千人をチェックすることを期待することができたためにブルートフォースで終了します。私はそれが最高のアルゴリズムであるかどうかはわかりませんが、それは簡単で機能します。

例コード：

from itertools import combinations 
import numpy 

a = [1,-2,3,-4,5,-6,7,-8] # Any list of float or integers... 
min = 5 
max = 10 
size = 3 
c = combinations(a, size) 
for combi in c: 
a = numpy.array(combi) 
if (a.sum() in range(min, max)): 
    print('Result found for '+str(combi)) 
    break