aroup's blog

Dynamic Programming Help
By aroup, 10 years ago, In English

I am currently learning to solve dynamic programming problems, and I found this problem.

Ferry Loading

I am trying recursive approach,but I am finding it hard to determine the ending of recursive branches.

I am saving dp[index][right_length][left_length].

Their values are obtained from the maximum of int p1,p2,p3.

p1=recurse(index+1,right,left) ; // we can move to the next car
p2=1+recurse(index+1,right+arr[index],left); // we take it and add to the right
p3=1+recurse(index+1,right,left+arr[index]); // we take it and add to the left

I am wondering what the base cases might be.Any help can is appreciated.Thanks in advance.

Tags #dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The length of the ferry is up to 100 metres which is 10000 centimetres. You can't create an array [200][10000][10000].

→ Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

bool dp[index][right_length]

dp[a][b] = can we pack first a cars that sum of lengths of cars on the right will be equal to b?

→ Reply