@navneet: good one.. In my above explanation, u could keep track of back pointers so that u may want to print the subset containing the sum..
On Jul 2, 11:54 am, Navneet Gupta <[email protected]> wrote: > 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 > > athttp://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.
