Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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!

share|improve this question

migrated from codegolf.stackexchange.com Jul 2 '12 at 14:19

This question came from our site for programming puzzle enthusiasts and code golfers.

1  
sounds like a knapsack problem –  gnat Jul 2 '12 at 17:13

1 Answer 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.

share|improve this answer
    
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 '12 at 8:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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