subset sum problem
---------------------
A subset sum problem is a NP-complete problem. For more information visit http://en.wikipedia.org/wiki/Subset_sum_problem
However if we have knowledge about the data, we can use various optimizations such that the problem can be solved in polynomial time.
One such technique is presented below.
Given an array, we wish to count how many ways we can get a particular sum.
Let an array A[]= { a1, a2, ...an }. How many ways can we get a particular sum S.
also 0<=ai<=MAX.
Here i will describe a O(n*MAX) algorithm to solve it.
int T[MAX]; //T[i] stores how many ways we can get a sum = i.
int subset_sum(int A[] , int n, int S)
{
int prev_max=0;
T[0]=1; //we can get a sum of 0 in 1 way.
for( int i=0; i < n; i++ )
{
for(int j = prev_max ; j >= 0; j--)
if (T[j])
{
T[j+A[i]] += T[j];
prev_max = max( prev_max , j+A[i] );
}
}
return T[S];
}
Pretty simple. isn't it? :)
There are some things to note here.
Why do we run the second for loop from back?
->if we ran the loop from the front (ie from j to prev_max) then following thing will happen.
suppose for some value of j we have T[j]=non-zero number. thus we update at T[j+A[i]].
later when j becomes j+A[i], T[j+A[i]] is again non-zero from previous update. thus we update at T[j+A[i]+A[i]].
ie. we will end up using the same number A[i] more than once. this is not allowed.
How large can MAX or n be?
-> That depends on 2 things. How much memory can you allocate? and What is the speed of your system?
Standard Online judge like SPOJ, Codechef are pretty slow and allow memory allocation up to 10^8 bytes.
They run a plain for loop of 10^8 in a little more than 1 second.
So for the problem to be solved using this algorithm n*MAX ~ 10^8 or less.
Do let me know if you have any questions.
kindly check first FOR , sth is missing thr.
ReplyDeletecan you please write a running cpp code, i tried to run it but its giving runtime errors as its trying to access A out of bounds. Meanwhile have a look at bottom up:
ReplyDeleteint sum=S; // value to attain.
int cache[101];
vector given; // contains possible array elements.
int forloopers(){
memset(cache, -1, sizeof(cache));
cache[0]=1;
for(int i=0; i<=sum+1; i++) if(cache[i] != -1) {
for(int j=0; j<given.size() ; j++){
if(cache[i+given[j]] != -1)
cache[i+given[j]] += cache[i];
else cache[i+given[j]] = cache[i];
}
}
return cache[sum];
}
sorry there was a typo, A[j] should be A[i]
ReplyDeleteBet-it n' Tread and Bet-it n' Bet-it n' Tread and Bet-it
ReplyDeleteThe bet-it titanium dog teeth implants n' Tread and Bet-it titanium wedding band n' Tread and Bet-it n' titanium aura quartz Tread and Bet-it N' Tread are both designed edc titanium to meet ecm titanium the demands of the punter, as well as the
z283b9hjswd376 g-spot dildos,sex toys,fantasy toys,Clitoral Vibrators,penis pumps,wholesale sex toys,sex chair,japanese sex dolls,dildo d508r9dbbfj712
ReplyDelete