the DP is not clear, can you give example on how this DP would work for n
invoices and k bills?
Why is F(0,k) = 1?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Mar 26, 2012 at 2:16 PM, atul anand atul.87fri...@gmail.com wrote:
it is
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
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 n0.
On Mon, Mar 26, 2012 at 1:34 PM, Ankush
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
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
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
@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
@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
*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
