The Sum-of-Subsets Problem(부분집합의 합 구하기)

Basic Concept

---

In the Sum-of-Subsets problem, there are n positive integers (weights) $w_i$ and a positive integer W. The goal is to find all subsets of the integers that sum to W. As mentioned earlier, we usually state our problems so as to find all solutions.

 

👉 부분집합의 합을 구하는 문제는 n개의 양의 정수(무게) $w_i$와 양의 정수 $W$가 주어졌을 때, 합이 $W$가 되는 정수의 부분집합을 모두 찾는 것이다. n-Queens 문제처럼 모든 해답을 찾도록 알고리즘을 구현할 것이다.

 

Example Suppose that n = 5, W = 21, and

$$ w_1=5 \quad w_2=6 \quad w_3=10 \quad w_4=11 \quad w_5=16. $$

because

$$ \begin{align}w_1 + w_2 + w_3 &= 5 + 6 + 10 = 21, \notag{}\\ w_1 + w_5 &= 5 + 16 = 21, \notag{}\\w_3 + w_4 &= 10 + 11 = 21, \notag{}\end{align}$$

the solutions are {$ w_1$, $w_2$, $w_3$}, {$w_1$, $w_5$}, and {$w_3$, $w_4$}.

 

Example Suppose that n = 4, W = 13, and
$$ w_1=3 \quad w_2=4 \quad w_3=5 \quad w_4=6. $$
becasue

$$ w_1 + w_2 + w_4  = 3 + 4 + 6 = 13$$

the solutions are {$ w_1, w_2, w_4$}.

 

The only solution is found at the node shaded in color. The nonpromising nodes are marked with crosses. The nodes containing 12, 8, and 9 are nonpromising because adding the next weight (6) would make the value of weight exceed W. The nodes containing 7, 3, 4, and 0 are nonpromising because there is not enough total weight remaining to bring the value of weight up to W.

 

👉 각 노드에는 그 노드까지의 총 합이 적혀 있다. 가장 왼쪽 잎노드인 12는 3 + 4 + 5의 결과이다. 부모노드를 기준으로 왼쪽 자식노드는 $w_i$를 포함시킨다는 뜻이며 오른쪽 노드는 $w_i$를 배제한다는 의미이다.

위의 상태공간트리에서 유망하지 않은 자식노드들은 X로 표시된다. 12, 8, 9를 포함하는 노드들은 다음 무게인 6을 추가하면 weight의 값이 W를 초과하기 때문에 유망하지 않다. 7, 3, 4, 0을 포함하는 노드들은 남은 무게를 더했을때의 총합이 W까지 가기에는 충분하지 않으므로 유망하지 않다.

 

 

The Backtracking Algorithm for the Sum-of-Subsets Problem

---

Algorithm Design

If we sort the weights in nondecreasing order before doing the search, there are obvious signs that a node is nonpromising.

👉 부분합 문제의 상태공간트리 전체를 깊이우선탐색하는 것은 비효율적이다. $w_1~ w_n$을 오름차순으로 정렬하면 가지치기를 판단할 수 있는 분명한 증거들이 있다.

 

If the weights are sorted in this manner, then $w_i$+1 is the lightest weight remaining when we are at the $i$th level. Let weight be the sum of the weights that have been included up to a node at level $i$. If the $w_{i+1}$ would bring the value of weight above W, then so would any other weight following it. Therefore, unless weight equals W (which means that there is a solution at the node), a node at the $i$th level is nonpromising if $weight + w_{i+1} < W$. The algorithm uses an array include. It sets include[i] to “YES” if w[i] is to be included and to “NO” if it is not.

• $weight$: the sum of the weights that have been included up to a node at level $i$

$$ weight + w_{i+1} > W \text{: a node is nonpromising.} $$

• $total$: the total weight of the remaining weights

$$weight + total < W \text{: a node is nonpromising.}$$

 

👉 $weight$는 $i$레벨에 있는 노드까지 포함된 무게의 합이다. weight에 $w_i$+1을 더한 결과가 $W$를 초과한다면 그 이후에 어떤 다른 무게도 $W$를 넘길 것이다. 즉, $w_i+1$부터는 유망하지 않으므로 그 자식 노드들은 탐색대상에서 제외한다.

$total$은 남아있는 아이템의 총 무게이다. $total$에 $weight$를 더해서 $W$보다 작다면, 그 노드 아래로 확장을 해도 $W$와 같아질 수 없다. 따라서 이 경우도 유망하지 않으므로 가지치기를 통해 탐색대상에서 제외한다.

$w_i$ 의 포함여부는 include[i] 배열을 통해 관리한다. include[i]는 $w_i$를 포함하면 “YES”, 그렇지 않으면 “NO” 값을 가진다.

 

