我最近在动态编程课程中遇到了这个问题，老实说，我不知道如何确定适当的状态。
你有N (1 <= N <= 70) 个段落和M (1 <= M <= N) 个数字。每个段落i需要PL_i (1 <= PL_i <= 100) 行并且最多引用一个图。每个图只引用一次（即，没有两个段落可以引用同一个图，并且每个图都有一个引用它的段落。）每个图都需要PF_i (1 <= PF_i <= 100) 行。
任务是按照给定的顺序将这些图形和段落分布在纸上，其中一张纸最多适合L行。没有段落或图形太大而不能放在一张纸上。如果放置在纸x_p上的段落x引用了图形y，则y必须放置在纸x_p - 1或x_p或x_p + 1上。
为了分配所有的图表和段落，我们必须找到要分配的最少行数（以及相应的页数）。任何帮助将不胜感激。提前致谢！
作为当前页面 P 的 DP 状态，您可以使用数组（大小为L * 2），按行数索引，在页面 P 上保留用于图形，从页面 P+1 引用或（取反的）行数，需要在第 P+1 页上的图，从第 P 页引用。
每个数组元素由两个值组成：
使用此数组计算下一页 (P+1) 的数组。对于数组 P 的每个有效元素，将新段落 ( x +1, x +2, ...) 添加到页面 P+1，更新数组 P+1 的对应元素。尽管可以，将这些段落引用的图形放在 P 页，然后放在 P+1 页，然后放在 P+2 页。用较高的值覆盖数组 P+1 中x值较低的元素。
该算法的时间复杂度为 O( L * N )：每页行数乘以段落数。因为处理每一页是 O(lines-per-page * average-paragraphs-per-page)。
通常存在的问题是您必须对段落 P 和图形 P 以太（P，F）顺序或（F，P）顺序进行重新排序。
放置在文档中的是 (P1,F1),(P2,F2),(P3,F3) 其中每个元组 (P,F) 可以是任意顺序 (P,F) 或 (F,P) 并且有一些 F长度为 0 表示没有 F。
问题是找到每个 (P,F) 对的排序。
找到最少 Paige 数的一种解决方案是应用此规则
lines_total = MIN(lines(P,F),lines(F,P)) + remaining() //this is custom addition
好的，这个函数缺少原型，但是对于 C 来说就像
calc_spend_lines(pfpairs * pairs)
pfpaires 在哪里
typedef struct
{
int P;
int F;
} pfpaires;
例如，当 P 为 0 时，你知道你已经结束了。
您所要做的就是制作函数，该函数实现了特殊的 + 符号，并考虑了分页符和死线。
这给出了 O(N) 解决方案，因为您的结束条件将是 0，所以对于最少的页数而不是行数。
如果您想最小化行数，您可以使用二分法，将结束条件设置为其他值而不是 0，这样您就可以
O(N*log(L)) 解
编辑
由于在当前 P 和 F 之间可能有其他 P，因此只需检查而不是 ((F,P),(P,F)) 还检查空白页 (N) 所以组合是 ((P,F) (P,N,F),(F,P),(F,N,P))。结论是，您最终会得到更复杂的算法，但复杂度相同。关键是，一旦您检查了 4 个排序之一，只有一种简单的方法可以进行最佳定位，只是当前状态（行）有点复杂。
可以优化，但它的工作解决方案：
公共类 ParagraphsAndFigures {
public static ArrayList<PageContent> generatePages(List<Paragraph> paragraphs, int L) {
ArrayList<PageContent> pages = new ArrayList<PageContent>();
for (int i = 0; i < paragraphs.size() * 2; i++) {
pages.add(new PageContent());
}
int page = 0;
for (Paragraph paragraph : paragraphs) {
do {
int cur = pages.get(page).linesReserved;
int next = pages.get(page + 1).linesReserved;
if (cur + paragraph.size < L) {
cur += paragraph.size;
if (paragraph.figure != null) {
if (pages.get(page + 1).hasPicture()) {
if (next + paragraph.figure.size < L) {
pages.get(page).texts.add(paragraph);
pages.get(page + 1).texts.add(paragraph.figure);
pages.get(page).linesReserved += paragraph.size;
pages.get(page + 1).linesReserved += paragraph.figure.size;
break; // next paragraph
} else {
page++;
continue;
}
}
if (pages.get(page).hasPicture()) {
if (cur + paragraph.figure.size < L) {
pages.get(page).texts.add(paragraph);
pages.get(page).texts.add(paragraph.figure);
pages.get(page).linesReserved += paragraph.size;
pages.get(page).linesReserved += paragraph.figure.size;
break; // next paragraph
} else {
if (next + paragraph.figure.size < L) {
pages.get(page).texts.add(paragraph);
pages.get(page + 1).texts.add(paragraph.figure);
pages.get(page).linesReserved += paragraph.size;
pages.get(page + 1).linesReserved += paragraph.figure.size;
break; // next paragraph
}
page++;
continue;
}
}
if (page != 0 && pages.get(page - 1).hasPicture()) {
int prev = pages.get(page - 1).linesReserved;
if (prev + paragraph.figure.size < L) {
pages.get(page).texts.add(paragraph);
pages.get(page - 1).texts.add(paragraph.figure);
pages.get(page).linesReserved += paragraph.size;
pages.get(page - 1).linesReserved += paragraph.figure.size;
break; // next paragraph
} else {
if (cur + paragraph.figure.size < L) {
pages.get(page).texts.add(paragraph);
pages.get(page).texts.add(paragraph.figure);
pages.get(page).linesReserved += paragraph.size;
pages.get(page).linesReserved += paragraph.figure.size;
break; // next paragraph
}
if (next + paragraph.figure.size < L) {
pages.get(page).texts.add(paragraph);
pages.get(page + 1).texts.add(paragraph.figure);
pages.get(page).linesReserved += paragraph.size;
pages.get(page + 1).linesReserved += paragraph.figure.size;
break; // next paragraph
}
page++;
}
}
if (page != 0) {
int prev = pages.get(page - 1).linesReserved;
if ( prev + paragraph.figure.size < L) {
pages.get(page).texts.add(paragraph);
pages.get(page - 1).texts.add(paragraph.figure);
pages.get(page).linesReserved += paragraph.size;
pages.get(page - 1).linesReserved += paragraph.figure.size;
break; // next paragraph
}
}
if (cur + paragraph.figure.size < L) {
pages.get(page).texts.add(paragraph);
pages.get(page).texts.add(paragraph.figure);
pages.get(page).linesReserved += paragraph.size;
pages.get(page).linesReserved += paragraph.figure.size;
break; // next paragraph
}
if (next + paragraph.figure.size < L) {
pages.get(page).texts.add(paragraph);
pages.get(page + 1).texts.add(paragraph.figure);
pages.get(page).linesReserved += paragraph.size;
pages.get(page + 1).linesReserved += paragraph.figure.size;
break; // next paragraph
}
page++;
}
}
page++;
} while (true);
}
return pages;
}
}
And tests:
public class ParagraphsAndFiguresTest {
@Test
public void pageGeneration1() throws Exception {
// given
ArrayList paragraphs = new ArrayList();
paragraphs.add(new Paragraph(20,21));
paragraphs.add(new Paragraph(22,23));
paragraphs.add(new Paragraph(24,25));
// when
ArrayList<PageContent> pageContents = ParagraphsAndFigures.generatePages(paragraphs, 50);
// then
assertThat(transformToList(pageContents), is(asList("20", "21", "p0" ,"22" ,"23", "p1" ,"24" ,"25", "p2")));
}
@Test
public void pageGeneration2() throws Exception {
// given
ArrayList<Paragraph> paragraphs = new ArrayList<Paragraph>();
paragraphs.add(new Paragraph(10,11));
paragraphs.add(new Paragraph(28,21));
paragraphs.add(new Paragraph(22,23));
// when
ArrayList<PageContent> pageContents = ParagraphsAndFigures.generatePages(paragraphs, 50);
// then
assertThat(transformToList(pageContents), is(asList("10", "11" ,"28", "p0" ,"21", "22" , "p1" ,"23", "p2")));
}
@Test
public void pageGeneration3() throws Exception {
// given
ArrayList<Paragraph> paragraphs = new ArrayList<Paragraph>();
paragraphs.add(new Paragraph(10,11));
paragraphs.add(new Paragraph(12,30));
paragraphs.add(new Paragraph(13,19));
// when
ArrayList<PageContent> pageContents = ParagraphsAndFigures.generatePages(paragraphs, 50);
// then
assertThat(transformToList(pageContents), is(asList("10", "11" ,"12", "13", "p0" ,"30", "19" , "p1" )));
}
@Test
public void pageGeneration4() throws Exception {
// given
ArrayList<Paragraph> paragraphs = new ArrayList<Paragraph>();
paragraphs.add(new Paragraph(10,11));
paragraphs.add(new Paragraph(30,12));
paragraphs.add(new Paragraph(13,16));
// when
ArrayList<PageContent> pageContents = ParagraphsAndFigures.generatePages(paragraphs, 50);
// then
assertThat(transformToList(pageContents), is(asList("10", "11" ,"12", "16", "p0" ,"30", "13" ,"p1" )));
}
@Test
public void pageGeneration5() throws Exception {
// given
ArrayList<Paragraph> paragraphs = new ArrayList<Paragraph>();
paragraphs.add(new Paragraph(31,32));
paragraphs.add(new Paragraph(17,21));
paragraphs.add(new Paragraph(30,35));
// when
ArrayList<PageContent> pageContents = ParagraphsAndFigures.generatePages(paragraphs, 50);
// then
assertThat(transformToList(pageContents), is(asList("31", "p0", "32", "17", "p1", "21", "p2", "30", "p3", "35", "p4")));
}
private List<String> transformToList(ArrayList<PageContent> pageContents) {
List<String> result = new ArrayList<String>();
for (int i = 0; i < pageContents.size(); i++) {
PageContent pageContent = pageContents.get(i);
if (!pageContent.texts.isEmpty()) {
for (Text text : pageContent.texts) {
result.add(String.valueOf(text.size));
}
result.add("p"+i);
}
}
return result;
}
}
And structures:
public class PageContent {
int linesReserved;
Collection texts = new ArrayList();
public boolean hasPicture() {
for (Text text : texts) {
if (text instanceof Figure) {
return true;
}
}
return false;
}
}
public class Text {
protected int size;
}
public class Figure extends Text{
}
public class Paragraph extends Text {
public Paragraph(int size, int fSIze) {
this.size = size;
this.figure = new Figure();
this.figure.size = fSIze;
}
Figure figure;
}
首先，我建议构建递归方法。
从变体中选择最佳：从段落或图形开始。
在每一步从可能的变体中选择最好的：添加分页符，添加下一个图，添加下一段。简单的状态机将有助于消除禁止的变体（例如，一行中的 2 个分页符），但这不是必需的。
当检查递归解决方案时，您可以将其转换为自顶向下或自底向上的动态规划，如大多数有关 DP 的算法课程中所述。