Wrote the code for same.
#include<iostream>
using namespace std;
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int main()
{
int n,k;
cout<<"\nEnter the count of numbers :";
cin>>n;
//Set of Elements
cout<<"\nEnter the elements :";
int *A;
A = new int[n];
for(int i = 0; i<n; i++)
cin>>A[i];
//Input Sum Value
cout<<"\nEnter the value of k :";
cin>>k;
//Matrix for holding boolean values for subproblems (max subproblems
upto nk)
int **M;
M = (int **)new int[n];
for(int i=0; i<n; i++)
M[i] = new int[k+1];
//Populate all the values to false
for(int i=0; i<n; i++)
for(int j=0; j<=k; j++)
M[i][j] = 0;
for(int i=0; i<n; i++)
M[i][0] = true;
for(int i=1; i<n; i++)
for(int j=0; j<=k; j++)
if(j-A[i]>=0)
{
M[i][j] = max(M[i-1][j], M[i-1][j-A[i]]);
}
if(M[n-1][k] == 1)
cout<<"\nPossible Subset present";
else
cout<<"\nPossible Subset not present";
cin.get();
return 0;
}
On Fri, Jun 24, 2011 at 11:42 PM, ross <[email protected]> wrote:
> This is the subset sum problem which is NP,.
>
> The DP is as follows,
>
> M[i,j] = 1 , if a subset of first i elements has a sum = j.
> else 0,
> The recurrence is,
> M[i,j] = max(M[i-1,j] , M[i-1,j-Ai]) where Ai is the ith element.
>
> You can maintain back pointers to keep track of previous elements so
> that
> the solution can be reconstructed from the DP.
>
> Once this matrix is populated till sum=k, Then, the column
> corresponding to sum=k, gives
> the answer. complexity o(nk).
>
>
>
> On Jun 20, 6:38 pm, Harshal <[email protected]> wrote:
>> The problem is NP. Complexity using DP will be O(nk), where n is number of
>> elements and k is required sum.
>>
>> S[0]=true; //choose no element
>> S[1...k] = false;
>> for each number i in your input
>> for s = k downto i
>> if ( S[s - i] == true )
>> S[s] = true;
>>
>> S[s] = true indicates a sum of i can be obtained from a subset of the set.
>> To get the elements, we can make S[s] contain the list of numbers that
>> contain the sum.
>> On Mon, Jun 20, 2011 at 6:53 PM, Navneet Gupta <[email protected]>wrote:
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> > Ideally, yes it can. Though i would be happy even if someone gives a
>> > good answer for non-negative values.
>>
>> > On Mon, Jun 20, 2011 at 6:28 PM, Akshata Sharma
>> > <[email protected]> wrote:
>> > > @Navneet: does the set contains negative elements also?
>>
>> > > On Mon, Jun 20, 2011 at 12:26 PM, pacific :-) <[email protected]>
>> > wrote:
>>
>> > >> @vaibhav : Please note that more than two numbers can sum upto k.
>>
>> > >> On Mon, Jun 20, 2011 at 12:21 PM, vaibhav shukla <
>> > [email protected]>
>> > >> wrote:
>>
>> > >>> sort the array using merge sort : order nlogn
>> > >>> take the first element,subtract it with 'k' , then search the result
>> > >>> using binary search in rest of the array : order nlogn
>> > >>> hence u get two elements which sum up to K in order nlogn
>>
>> > >>> On Mon, Jun 20, 2011 at 12:14 PM, Navneet Gupta <[email protected]
>>
>> > >>> wrote:
>>
>> > >>>> Right, in the worst case, complexity with be O(2^N).
>> > >>>> So what are the possible optimizations here? Would building
>> > pre-computed
>> > >>>> data structures with intermediate sum values help in finding such
>> > pairs in
>> > >>>> less complexity? I think then we can apply dynamic programming to find
>> > such
>> > >>>> pairs.
>>
>> > >>>> On Mon, Jun 20, 2011 at 12:09 PM, oppilas . <
>> > [email protected]>
>> > >>>> wrote:
>>
>> > >>>>> I think its a NP problem. The solution complexity can go up O(2^N) in
>> > >>>>> worst case.
>>
>> > >>>>> On Mon, Jun 20, 2011 at 11:55 AM, Navneet Gupta <
>> > [email protected]>
>> > >>>>> wrote:
>>
>> > >>>>>> Given a set of integers , find a set of numbers such that they sum
>> > to
>> > >>>>>> a given number k .
>> > >>>>>> Notice the set of numbers can have 2 or more than 2 numbers.
>>
>> > >>>>>> --Navneet
>>
>> > >>>>>> --
>> > >>>>>> You received this message because you are subscribed to the Google
>> > >>>>>> Groups "Algorithm Geeks" group.
>> > >>>>>> To post to this group, send email to [email protected].
>> > >>>>>> To unsubscribe from this group, send email to
>> > >>>>>> [email protected].
>> > >>>>>> For more options, visit this group at
>> > >>>>>>http://groups.google.com/group/algogeeks?hl=en.
>>
>> > >>>>> --
>> > >>>>> You received this message because you are subscribed to the Google
>> > >>>>> Groups "Algorithm Geeks" group.
>> > >>>>> To post to this group, send email to [email protected].
>> > >>>>> To unsubscribe from this group, send email to
>> > >>>>> [email protected].
>> > >>>>> For more options, visit this group at
>> > >>>>>http://groups.google.com/group/algogeeks?hl=en.
>>
>> > >>>> --
>> > >>>> --Navneet
>>
>> > >>>> --
>> > >>>> You received this message because you are subscribed to the Google
>> > >>>> Groups "Algorithm Geeks" group.
>> > >>>> To post to this group, send email to [email protected].
>> > >>>> To unsubscribe from this group, send email to
>> > >>>> [email protected].
>> > >>>> For more options, visit this group at
>> > >>>>http://groups.google.com/group/algogeeks?hl=en.
>>
>> > >>> --
>> > >>> best wishes!!
>> > >>> Vaibhav Shukla
>> > >>> DU-MCA
>>
>> > >>> --
>> > >>> You received this message because you are subscribed to the Google
>> > Groups
>> > >>> "Algorithm Geeks" group.
>> > >>> To post to this group, send email to [email protected].
>> > >>> To unsubscribe from this group, send email to
>> > >>> [email protected].
>> > >>> For more options, visit this group at
>> > >>>http://groups.google.com/group/algogeeks?hl=en.
>>
>> > >> --
>> > >> regards,
>> > >> chinna.
>>
>> > >> --
>> > >> You received this message because you are subscribed to the Google
>> > Groups
>> > >> "Algorithm Geeks" group.
>> > >> To post to this group, send email to [email protected].
>> > >> To unsubscribe from this group, send email to
>> > >> [email protected].
>> > >> For more options, visit this group at
>> > >>http://groups.google.com/group/algogeeks?hl=en.
>>
>> > > --
>> > > You received this message because you are subscribed to the Google Groups
>> > > "Algorithm Geeks" group.
>> > > To post to this group, send email to [email protected].
>> > > To unsubscribe from this group, send email to
>> > > [email protected].
>> > > For more options, visit this group at
>> > >http://groups.google.com/group/algogeeks?hl=en.
>>
>> > --
>> > --Navneet
>>
>> > --
>> > You received this message because you are subscribed to the Google Groups
>> > "Algorithm Geeks" group.
>> > To post to this group, send email to [email protected].
>> > To unsubscribe from this group, send email to
>> > [email protected].
>> > For more options, visit this group at
>> >http://groups.google.com/group/algogeeks?hl=en.
>>
>> --
>> Harshal Choudhary,
>> Final Year B.Tech CSE,
>> NIT Surathkal, Karnataka, India.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
--Navneet
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
