合計が目標値に近づくようにグループ化するアルゴリズム

Question

私はアルゴリズムを見つけようとしていますが、私の正確な問題でグーグルが私に必要な正確な結果を見つけることができません。

数値とターゲットの合計が与えられました。私はそれらのグループの合計が目標値を超えないでできるだけ近くなるようにグループに数値を割り当てる必要があります。

Example Target Sum = 99 
Example Set = { 70, 40, 10, 70, 98, 14, 4, 7, 29, 11, 91, 50, 30 } 

何かのように目的の結果は次のようになります。彼らはすべて99

に近い数まで追加するので目標は、いくつかのグループとして持つことになります

{ 70, 29 } 
{ 40, 50, 7} 
{ 98 } 
{ 91, 4 } 
{ 70, 10, 11 } 
{ 30, 14 } 

...できるだけ。 私はリソースについてあまり心配する必要はありません。これは控えめに実行され、値の数はかなり少なくなります。

Answer 1

グループの数を最小にすることが目的であり、各グループの合計サイズが目標値を超えないことが唯一の制約である場合、考慮する問題はbin packing問題です。理解された。

一般に、First FitまたはFirst Fit Decreasingと呼ばれる比較的単純なヒューリスティックスは、2より小さい近似比を生成します。より正確には、First Fit Decreasingは、(11/9)OPT+(6/9)のタイトな比率をもたらします。ビンパッキングは、PTAS（したがって、FPTASなし）を認めるのではなく、(1+epsilon)OPT+1の比率を持つ漸近的なPTASであり、ここでepsilonは精度パラメータです。

比較的簡単に実装できる適切なソリューションが必要な場合は、First Fit Decreasingが候補になります。