Saturday, February 25, 2012

My Dynamic Programming Study: Subset sum problem

This problem is NP-complete.

The problem is this: given a set of integers, is there a non-empty subset whose sum is zero? 

For example, given the set x[]={ −7, −3, −2, -4, 8, 5, 6 }, the answer is yes because the subset { −4, −2, 6} sums to zero. 

Solution

DP Array: 
COLUMN :  -7-3-2-4 <= sum <= 8+5+6   = -16<=x<=19

ROW : { −7, −3, −2, ,-4, 8, 5, 6 }

N is number of elements.
D is the range (max-min) of the elements.
M is also the number of elements
n is index of testing element.
m is number of element used.
d is the testing sum.

Method 1

(Need Many Memory)
            long long dp[D+2][N+1][M+2];
            forr(n,N+1)
            forr(d,D+2)
            forr(m,M+2)
            dp[d][n][m]=0;
            
            dp[0][0][0]=1;

            forr(n,N)
            forr(m,M+1)
            forr(d,D)
            {
                if(dp[d][n][m]>0)
                {
                     dp[d+v[n]][n+1][m+1]+=dp[d][n][m];
                     dp[d][n+1][m]+=dp[d][n][m];
                }
            }
            cout<<dp[0][N][M]<<endl;

dp[d][n][m] just ca be 0 or 1.

Method 2

Initial:
DP[?][?]=0

Forward: j++
if(i==0 and DP[i][j]==0) or DP[i][j]>0)
- DP[i + x[j] ][j+1]=DP[i][j]+1
- DP[      i     ][j+1]=DP[i][j]

*** DP[i][j] can be any number > 0.

Result:
After j reaches x.size(), if DP[0][z.size()]>0 ==> return 'yes'
and DP[0][z.size()]= number of element in this subset.

No comments:

Post a Comment