Could some body give some Hints how to solve this in Time ??
i Use Knapsack algorithm to find the nearest match to Sum/2 ....
Edit : solved it ...
11856 - Ferry Loading V
Moderator: Board moderators
11856 - Ferry Loading V
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)
Beliefs are not facts, believe what you need to believe;)
Re: 11856 - Ferry Loading V
The very important detail given in problem description is that the difference should be 2%. Think about how to convert the double range into integer range and then use DP on integers.
Re: 11856 - Ferry Loading V
Spoiler ahead...
I got that i have to normalize to solve this problem, but why does that work? Because i could have a large number (as 100.00) and so small numbers (0.0000001) that depending on how i normalize, the small numbers would be 0 and so my DP wouldn't work properly. Does it have to do with the fact that there is an answer within 1% and so that would guarantee by some way that such discrepancy with the numbers isn't possible (or if it happens, as i am looking for an answer within 2% that wouldn't be a problem)?
I got that i have to normalize to solve this problem, but why does that work? Because i could have a large number (as 100.00) and so small numbers (0.0000001) that depending on how i normalize, the small numbers would be 0 and so my DP wouldn't work properly. Does it have to do with the fact that there is an answer within 1% and so that would guarantee by some way that such discrepancy with the numbers isn't possible (or if it happens, as i am looking for an answer within 2% that wouldn't be a problem)?