私は最近、動的プログラミングのカリキュラムでこの問題に直面しましたが、正直なところ、適切な状態を判断する方法がわかりません。
N (1 <= N <= 70) の段落とM (1 <= M <= N) の図が与えられます。各パラグラフiには、PL_i (1 <= PL_i <= 100) 行と最大 1 つの図への参照が必要です。各図は 1 回だけ参照されます (つまり、2 つの段落が同じ図を参照することはできず、各図にはそれを参照する段落があります)。各図にはPF_i (1 <= PF_i <= 100) 行が必要です。
タスクは、それらの図と段落を与えられた順序で紙に配布することです。1 枚の紙は最大でL行に収まります。大きすぎて 1 枚の紙に収まらない段落や図はありません。紙x_pに配置された段落xが図yを参照する場合、 yは紙x_p - 1またはx_pまたはx_p + 1のいずれかに配置する必要があります。
すべての図と段落を配布するために、割り当てる行 (およびページ) の最小数を見つける必要があります。どんな助けでも大歓迎です。前もって感謝します！
一般に、パラグラフPとフィギュアPのエーテル（P、F）の順序または（F、P）の順序を並べ替える必要があるという問題があります。
ドキュメントへの配置は（P1、F1）、（P2、F2）、（P3、F3）であり、各タプル（P、F）は任意の順序（P、F）または（F、P）であり、いくつかのFがあります。長さ0は、Fがないことを意味します。
問題は、各（P、F）ペアの順序を見つけることです。
最小数のペイジを見つけるための1つの解決策は、このルールを適用することです
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のときに終了に達したことがわかります。
あなたがしなければならないのは、ページ分割とデッドラインを念頭に置いてその特別な+記号を実装する関数を作成することです。
これにより、終了条件が0になるため、ページ数ではなく行数ではなく、最小のO（N）ソリューションが得られます。
行数を最小限に抑えたい場合は、終了条件を0ではなく別の条件に設定する二分法を使用できます。
O（N * log（L））ソリューション
編集
現在のPとFの間に他のPが存在する可能性があるため、（（F、P）、（P、F））の代わりにチェックする必要があります。空白ページ（N）もチェックするため、コンボは（（P、F））になります。 （P、N、F）、（F、P）、（F、N、P））。結論は、最終的にはより複雑なアルゴリズムになりますが、同じ複雑さになるということです。ポイントは、4つの順序のいずれかをチェックすると、最適なポジショニングを作成するための簡単な方法は1つだけであり、現在の状態（線）だけが少し複雑になるということです。
最適化できますが、それは機能するソリューションです:
public class 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;
}
現在のページ P の DP 状態として、行数でインデックス付けされた (サイズL * 2 の) 配列を使用できます。これは、ページ P+1 または (否定された) 行数から参照される図のためにページ P で予約されています。図は P+1 ページ、P ページから参照。
各配列要素は、次の 2 つの値で構成されます。
この配列を使用して、次のページ (P+1) の配列を計算します。配列 P の有効な要素ごとに、新しい段落 ( x +1、x +2、...) をページ P+1 に追加し、配列 P+1 の対応する要素を更新します。可能であれば、これらの段落で参照される図を P ページ、次に P+1 ページ、次に P+2 ページに配置します。xの値が小さい配列 P+1 の要素を大きい値で上書きします。
このアルゴリズムの時間計算量は O( L * N ) です: ページあたりの行数に段落数を掛けたものです。各ページの処理は O(ページあたりの行数 * ページあたりの平均段落数) であるためです。
最初は、再帰的なメソッドを作成することをお勧めします。
バリエーションから最適なものを選択してください。段落または図から始めてください。
すべてのステップで、可能なバリエーションから最適なものを選択します。ページブレークを追加し、次の図を追加し、次の段落を追加します。単純なステートマシンは、禁止されているバリアント（たとえば、2つのページブレークが連続している）を排除するのに役立ちますが、必須ではありません。
再帰的解法がチェックされるとき、DPに関するほとんどのアルゴリズムコースで説明されているように、それをトップダウンまたはボトムアップの動的計画法に変換できます。