All You need to know about Subset Sum Problem

25/10/2019

Bài toán: Cho 1 multiset $S = \{a_1, a_2, …, a_n\}$, tìm 1 subset of $S$ thỏa điều kiện $P$.
Naive Solution: $\rightarrow O(2^n * n)$
Ta sinh tất cả các subset của $S$ $(O(2^n))$, sau đó duyệt qua từng subset $(O(n))$ để kiểm tra xem nó có thỏa điều kiện $P$ hay không.

Nó thực sự là 1 bài toán NP-Complete nên ta chỉ có thể giải trong thời gian exponential. Có cải tiến $O(n^\frac{n}{2})$, xem wiki

Khi mà bài toán trở nên cụ thể (ie: Tập giá trị nhỏ), ta có thể dùng DP Technique để giải trong thời gian đa thức. Chúng ta cùng tìm hiểu 1 số bài toán cụ thể của Subset Sum problem sau đây:

1. 0-1 Knapsack Problem

Bài toán:
Bạn có 1 balo (Knapsack) với sức chứa $W$ kilograms.
Có $n$ món đồ có trọng lượng $\{w_1, w_2, …, w_n\}$ và có giá trị tương ứng $\{v_1, v_2, …, v_n\}$.
Hãy tìm cách lấy các món đồ nào đó để bỏ vừa trong balo và đạt giá trị cao nhất.

Khi mà bài toán có tính lặp lại nhỏ hơn (recursion, suboptimal problem) và Overlap (hiển nhiên đến sau) thì đó là lúc ta dùng DP Technique.

Solution: (DP Technique)
Đặt $dp(n, W)$ là maximum value we can get from $n$ món đồ và với cái balo có capacity of $W$ kilograms. Thì:
$$ dp(n, W) = max\begin{cases}dp(n-1, W) & (not\ taken)\\ v[n] + dp(n-1, W - w[n]) & (taken)\end{cases}$$
Base case: (Vẽ bảng ra cho rõ)

• $dp(0, j) = 0\ \ \ \forall 0\leq j \leq W$
• $dp(i, 0) = 0\ \ \ \forall 1\leq i \leq n$

Implementation:

 1//top-down approach
 2int n, W, w[N], v[N];
 3int mem[N][W]; //memset(mem, -1, sizeof mem);
 4int dp(int n, int W){
 5    if (W <= 0 || n == 0) return 0;
 6    int &res(mem[n][W]);
 7    if (res != -1) return res;
 8    return res = max(dp(n-1, W), v[n]+dp(n-1, W - w[n]));
 9}
10
11//bottom-up approach
12int dp[N][W]; //full 0
13for(int i=1; i<=n; i++) {
14    for(int j=1; j<=W; j++) {
15        dp[i][j] = max(dp[i-1][j], v[i]+dp[i-1][j-w[i]});
16    }
17}

Complexity: $$\rightarrow O(nW)$$ Note: Guessing? Is the last element was taken or not? :v

2. Existence of a subset Equal to given Sum

Bài toán
Given a set of non-negative integers $S$, and a value $SUM$, determine if there is a subset of $S$ with sum equal to given $SUM$.

Solution (DP Technique)
Why DP? Giả sử ta đang ở trạng thái lơ lửng $i$ (đang duyệt tới phần tử thứ i (based 1)), nếu $i-1$ phần tử trước đó đã có thể construct a subset with sum $SUM$ thì tới đây chắc chắn có mà không cần đếm xỉa tới $a[i]$, nếu trước đó chưa có nhưng nó có subset with sum equal $SUM-a[i]$ thì giờ thêm $a[i]$ vào subset đó 100% perfect. Cảm quan như vậy dẫn đường cho DP.
$\rightarrow$ Recall: Những bài subset thường là tới phần tử $i$ ta dựa vào tất cả những cái subset đã cấu thành tử $i-1$ phần tử trước đó và thêm vào, + với nó đứng 1 mình (tương đương với thêm vào tập rỗng $i-1$ phần tử trước đó).

Đặt $dp(i, j)$ là có hay không subset of i phần tử đầu với sum bằng $j$.
Rõ ràng:
$$dp(i, j) = dp(i-1, j-a[i])\ |\ dp(i-1, j)$$ base case: $dp(i, 0) = true \ \ \ \forall 1\leq i\leq n$

Implementation

 1int dp[N][SUM]; //int ms bitwise or duoc
 2for(int i=0; i<=n; i++) dp[i][0] = true;
 3for(int i=1; i<=n; i++){
 4    for(int j=0; j<=SUM; j++){
 5        dp[i][j] = dp[i-1][j];
 6        if (j-a[i]>=0) dp[i][j] |= dp[i-1][j-a[i]];
 7    }
 8}
 9bool ans = dp[n][SUM];
10//Link Submission: https://practice.geeksforgeeks.org/problems/subset-sum-problem/0

$\rightarrow$ Bài toán có thể modify thành bài toán kiểm tra sự tồn tại của subset equal 0 với set gồm các phần tử không cần phải non-negative.

2.1. Parition Problem

Bài toán:
Cho 1 multiset of integers $S$, the task is divide it into $2$ set $S1$ and $S2$ such that the absolute difference between their sums is minimum.

$\rightarrow$ Thật ra đây chỉ là bài giống bài trên, ta check xem cái $sum$ nào có thể construct gần với $mid$ nhất là ok.
Solution
Dùng DP như trên, chỉ khác ở bước kết quả, ta duyệt từ mid về trước để tìm cái $dp[n][i] = true$ đầu tiên thôi.
Implementation

 1int n, a[N], sum = 0;
 2int all_sum;
 3for(int i=1; i<=n; i++) sum += [i];
 4all_sum = sum;
 5sum /= 2;
 6vector<vector<int>> dp(n+1, vector<int>(sum+1, 0));
 7for(int i=0; i<=n; i++) dp[i][0] = 1; //empty set
 8for(int i=1; i<=n; i++){
 9    for(int j=0; j<=sum; j++){
10        dp[i][j] = dp[i-1][j];
11        if (j-a[i]>=0) dp[i][j] |= dp[i-1][j-a[i]];
12    }
13}
14int ans;
15for(int i=sum; ; i--){
16    if (dp[n][i] == true){
17        ans = all_sum - i - i;
18        break;
19    }
20}
21cout << ans << endl;
22//Link submission: https://practice.geeksforgeeks.org/problems/minimum-sum-partition/0