1

1 つの数字「n」と数字の表があるとします。表の中から 4 つまでの数字を選びたいのですが、それら 4 つの合計が n に最も近いものになります。テーブルの長さ 'L' を指定すると、実行する必要がある組み合わせの数は (6*L + 11*L^2 + 6*L^3 + L^4)/24 です。

元。変数があるとします

n = 100

と数の集合

t = {86, 23, 19, 8, 42, 12, 49}

このリストを考えると、n に最も近い 4 の組み合わせは 49 + 23 + 19 + 8 = 99 です。

可能な限り少ない計算回数でこれを行う最適な方法は何ですか?

4

2 に答える 2

2

これは、NP 完全であることが知られている「サブセット合計」 ( http://en.wikipedia.org/wiki/Subset_sum_problemを参照) 問題のバリエーションのように見えるため、残念ながら、おそらく賢いアルゴリズムは存在しないでしょう。最悪の場合、アイテム数の指数関数的な速度で実行されます。

チェックする項目が多くない場合 (約 10 程度) は、できるだけ早く深さ優先検索でブランチを枝刈りしてみてください。

最適な解を探す代わりに、チェックする項目がもっとたくさんある場合は、ある程度適切な近似値を見つけようとする方がよいでしょう。

于 2013-03-26T19:37:15.593 に答える
0

すべての数値が正の整数であると仮定すると、Yexo が指摘したように実行できます。 

local n = 100
local t = {86, 23, 19, 8, 42, 12, 49}
local max_terms = 4
-- best[subset_size][terms][k] = {abs_diff, expr}
local best = {[0] = {}}
for k = 1, n do best[0][k] = {k, ''} end
for terms = 0, max_terms do best[terms] = best[0] end
for subset_size = 1, #t do
   local new_best = {}
   for terms = subset_size == #t and max_terms or 0, max_terms do
      new_best[terms] = {}
      for k = subset_size == #t and n or 1, n do
         local b0 = best[terms][k]
         local diff = k - t[subset_size]
         local b1 = terms > 0 and (
            diff > 0 and {
               best[terms-1][diff][1],
               best[terms-1][diff][2]..'+'..t[subset_size]
            } or {math.abs(diff), t[subset_size]}
         ) or b0
         new_best[terms][k] = b1[1] < b0[1] and b1 or b0
      end
   end
   best = new_best
end
local expr = best[max_terms][n][2]:match'^%+?(.*)'
print((loadstring or load)('return '..expr)()..' = '..expr)

-- Output
99 = 23+19+8+49
于 2013-03-26T20:46:38.420 に答える