0

私の問題は、整数の配列の合計が値になる組み合わせの数を数える必要があることですW。

言ってみましょう:

int array[] = {1,2,3,4,5};

私のアルゴリズムは、から1までの長さのすべての組み合わせを見つけるだけです.W / minimum(array)WN

これを解決する他のアルゴリズムはありますか? より速くなるはずです:)

更新: OK、サブセット問題とナップザック問題は良いですが、私の問題は、配列の組み合わせが次のように要素を繰り返すことです:

1,1,1 -> the 1st combination
1,1,2
1,1,3
1,1,4
1,1,5
1,2,2 -> this combination is 1,2,2, not 1,2,1 because we already have 1,1,2. 
1,2,3
1,2,4
1,2,5
1,3,3 -> this combination is 1,3,3, not 1,3,1 because we already have 1,1,3. 
1,3,4
.
.
1,5,5
2,2,2 -> this combination is 2,2,2, not 2,1,1 because we already have 1,1,2. 
2,2,3
2,2,4
2,2,5
2,3,3 -> this combination is 2,3,3, not 2,3,1 because we already have 1,2,3.
.
.
5,5,5 -> Last combination

これらはすべて{1,2,3,4,5}長さ 3 の組み合わせです。部分和問題は、私が興味のない別の種類の組み合わせを提供します。

したがって、合計すると となる組み合わせWはW = 7、

2,5
1,1,5
1,3,3
2,2,3
1,1,2,3
1,2,2,2
1,1,1,1,3
1,1,1,2,2
1,1,1,1,1,2
1,1,1,1,1,1,1

更新: 本当の問題は要素の繰り返しにあり1,1,1、生成された組み合わせの順序は重要ではないため、および と1,2,1同じです。1,1,22,1,1

4

4 に答える 4

9

現在のところ効率的なアルゴリズムは存在せず、今後も存在しない可能性があります (NP 完全問題)。

これは部分和問題(のバリエーション)です。

于 2012-09-21T14:50:09.777 に答える
3

これはコイン交換の問題です。これは、Wとセットサイズの合理的な制限を伴う動的計画法によって解決できます。

于 2012-09-21T15:44:14.063 に答える
0

これを解決するために、この問題に対する再帰的および (非常に単純な) 動的プログラミングのソリューションを次に示します。より洗練された終了条件を使用することで、再帰ソリューションの実行時間を短縮できますが (時間の複雑さは短縮できません)、その主なポイントはロジックを示すことです。

私が見た動的計画法ソリューションの多くは、N x |c| 全体を保持しています。結果の配列ですが、行 i は行 i-1 から生成でき、さらに左から右の順に生成できるため、コピーを作成する必要がないため、これは必須ではありません。

コメントがロジックの説明に役立つことを願っています。dp ソリューションは十分に高速であるため、数ミリ秒以上かかる長時間オーバーフローしないテスト ケースを見つけることができませんでした。例えば：

$ time ./coins dp 1000000 1 2 3 4 5 6 7
3563762607322787603

real    0m0.024s
user    0m0.012s
sys     0m0.012s

// Return the number of ways of generating the sum n from the
// elements of a container of positive integers.
// Note: This function will overflow the stack if an element
//       of the container is <= 0.
template<typename ITER>
long long count(int n, ITER begin, ITER end) {
  if (n == 0) return 1;
  else if (begin == end || n < 0) return 0;
  else return
      // combinations which don't use *begin
    count(n, begin + 1, end) +
      // use one (more) *begin.
    count(n - *begin, begin, end);
}

// Same thing, but uses O(n) storage and runs in O(n*|c|) time, 
// where |c| is the length of the container. This implementation falls
// directly out of the recursive one above, but processes the items
// in the reverse order; each time through the outer loop computes
// the combinations (for all possible sums <= n) for sum prefix of
// the container.
template<typename ITER>
long long count1(int n, ITER begin, ITER end) {
  std::vector<long long> v(n + 1, 0);
  v[0] = 1;
  // Initial state of v: v[0] is 1; v[i] is 0 for 1 <= i <= n.
  // Corresponds to the termination condition of the recursion.

  auto vbegin = v.begin();
  auto vend = v.end();
  for (auto here = begin; here != end; ++here) {
    int a = *here;
    if (a > 0 && a <= n) {
      auto in = vbegin;
      auto out = vbegin + a;
      // *in is count(n - a, begin, here).
      // *out is count(n, begin, here - 1).
      do *out++ += *in++; while (out != vend);
    }
  } 
  return v[n];
}
于 2012-09-21T22:15:31.547 に答える
0

この問題を解決する Go のコードを次に示します。O(W / min(A)) 時間で実行されると思います。コメントは、それがどのように機能するかを確認するのに十分なはずです。重要な詳細は、 A の要素を複数回使用できることですが、その要素の使用を停止すると、二度と使用されなくなります。これにより、[1,2,1] や [1,1,2] などの二重カウントが回避されます。

package main

import (
  "fmt"
  "sort"
)

// This is just to keep track of how many times we hit ninjaHelper
var hits int = 0

// This is our way of indexing into our memo, so that we don't redo any
// calculations.
type memoPos struct {
  pos, sum int
}

func ninjaHelper(a []int, pos, sum, w int, memo map[memoPos]int64) int64 {
  // Count how many times we call this function.
  hits++

  // Check to see if we've already done this computation.
  if r, ok := memo[memoPos{pos, sum}]; ok {
    return r
  }

  // We got it, and we can't get more than one match this way, so return now.
  if sum == w {
    return 1
  }

  // Once we're over w we can't possibly succeed, so just bail out now.
  if sum > w {
    return 0
  }

  var ret int64 = 0
  // By only checking values at this position or later in the array we make
  // sure that we don't repeat ourselves.
  for i := pos; i < len(a); i++ {
    ret += ninjaHelper(a, i, sum+a[i], w, memo)
  }

  // Write down our answer in the memo so we don't have to do it later.
  memo[memoPos{pos, sum}] = ret
  return ret
}

func ninja(a []int, w int) int64 {
  // We reverse sort the array.  This doesn't change the complexity of
  // the algorithm, but by counting the larger numbers first we can hit our
  // target faster in a lot of cases, avoid a bit of work.
  sort.Ints(a)
  for i := 0; i < len(a)/2; i++ {
    a[i], a[len(a)-i-1] = a[len(a)-i-1], a[i]
  }
  return ninjaHelper(a, 0, 0, w, make(map[memoPos]int64))
}

func main() {
  a := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
  w := 1000
  fmt.Printf("%v, w=%d: %d\n", a, w, ninja(a, w))
  fmt.Printf("Hits: %v\n", hits)
}
于 2012-09-21T17:13:58.617 に答える