0

Consider the following problem:

We have a ferry of length L. This ferry is used to transport vehicles between two shores of a river. The ferry has two lanes in which vehicles can be accommodated. Each vehicle has a length l_i. Vehicles in each lane can be accommodated such that they do not exceed the ferries' length. Given a queue of vehicles with length l_1, l_2, ..., l_n and a ferry of length L, find the maximum number of vehicles that can be accommodated.

Keep in mind that the vehicles can only enter the ferry according to their position in the queue. For example, if the vehicles in the queue have lengths 700, 600, with the larger vehicle in the front, and the space remaining in the lanes is 0, 400, you cannot load the shorter car instead of the longer one.

I was able to solve this problem using a recurrence relation. Let solve(L1, L2, l_i, l_i+1, ..., l_n) return the maximum number of vehicles with lengths l_i, l_i+1, ..., l_n that can be accommodated in a ferry with lengths L1, L2 remaining in its two lanes.

function solve(L1, L2, l_i, l_i+1, ..., l_n) {
    if (L1 - l_i > 0 and L2 - l_i > 0) {
       return 1 + max(solve(L1 - l_i, L2, l_i+1, ..., l_n), solve(L1, L2 - l_i, l_i+1, ..., l_n))
    } else if (L1 - l_i > 0) {
       return 1 + solve(L1 - l_i, L2, l_i+1, ..., l_n)
    } else if (L2 - l_i > 0) {
       return 1 + solve(L1, L2 - l_i, l_i+1, ..., l_n)
    } else {
       return 0
    }

}

Basically this algorithm computes the best way to place the vehicles in the ferry and in each recurrence, it subtracts the length of the current vehicle in the queue from the length of the both lanes and passes this to itself, and computes the maximum of both strategies.

As you can see, the recursive calls build up quite quickly, and the program isn't very efficient. How can I implement the same algorithm using a dynamic programming fashion?

EDIT: The constraints are, L is between 1 and 10,000 and the length of each car is between 100 and 3000.

3 Answers 3

1

Compute all possible ferry configurations given that you've accepted i cars. To process car i+1, the set of new configurations are the configurations from the previous step with the new car in one lane or the other (where possible).

A single configuration can be the length of one of the lanes (since after processing i cars, you'll know that the sum of the lengths of the two lanes is l1+l2+...+l_i.

So, the table you can keep can be a set of lengths. Or if you want a "table" then you can use an array of true/false values and update (carefully) in place, which is the approach taken in this code.

def solve(L, car_lengths):
    confs = [True] + [False] * L
    S = 0
    for i, c in enumerate(car_lengths):
        S += c
        for j in xrange(L, -1, -1):
            if confs[j]:
                if S - j > L:
                    confs[j] = False
                if j + c <= L and S - j - c <= L:
                    confs[j + c] = True
        if not any(confs):
            return i


print solve(9, (5, 2, 3, 4, 5, 5, 3, 4, 8))

The code is slightly tricksy because of the in-place updating: if confs[j] is 1, then that means it's possible to have a configuration up to the previous car with j cars in the first lane. Then if you add the new car (of length c), possible configurations are j again (adding the car to the second lane), and j+c (adding the car to the first lane). Since we already have conf[j] set, the code tests if the car can't be added to the second lane and clears conf[j] in that case.

Here's the less tricky code using the same approach but with a set.

def solve(L, car_lengths):
    confs = set([0])
    S = 0
    for i, c in enumerate(car_lengths):
        S += c
        confs |= set(j + c for j in confs)
        confs = set(j for j in confs if j <= L and S - j <= L)
        if not confs:
            return i


print solve(9, (5, 2, 3, 4, 5, 5, 3, 4, 8))
1

Usually in DP you would create an array of all possible states as done in the answer Pham. As per the OP's remark, this is not feasible in this situation. Therefore, it might be better to keep a set of possible states up till the current car.

Let's create the state class (I do this in Java, hope that's fine). I want to keep it concise, so I don't use getters, just public fields.

class State {
    public int lane1;
    public int lane2;        

    public State(int lane1, int lane2) {
        this.lane1 = lane1;
        this.lane2 = lane2;
    }        

    public boolean equals(Object o) {
        if (o instanceof State) {
            State other = (State) o;
            return lane1 == other.lane1 && lane2 == other.lane2;
        } else {
            return false;
        }            
    }

    public int hashCode() {
        return 31 * lane1 + lane2;
    }
}

The equals and hashcode implementation are needed because I want to put State objects in a hashset and we want value equivalence rather than reference equivalence.

With these states you can just loop over the cars. When considering car i, we need to know all possible states up to car i-1, add car i to both lanes and store both resulting states (if they are feasible). In code:

public int findMaxCars(int L, int[] len) {        
    Set<State> previousStates = new HashSet<>();

    // the only possible state when there are no cars on the ferry:
    // both lanes have L remaining space
    previousStates.add(new State(L, L));

    for (int i = 0; i < len.length; i++) {
        Set<State> nextStates = new HashSet<>();

        for (State s : previousStates) {
            if (s.lane1 - len[i] >= 0) // can fit car i in lane1
                nextStates.add(new State(s.lane1 - len[i], s.lane2));
            if (s.lane2 - len[i] >= 0) // can fit car i in lane2
                nextStates.add(new State(s.lane1, s.lane2 - len[i]));
        }

        if (nextStates.isEmpty()) {
            // we couldn't fit car i anywhere, so the answer is: at most i cars
            return i;
        } else {
            previousStates = nextStates;
        }
    }
    // finished the loop, so all cars fit
    return len.length;
}
0

For your solution, observe that only one value is referring at a time, we can simply modify the function into

function solve(int L1,int L2, index, int [] length){//index : what is the current index in the array length we are referring to
}

Which will do the same thing. So we can easily come up with a DP state : DP[L1][L2][index]

Another thing is you can either choose to take into account the current index value or move on to next index by doing something like this

if(DP[L1][L2][index] != -1){//Need to initialize the DP table first
    return DP[L1][L2][index];
}
int max = 0;
if(L1 >= length[index]){
    max = 1 + solve(L1 - length[index],L2,index + 1, length);
}
if(L2 >= length[index]){
    max = 1 + max(max,solve(L1 ,L2 - length[index],index + 1, length));
}
max = max(max,solve(L1,L2,index + 1, length);

Last observation is order of L1 and L2 is not important, so it can be replace by min, max, (min value between L1 and L2, max value between L1 and L2)which help to reduce the number of step for the DP.

3
  • Ok. So if the length of the ferry is something like 5000 and the cars are 2500, 3000, 1000, 1000, 1500, 700, 800, this program will make a 5000*5000*7 3d array and compute values in that. Am I right? That would be pretty inefficient as we will be computing a lot of cases we don't need. Is there some way to reduce the size of the array?
    – Gerard
    Jan 16, 2014 at 15:33
  • @Gerard you should provide that constraint in the first place my friend. Never see them in your post.Give a DP solution without knowing about its constraint is never a good idea :)
    – Pham Trung
    Jan 16, 2014 at 16:00
  • @Gerard if array length is small , you can even consider bit-mask technique (7 in your case), the best thing is provide the link to the problem here :)
    – Pham Trung
    Jan 16, 2014 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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