动态编程 - 确定状态

Question

我最近在动态编程课程中遇到了这个问题,老实说,我不知道如何确定合适的状态.

你得到N(1 <= N <= 70)段和M(1 <= M <= N)个数字.每个段落我需要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上.

我们必须找到要分配的最小行数(以及页面),以便分发所有的数字和段落.任何帮助将非常感激.提前致谢!

Answer 1

通常存在的问题是您必须重新排序段落 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 个排序之一，就只有一种简单的方法来进行最佳定位，只是当前状态（线）有点复杂。