When the sum of the weights included up to a node equals W , there is a solution at that node. Therefore, we cannot get another solution by including more items. This means that if

$$W = weight$$

we should print the solution and backtrack.

 

👉 W = weight 등식이 성립하면 해답을 출력하고 백트래킹한다.

 

Pseudo Code

• The Backtracking Algorithm for the Sum-of-Subsets Problem

void sum_of_subsets(index i, int weight, int total)
{
  if (promising(i))
    if (weight == W)
      cout << include[1] through include[i];
    else {
      include[i+1] = "yes"; // Include w[i+1]
      sum_of_subsets(i+1, weight + w[i+1], total - w[i+1]);
      include[i+1] = "no";  // Do not include w[i+1]
      sum_of_subsets(i+1, weight, total - w[i+1]);
    }
}

bool promising(index i)
{
  return (weight + total >= W) && (weight == W || weight + w[i+1] <= W);
}

 

Soruce Code

• sumofsubs.h

// File: sumofsubs.h
#include <cstring>
using namespace std; // for string

namespace algorithms
{
  void sum_of_subsets(int i, int weight, int total, int W, int* w, string* include);
  // Problem: Given n positive integers (weights) and a positive integer W,
  // determine all combinations of the integers that sum to W.
  // Inputs: positive integer n, sorted (nondecreasing order) array of positive
  // integers w indexed from 1 to n, and a positive integer W.
  // Outputs: all combinations of the integers that sum to W.

  bool promising(int i, int weight, int total, int W, int* w);

  template <typename Item>
  Item* get_vector_space(const int n)
  // Prostcondition: Return the array containing n spaces
  {
    Item* v = new Item[n];
    return (v-1); // offset the pointer
  }
}

 

• sumofsubs.cpp

// File: sumofsubs.cpp
#include <iostream>
#include <iomanip> // Provides setw
#include "sumofsubs.h"

namespace algorithms
{
  void sum_of_subsets(int i, int weight, int total, int W, int* w, string* include)
  {
    if (promising(i, weight, total, W, w))
    {
      if (weight == W)
      {
        for (int j = 1; j <= i; ++j)
          cout << setw(3) << "w" << j << ": " << include[j] << setw(3);
        cout << endl;
      }
      else
      {
        include[i + 1] = "YES"; // Include w[i+1]
        sum_of_subsets(i + 1, weight + w[i + 1], total - w[i + 1], W, w, include);
        include[i + 1] = "NO "; // Do not include w[i+1]
        sum_of_subsets(i + 1, weight, total - w[i + 1], W, w, include);
      }
    }
  }

  bool promising(int i, int weight, int total, int W, int *w)
  {
    return (weight + total >= W) && (weight == W || weight + w[i + 1] <= W);
  }
}

 

• sumofsubstest.cpp

// File: sumofsubstest.cpp
#include <iostream>
#include <cstdlib> // Provides EXIT_SUCCESS
#include "sumofsubs.h"
using namespace algorithms;

int main( )
{
  const int N = 5;
  const int W = 21;
  int* w = get_vector_space<int>(N);
  int total = 0;
  string* include = get_vector_space<string>(N);

  w[1] = 5;
  w[2] = 6;
  w[3] = 10;
  w[4] = 11;
  w[5] = 16;

  // total 초기값 계산
  for (int i = 1; i <= 5; ++i)
  	total += w[i];

  sum_of_subsets(0, 0, total, W, w, include);

  delete [ ] (w + 1);
  delete [ ] (include + 1);

  return EXIT_SUCCESS;
}

 

 

Time Complexity Analysis

---

Worst-Case Time Complexity

$\displaystyle O(n) = 1 + 2 + 2^2 + 2^3 + … + 2^n = 2^{n+1} - 1 \in \Theta(2^n)$

 

As stressed before, even though the worst case is exponential, the algorithm can be efficient for many large instances.

 

👉 $w_i$를 포함시키느냐 그렇지 않느냐의 두 가지 선택이므로 상태공간트리 내 전체 노드의 수는 최대 $2^{n+1}-1$개가 된다. 최악의 경우 시간복잡도가 지수시간이지만, 가지치기를 통해 상태노드의 수를 줄일 수 있기 때문에 알고리즘의 효율은 더 좋을 수 있다.

n-Queens 문제와 마찬가지로 유망한 노드의 수를 정확히 구하기 위한 방법은 실제 알고리즘을 수행 후 구축된 상태공간트리의 노드 갯수를 세어 보는 수 밖에 없다. 또한 몬테 카를로 알고리즘을 이용해 시간복잡도를 추정할 수 있다.