A dynamic programming problema on containers and product

Question

We have two production lines - product and container (two integer arrays product_list[N] and container_list[M]). If the volume of a container is equal or larger than that of a product, then we could put the product into that container.

We want to put as many products into containers as possible.

We can pick any initial position of products (any i in product_list array), and match each container one by one. We can't skip product but we can skip containers. No recurring of arrays i.e. product line won't go back if reach the end.

My solution is that, start from first product until last product (for i = 0; i < N), then match the container list from 1st to the last (for j = 0; j < M). For each starting point i, count the number of matched products (count_array[i]+1 if container_list[j] >= product_list[i]). Finally output the maximum of the count array.

I believe my algorithm isn't optimal, but I can't come up with a better way to do this problem in dynamic programming.

Any help will be appreciated! Thanks for everyone reading this problem!

Answer 1

Here is one approach, I could think of.

$T(x, y) = $ The maximum number of products which could be put into containers if we start at position $x$ in container line, whereas position $y$ in the product line.

If $size(C_x) >= size(P_y)$ we can either choose or skip the container. Else if the size of container is smaller, since we cannot skip the product, we would have to skip the container.

Hence, the recursion would be: \begin{equation} T[x, y]=\begin{cases} max(1 + T[x+1,\hspace{1mm} y+1], \hspace{2mm} T[x+1,\hspace{1mm} y]), & \text{if $size(C_x) >= size(P_y)$}.\\ T[x+1,\hspace{1mm}y], & \text{otherwise}. \end{cases} \end{equation}

Starting from the end of both the arrays, $$max(T[1,i]) \hspace{2mm}: \hspace{2mm} 1<=i<=n$$ should have the required result.

http://ideone.com/3dsrZu