11856 - Ferry Loading V

All about problems in Volume 118. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

11856 - Ferry Loading V

Post by Angeh » Tue Oct 05, 2010 5:55 am

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 ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm

Re: 11856 - Ferry Loading V

Post by Leonid » Wed Oct 06, 2010 1:17 am

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.

New poster
Posts: 17
Joined: Mon May 18, 2009 10:00 pm

Re: 11856 - Ferry Loading V

Post by LucasSchm » Sat Oct 01, 2011 11:40 pm

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)?

Post Reply

Return to “Volume 118 (11800-11899)”