knapsack problem and set sum problem

http://en.wikipedia.org/wiki/Subset_sum

NP complete, pseudo-polynomial

The trick is: O(nW) looks like a polynomial time, but it is not, it is pseudo-polynomial. Time complexity measures the time that an algorithm takes as function of the length in bits of its input. The dynamic programming solution is indeed linear in the value of W but exponential in the length of W - and that's what matters.




inline bool set_sum(vector<int> input,int S)
{
sort(input.begin(),input.end());
int neg=0,pos=0;
for(vector<int>::iterator j=input.begin();j<input.end();j++)
{
if(*j<0)neg+=-*j;
else pos+=*j;
}
vector<vector<bool>> table;
int input_num=input.size();
table.resize(input_num+1);
int sum_range=pos+neg+1;
for(int i=0;i<=input_num;i++)
{
table[i].resize(sum_range);
if(i==0)
fill(table[i].begin(),table[i].end(),false);
}
for(int i=1;i<=input_num;i++)
{
for(int j=0;j<sum_range;j++)
{
int cur_sum=j-neg;
if(input[i-1]==cur_sum)
table[i][j]=true;
else if(table[i-1][j]==true)
table[i][j]=true;
else if(j-input[i-1]>=0 && j-input[i-1]<sum_range && table[i-1][j-input[i-1]])
table[i][j]=true;
}
}
return S+neg>=0 && S+neg<sum_range && table[input_num][S+neg];
}