我最近在动态规划类(class)中遇到了这个问题，老实说我不知道如何确定适当的状态。
你有 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 必须放在纸上 < strong>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) 并且有是一些长度为 0 的 F-s，这意味着没有 F。
问题是找到每个 (P,F) 对的顺序。
找到最少数量的 Paiges 的一种解决方案是应用此规则
lines_total = MIN(lines(P,F),lines(F,P)) + remaining() //this is custom addition
好的，这个函数缺少原型(prototype)，但是对于 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 个排序中的一个，只有一种简单的方法可以进行最佳定位，只有当前状态(行)有点复杂。
关于algorithm - 动态规划——确定状态，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11273181/