5

I have the following problem to solve:

Given a ferry with length d and a list of n cars conataining their length we must load the cars on the ferry in an order in which they appear in the list on 2 different lanes (each one having length d). Write a program that given length d and the list of cars outputs maximal number of cars that can be loaded on the ferry.

It's quite easy to do in O(2^cars) with backtracking - we load car on the left and try all the possibilities then, we save maximum and load car on the right and do the same saving max again.

But I have a feeling this can be reduced to polynomial time with dynamic programming. How to tell whether my gut feeling is true?

  • 1
  • 1
  • 2
    Sounds like a variation of the Knapsack problem – Dan Pichelman Jan 20 '15 at 21:14
  • 1
    Your original question title did not match your actual question, I took the freedom to correct this. If you think I got it wrong, please undo my edit (but if that's the case, please consider to edit your question to avoid further misunderstandings). – Doc Brown Jan 20 '15 at 21:46
  • Maybe this title is more appropriate to what I wanted to know - I generally have problems with finding DP subproblems and I wanted someone to show me how it's generally done using this problem. I'm already familiar with "DP theory", it's when I need to apply it to a specific problem then I have a hard time... – qiubit Jan 20 '15 at 22:03
4
+50

A possible approach is the following.

I am going to make the following assumptions. Let me know if either of them is actually incorrect. As soon as we encounter a car that can be added in neither of the lanes, then we stop adding cars to the ferry (it is not allowed to skip a big car to add a smaller car that comes latter in the list). I am going to make the assumption that the sum of the length of all cars is below 2d. If it is not the case, this can easily be enforced in a preprocessing step. I am also going to consider that d is an integer value, as well as all car sizes.

What we are now going to do is solve a 0/1 knapsack problem to find if a set of car can fit in both lanes.

Here the size of the knapsack is d (it is actually a lane), the size of the items are the size of the cars and the value associated with the items are the size of the cars (ie, we want to fill one lane as much as possible). To solve this 0/1 knapsack problem you can use the DP algorithm outlined on the following wikipedia webpage: http://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem (I am just going to reproduce it here so that the answer stands even if the wikipedia page would disappear):

Let us call s1, the size of car 1, s2 the size of car2, and so on (we are going to consider that we have n cars).

Define m[i,s] to be the maximum value that can be attained with a total size used less than or equal to s using cars up to i (first i cars).

We can define m[i,s] recursively as follows: m[i,s]=m[i-1,s] if si > s\, (the new car is longer than the current size limit) m[i,s]=max(m[i-1,s],\,m[i-1,s-si]+si) if si less or equal than s.

The solution can then be found by calculating m[n,d].

let us call s, the sum of the length of the cars in the solution from the knapsack problem. If the sum of all the cars length - s is less or equal than d, then all the cars considered for solving the knapsack problems can fit in the ferry (one lane being all those selected to be part of the knapsack solution, the other lane being the rest). If the sum of the length of the rest of the cars is more than d, then all the cars cannot fit in the ferry. Remove the last car from the list of the cars, and solve again the knapsack problem. Do this until the sum of the length of the not selected cars is below d.

The complexity of the DP algorithm to solve the knapsack problem is O(nd) and it needs to be solved at most n times -> complexity O(n^2d)

Here is a sketch of the solution in python:

def solveKnapsack(cars, lengthOfLane):
  m = [[0] * (lengthOfLane+1)]
  for s in cars:
    m.append([])
    for j in range(lengthOfLane+1):
      if s <= j:
        m[-1].append(max(m[-2][j],m[-2][j-s]+s))
      else:
        m[-1].append(m[-2][j])
  return max(m[-1])

def solveTwoLanes(cars, lengthOfLane):
  maxOneLane = solveKnapsack(cars, lengthOfLane)
  if sum(cars) - maxOneLane <= lengthOfLane:
    return len(cars)
  else:
    return solveTwoLanes(cars[:-1], lengthOfLane)


def main():
  # small example that should output 2.
  print solveTwoLanes([3,3,3,1],5)

if  __name__ =='__main__':main()
  • just curious is this working i tried in compiler i got syntax error near print solveTwoLanes([3,3,3,1],5) i can upvote you if you fix it. – user2733436 Mar 24 '15 at 16:11
  • hello, it works but I used python 2.7 syntax, your error let me think that you used python 3.x. Replacing print solveTwoLanes([3,3,3,1],5) by print(solveTwoLanes([3,3,3,1],5)) should do the trick – Renaud M. Mar 26 '15 at 7:03
  • @RenaudM. Great explanation. – bornfree Apr 24 '17 at 20:33
0

This is a multiple knapsack problem. Solving with Meet-in-the-middle algorithms, it takes O(2^(n/2)) for each "lane".

partition the set {1...n} into two sets A and B of approximately equal size
compute the weights and values of all subsets of each set for each subset of A

find the subset of B of greatest value such that the combined weight is less than W
keep track of the greatest combined value seen so far

More details here: http://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-middle

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.