0

我的问题是，我需要计算有多少整数数组的组合总和为一个值W。`

让我们说：

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

我的算法只是找到从1到的所有长度组合W / minimum(array)，这等于，W因为最小值为 1。如果每个组合的总和等于 W，则检查每个组合，然后增加一个计数器N。

任何其他算法来解决这个问题？应该更快:)

更新： 好的，子集问题和背包问题都很好，但我的问题是数组的组合重复了元素，像这样：

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是需要的，并且生成的组合的顺序并不重要，因此与and1,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

这是解决此问题的 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 回答
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 回答