I am not able to figure out where is the DP first property of Overlapping subproblem fits in Subset Sum Problem. However, I understand the Optimal Substructure part.While doing the recursive solution of Including and excluding the element where are the problems getting overlapped?
Is it like since it is an NP problem so not having two properties of DP.
The Link to problem is http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
Can someone please help me in understanding this.
-
I would recommend you not to care about these two properties at all. They are not necessary neither to understand and code a dynamic programming solution nor to prove it.kraskevich– kraskevich2015-01-25 16:54:39 +00:00Commented Jan 25, 2015 at 16:54
-
@ILoveCoding So u mean the above without these two properties also we can find a DP solution? nad do u see any Overlapping Problem in the recursive solution of Subset Sum?Art– Art2015-01-25 17:01:50 +00:00Commented Jan 25, 2015 at 17:01
-
Nope, I'm trying to say there is no need to use a notion of these two properties(in my opinion, they do not help to solve problems). You can prove the correctness of this solution and analyse its time complexity without them.kraskevich– kraskevich2015-01-25 17:05:00 +00:00Commented Jan 25, 2015 at 17:05
-
1Ok...then how will i come to know that DP can be applied in this particular problem if I dont see the above two properties?Art– Art2015-01-25 17:06:57 +00:00Commented Jan 25, 2015 at 17:06
-
It is possible to prove the correctness of this solution using mathematical induction.kraskevich– kraskevich2015-01-25 17:13:42 +00:00Commented Jan 25, 2015 at 17:13
Add a comment
|
1 Answer
Let's call the entire set of numbers S = {s[1], ...., s[n]}, the target value k, and write f(X, t) = 1 if there is a subset of X that sums to t, and 0 otherwise. So the answer we want to calculate is f(S, k).
You will get overlapping subproblems whenever two different subsets of numbers have the same sum, and that sum is less than the target k. In detail, suppose there is a subset SI = {s[i_1], ..., s[i_p]} and a different subset SJ = {s[j_1], ..., s[j_q]}, such that sum(SI) = sum(SJ) < k. Suppose w.l.o.g. that the indices are all in order (i.e. a < b implies i_a < i_b and j_a < j_b), and i_1 <= j_1 (if it doesn't, just swap SI and SJ). Then the subproblem f({s[1], ..., s[m-1]}, k-sum(SI)) will arise for (at least) two different paths through the call tree: after starting at f(S, k) (i.e. the root) and choosing to include all numbers in SI and no other numbers with indices >= i_1; and after starting at f(S, k) and choosing to include all numbers in SJ and no other numbers with indices >= j_1, and then choosing to also exclude the next j_1 - i_1 numbers.
Worked Example
Suppose S = {3, 4, 5, 6, 11} and k = 14. Then by excluding the 11 and including the 5 and the 6, we arrive at the subproblem f({3, 4}, 3) (which will have the solution 1) -- this corresponds to choosing SI = {5, 6} and i_1 = 3. Alternatively, by including the 11 and then excluding the 5 and the 6, we again arrive at the subproblem f({3, 4}, 3) -- this corresponds to choosing SJ = {11} and j_1 = 5.
answered Jan 25, 2015 at 17:54
j_random_hacker
51.6k10 gold badges109 silver badges176 bronze badges
7 Comments
Surbhi Jain
But it isnt always necesary that there would be overlapping subproblem, right? It would only happen whenever two different subsets of numbers have the same sum, and that sum is less than the target k, as you mentioned in your answer, right? @j_random_hacker and Raghav. Also could you pls explain the optimal substructure property for this question. Thanks
j_random_hacker
@SurbhiJain: If your first question is, "Are there problem instances for which no subproblem is ever encountered more than once?" then the answer is yes: in particular, whenever there are no two subsets that give the same sum (for example, when S is {1, 2, 4, 8, 16, 32} then there is exactly 1 way to make every number between 0 and 63 inclusive). A nice way to think about it is: Draw an n-by-k grid of vertices, where the vertex at (i, j) corresponds to the subproblem ({s[1], ..., s[i], j), which I'll abbreviate as (i, j). Now for each such vertex (i, j), draw two incoming arrows: one ...
j_random_hacker
... from (i-1, j), and one from (i-1, j-s[i]): each arrow represents a subproblem that we need to solve in order to solve the subproblem (i, j). Now think about this: A subproblem is reused iff there is more than one outgoing arrow from its vertex. In fact there can be at most 2 outgoing arrows from a vertex (i, j): One horizontal, to (i+1, j), and one diagonal, to (i+1, j+s[i+1]). The former exists whenever there is a path from (i+1, j) to (n, k), or equivalently whenever there is a subset of {s[i+2], ..., s[n]} that sums to k-j: this subset contributes the "vertical" movement. ...
j_random_hacker
... The latter exists whenever there is a path from (i+1, j+s[i+1]) to (n, k), or equivalently whenever there is a subset of {s[i+2], ..., s[n]} that sums to k-(j+s[i+1]): notice that we can add s[i+1] to this set to get a second, necessarily different, subset of S that sums to k-j. So if both outgoing edges from (i, j) exist then there are at least 2 subsets of S that sum to the same value, namely k-j.
j_random_hacker
In those cases where there are no overlapping subproblems, the DP provides no improvement over a plain recursive solution. But it's no worse than plain recursion in those cases, and can be exponentially faster on the remaining cases.
|