Page 1 of 1
11856 - Ferry Loading V
Posted: Tue Oct 05, 2010 5:55 am
by Angeh
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 ...
Re: 11856 - Ferry Loading V
Posted: Wed Oct 06, 2010 1:17 am
by Leonid
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
Posted: Sat Oct 01, 2011 11:40 pm
by LucasSchm
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)?