1

I've recently faced this problem in a dynamic programming curriculum, and I honestly have no idea about how to determine the appropriate state.

You're given N (1 <= N <= 70) paragraphs and M (1 <= M <= N) figures. Each paragraph i requires PL_i (1 <= PL_i <= 100) lines and references at most one figure. Each figure is referenced exactly once (i.e., no two paragraphs can reference the same figure, and for each figure there's a paragraph that references it.) Each figure requires PF_i (1 <= PF_i <= 100) lines.

The task is to distribute those figures and paragraphs on paper in the order they're given, where one paper fits for L lines at most. No paragraph or figure is too large to fit on one paper. If a paragraph x placed on paper x_p references a figure y then y must be placed on either the paper x_p - 1 or x_p or x_p + 1.

We have to find the minimum number of lines (and thus pages) to allocate in order to distribute all the figures and paragraphs. Any help would be extremely appreciated. Thanks in advance!

1

1 Answer 1

1

Have a 2d matrix. Row is number of number of paragraphs you can fit, column is number of figures you can fit, cell value is the minimum number of lines possible. Cell[0,0] = 0. Cell[1,0] and Cell[0,1] can be calculated trivially. Cell[1,1] can be calculated by finding a minimum based on Cell[1,0] and Cell[0,1]. The bottom right cell is your answer. There's a step missing in this explanation related to "x_p - 1 or x_p or x_p + 1," but I think this is probably the right direction for using dynamic programming to solve this problem.

More detail:
You can calculate Cell[X,Y] by finding the most efficient way to reach it (i.e., check the minimum cost of reaching it from Cell[X-1,Y] and from Cell[X,Y-1]). In the case of a figure, the cost to jump one cell won't necessarily be equal to the number of lines in the figure, since you may be forced to move the figure to the next page. What this explanation is missing is how to cut off cells where the figures are to far behind or in front of the paragraphs.

1
  • Thanks for you answer! I don't see how your state can be used to form an efficient solution -- can you please elaborate more? Hugely appreciated. Thanks in advance.
    – Chris
    Jul 5, 2012 at 8:22

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.