0

したがって、ソートされたリスト/配列、つまり[1,6,8,15,40]、配列のサイズ、および要求された数が与えられた場合..

そのリストから要求された数に合計するために必要な値の最小数をどのように見つけますか?

たとえば、配列 [1,6,8,15,40] が与えられた場合、数値 23 を要求すると、リストから 2 つの値 (8 と 15) を取得して 23 に等しくなります。関数は 2 (値の数) を返します。 ）。さらに、配列には無制限の数の 1 があります (したがって、関数は常に値を返します)。

どんな助けでも大歓迎です

4

2 に答える 2

2

NP 完全サブセット和問題は自明にあなたの問題に還元されます:整数の集合Sと目標値sが与えられると、Sの各x kに対して値(n+1) x kを持つ集合S'を構築し、目標を設定します。(n+1) sに等しい。元のセットSのサブセットの合計がsである場合、合計が(n+1) s の新しいセットには最大でn 個のサイズのサブセットが存在し、そのようなセットに余分な 1 を含めることはできません。そのようなサブセットがない場合、回答として生成されるサブセットには、少なくともn+1が含まれている必要があります。n+1の倍数になるには十分な数の1が必要なためです。

したがって、この問題は、コンピューティングの革命なしに多項式時間の解を受け入れることはできません。その免責事項が邪魔にならないので、セットの最大サイズが小さい場合に実際にうまく機能する、問題に対するいくつかの疑似多項式時間の解決策を検討できます。

これを行うPythonアルゴリズムは次のとおりです。

import functools
S = [1, 6, 8, 15, 40] # must contain only positive integers
@functools.lru_cache(maxsize=None) # memoizing decorator
def min_subset(k, s):
    # returns the minimum size of a subset of S[:k] summing to s, including any extra 1s needed to get there
    best = s # use all ones
    for i, j in enumerate(S[:k]):
        if j <= s:
            sz = min_subset(i, s-j)+1
            if sz < best: best = sz
    return best

print min_subset(len(S), 23) # prints 2

これは、値が制限されていれば、かなり大きなリスト (n=50 要素のランダムなリストをテストしました) の場合でも扱いやすいです。を使用するS = [random.randint(1, 500) for _ in xrange(50)]と、min_subset(len(S), 8489)実行に 10 秒もかかりません。

于 2012-09-26T23:06:27.130 に答える
0

もっと簡単な解決策があるかもしれませんが、リストが十分に短い場合は、すべての値のセットを試すことができます。

  • 1 --> 23 ではない
  • 6 --> 23 ではない
  • ...
  • 1 + 6 = 7 --> 23 ではない
  • 1 + 8 = 9 --> 23 ではない
  • ...
  • 1 + 40 = 41 --> 23 ではない
  • 6 + 8 = 14 --> 23 ではない
  • ...
  • 8 + 15 = 23 --> おお、これは 23 で、2 つの値を追加しました

リストがソートされていることがわかっている場合は、いくつかのテストをスキップできます。6 + 20 > 23 の場合、6 + 40 をテストする必要がないからです。

于 2012-09-26T23:02:05.480 に答える