Dynamic programming - determining the state

Question

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!

Answer 1

there is in general problem that you have to redorder paragraps P and Figures P ether (P,F) order or (F,P) ordering.

Placing in document is (P1,F1),(P2,F2),(P3,F3) where each tuple (P,F) can be of any order (P,F) or (F,P) and there are some F-s that has length 0 what means there is no F.

Problem is to find ordering for each (P,F) pair.

One solution for finding least number of Paiges is applying this rule

lines_total = MIN(lines(P,F),lines(F,P)) + remaining() //this is custom addition

Ok, there is lack of prototype of this function, but for C goes like

calc_spend_lines(pfpairs * pairs)

Where pfpaires is

typedef struct
{
   int P;
   int F;
} pfpaires;

And you know that you reached end when P is 0 for instance.

All you have to do, is to make function, that implements that special + sign having in mind page breaks and dead lines.

This gives O(N) solution, for minimum over number of pages but not number of lines, since your ending condition will be 0.

If you want to minimise over number of lines you can use bisection where you set ending condition to something else instead of 0 and that gives you

O(N*log(L)) solution

EDIT
Since there can be other P inbetween current P and F, one just have to check instead of ((F,P),(P,F)) also check for blank page (N) so combos are ((P,F)(P,N,F),(F,P),(F,N,P)). Conclusion is , that you end up more complicated algorithm, but same complexity. Point is that once you check one of 4 ordering, there is only one trivial way to make optimal positioning, just current state (lines) is bit complicated.