CODEWITHSUNDEEP
algorithmmathsumfractions
Manuel
Manuel

Reputation: 247

Approximate with sum of Fractions

Suppose the result of adding fractions a/b and c/d is (a + c)/(b + d). Similarly the result of adding 3 fractions a/b, c/d, e/f is (a + c + e)/(b + d + f), and so on. I have the following problem I could not solve.

Given an array A with n fractions a1/b1, a2/b2, ...., an/bn, a number k< n, and a fraction c/d. I need to test if it is possible to take exactly k indexes {i1,i2,...,ik} such a way the sum of A[i1]+A[i2]+...+A[ik] >= c/d. If this is possible print the indexes.

For example: If you have the fractions 1/4, 300/600, 400/400, k=2 and c/d = 400/400 Then the answer is NO. On the other hand, if c/d =400/404 then the answer is 1 and 3 because 1/4+400/400 = 401/404 >= 400/404.

Thanks!

Upvotes: 0

Views: 730

Answers (2)

Abhishek Patel
Abhishek Patel

Reputation: 814

This looks like an variation on knapsack problem. Try to maximize the sum of k fractions ( take k items to maximize value ) and see if that exceeds c/d.

Also when calculating the value, use (a+b)/(c+d) and so on rather than summing up their individual values.

Upvotes: 0

gnagar1996
gnagar1996

Reputation: 36

Notice that if 0 <= a/b <= c/d, then (a + c)/(b + d) <= c/d. So, all you need to do is go through the whole array looking for the maximum fraction. This is a linear time operation as it avoids the bottleneck of sorting the whole array.

Here is the proof of the statement. Assume there exist 2 positive rational numbers a/b, c/d such that a/b <= c/d. Notice then, ad <= bc, which would mean that ad + cd <= bc + cd. This is equivalent to saying that (a + c)d <= c(b + d), which implies (a + c)/(b + d) <= c/d. Because of this, your subset sum (as you have defined it) is bounded by the maximum positive fraction in your array. So, all you need to do is find the maximum fraction in your array (call it maxP) and return max(maxP, 0), assuming an empty subset is allowed.

Upvotes: 1

Related Questions