@ankush: i told one approach above , but may i want clear . i am not saying this is the best approach to do so but it is one naive soln i came up with.
so find all possible combination for each invoice and save it in some data structure. now start from 1st invoice and select 1st invoice combination say for invoice 80 = 50 + 30 now search in next invoice(210) combination , if there is any combination for this invoice which does not include 50 and 30 if yes there is one say 210= 10 + 10 +20 + 70 + 100 , we have a hit and do similar with other invoice . every time you move fwd make sure that you should search for combination which does not include any of those bill used in prev finding. if no, then we know that there is no point of moving fwd , so select another combination from prev invoice in this case its 80 and follow same as above. On Mon, Mar 26, 2012 at 5:56 PM, <ankush.bago...@gmail.com> wrote: > ** > You can use dp to find subsets . But how is dp used for the overall > probkem > Sent from BlackBerry® on Airtel > ------------------------------ > *From: * atul anand <atul.87fri...@gmail.com> > *Sender: * algogeeks@googlegroups.com > *Date: *Mon, 26 Mar 2012 16:52:08 +0530 > *To: *<algogeeks@googlegroups.com> > *ReplyTo: * algogeeks@googlegroups.com > *Subject: *Re: [algogeeks] Google Question Invoice -bills > > @umer : dp approach is given in above post. > > On Mon, Mar 26, 2012 at 4:11 PM, Umer Farooq <the.um...@gmail.com> wrote: > >> Well, they have specified in the question that "you are dealing with >> big-data sets". So, recursion won't be a good option I guess. >> >> Can we solve it with dynamic programming technique? >> >> >> On Mon, Mar 26, 2012 at 2:24 PM, atul anand <atul.87fri...@gmail.com>wrote: >> >>> one way to do it , is say first combination for invoice 80= 50 + 30 >>> now remove 80 and 30 from the input bills while finding combination from >>> 210 , check if it is possible >>> if yes , we got one solution >>> not select another invoice combination 80= 50 + 10 + 20 >>> now dont consider these values while find combination for 210. >>> >>> i guess there can be better way to solve this...... >>> >>> >>> On Mon, Mar 26, 2012 at 2:36 PM, Ankush Bagotra < >>> ankush.bago...@gmail.com> wrote: >>> >>>> Ok now you have combination of each invoice . What is the approach to >>>> take mutual exclusive combinations for so that sum of all bills equals >>>> sum of all invoices >>>> >>>> On Mon, Mar 26, 2012 at 2:16 PM, atul anand <atul.87fri...@gmail.com> >>>> wrote: >>>> > it is similar to sum-subset problem following recurrance will solve >>>> this >>>> > problem , you need to run algo for each invoice to find all >>>> combination >>>> > >>>> > F(n,k) = F(n,k-1) or F(n - a[k], k-1) >>>> > base case :F(0,k)=1 for k>=0 >>>> > F(n,0)= 0 for n>0. >>>> > >>>> > On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra < >>>> ankush.bago...@gmail.com> >>>> > wrote: >>>> >> >>>> >> There are 210 Invoices and 1700 bills – these bills add up to these >>>> >> invoices >>>> >> >>>> >> The association between bills and invoices is lost . The only way to >>>> >> match them is by adding them up to correct amounts that are equal to >>>> >> the invoices. >>>> >> >>>> >> For Example : there were 2 invoices for 80, 210 and you have bills >>>> >> for these 50, 10 ,10, 30 , 20, 70, 100 values >>>> >> >>>> >> One of the possible solution is : >>>> >> >>>> >> 80=50 + 30 >>>> >> 210= 10 + 10 +20 + 70 + 100 >>>> >> >>>> >> Other possible solution is >>>> >> >>>> >> 80=50 + 10 + 20 >>>> >> 210= 30 +20 + 70 + 100 >>>> >> >>>> >> >>>> >> What is the best possible way to get all solutions ? Remember you are >>>> >> dealing with big datasets >>>> >> >>>> >> -Kabir >>>> >> >>>> >> -- >>>> >> You received this message because you are subscribed to the Google >>>> Groups >>>> >> "Algorithm Geeks" group. >>>> >> To post to this group, send email to algogeeks@googlegroups.com. >>>> >> To unsubscribe from this group, send email to >>>> >> algogeeks+unsubscr...@googlegroups.com. >>>> >> 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 algogeeks@googlegroups.com. >>>> > To unsubscribe from this group, send email to >>>> > algogeeks+unsubscr...@googlegroups.com. >>>> > 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 algogeeks@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com. >>>> 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 algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Umer >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
