Atul, I think that your approach will work, although it may take a huge amount of time. One way to potentially make it faster is to select the invoices with the smallest number of combinations first. If you first select all of the invoices with exactly one possible combination, this will prevent you from wasting a lot of time considering combinations for other invoices which require those bills. After assigning all of the invoices with exactly one possible combination, you can clear out all combinations for the other invoices which use any of the assigned bills. That might result in more invoices with exactly one possible combination, but it will almost certainly narrow down the options significantly for the rest of the problem. This approach doesn't ensure a faster solution. I could come up with a diabolical input set which would defeat it. But in most cases it should speed things up a lot. Don
On Mar 26, 11:32 pm, atul anand <atul.87fri...@gmail.com> wrote: > @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.- Hide quoted text - > > - Show quoted text - -- 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.
