私はこれを逆に実行したくなりますが、許可されているかどうかはわかりません (私のコメントを参照してください)。
したがって、値を 1 つずつ削除する代わりに、合計が範囲内にある最小のサブリストを見つけましょう!
問題があります-サブセット合計の問題はnp-completeであるため、このアプローチもそうです。(範囲が 0 である状況を想像してみてください。それは同じ問題です。)
この問題を O(2 N/2 ) で解く既知のアルゴリズムがあります。いくつかの Python コードのモックアップを作成しますが、それまでの間、ウィキペディアのページが役立つはずです。範囲内で最小のリストを見つけたいので、明らかに少し変更する必要があります。
基本的に、リストをそれぞれ長さ N/2 の 2 つの任意のサブリストに分割します (リストには N 個の要素があります)。次に、各リストにすべてのサブセットを生成し、それらの合計を計算します。(ここでは、サブセットとその合計を辞書に保存するので、どの数値が残っているかがわかります。最小のものだけを見つけたいので、より小さいものと同じ合計を持つすべてのサブセットも削除します。)これらのリストを並べ替え、範囲内に収まる合計がすべて見つかるまで、順方向と逆方向に実行します。最後に、どれが最も少ない要素を含んでいるかを調べれば、準備完了です!
最終的なリストが範囲内にある限り、ルールに違反する排除を行うことが許可されている場合は、この質問を確認してください
編集：ここにいくつかのPythonがあります。それは：
テストされていない
Python、特に高速ではない
明らかに最適ではない
リファクタリングが急務
しかし、一般的な考え方としては、取得できる最速のアルゴリズムだと思います。もっと速いコンセプトに興味があります！
>>> from itertools import combinations, chain
>>>
>>> available = [-10, -5, -2, 7, 9, 15]
>>> target = (10, 18)
>>>
>>>
>>>
>>> def powerset(iterable): # from https://stackoverflow.com/questions/374626/how-can-i-find-all-the-subsets-of-a-set-with-exactly-n-elements
... xs = list(iterable)
... # note we return an iterator rather than a list
... return chain.from_iterable(combinations(xs, n) for n in range(len(xs)+1))
...
>>>
>>> def getMinList(available, target):
... middleIndex = len(available)/2
... l1 = available[:middleIndex]
... l2 = available[middleIndex:]
... dict1 = {}
... dict2 = {}
... for subset in powerset(l1): # reverse so only the smallest subsets are used.
... total = sum(subset)
... if total not in dict1:
... dict1[total] = subset
... for subset in powerset(l2):
... total = sum(subset)
... if total not in dict2:
... dict2[total] = subset
... sortedDict1 = sorted(dict1.iteritems())
... sortedDict2 = sorted(dict2.iteritems())
... resultList = ()
... minValues = middleIndex * 2
... for k1, v1 in sortedDict1:
... for k2, v2 in reversed(sortedDict2):
... sumOfSubsets = k1 + k2
... if sumOfSubsets <= target[1] and sumOfSubsets >= target[0]:
... newTuple = v1 + v2
... lenNewTuple = len(newTuple)
... if (lenNewTuple) < minValues:
... resultList = ((sumOfSubsets, newTuple))
... minValues = lenNewTuple
... return resultList
...
>>> getMinList(available, target)
(15, (15,))
>>>
>>> target = (10, 10)
>>>
>>> getMinList(available, target)
(10, (-5, 15))
>>>
>>> target = (19, 22)
>>>
>>> getMinList(available, target)
(22, (7, 15))