7

考虑您有几种日期模式 P1 - Pn。

其中一些很简单，例如 P1 - 所有星期一，P2 - 所有星期二；其他更复杂，如 P4 - 所有工作日等。

对于自定义日期数组（V1，V2），我必须创建最短的结果字符串，如图所示：

多模式匹配

对于任何数组，我们必须创建表示数组中日期的字符串。最简单的方法是创建像 1.5.2013, 2.5.2013, 3.5.2013 ... 这样的字符串，但结果字符串会很长。

使用几个预定义的模式，我们可以创建更短的结果字符串。

对于结果字符串，我使用以下规则：

单个日期格式：DD.MM.YYYY （10 个字符）
枚举（日期和模式）：逗号和空格（2 个字符）
日期间隔：DD.MM.YYYY-DD.MM.YYYY （21 个字符）
模式名称的间隔: Px-Py (5 个字符)
特殊词: except (6 个字符)

结果字符串示例：

  • V1 使用 P4 模式：

    P4 除了 01.05.2013-03.05.2013、09.05.2013、10.05.2013、16.05.2013、17.05.2013 （80 个字符）

  • V1 使用 Pn 模式：

    Pn 06.05.2013-08.05.2013、13.05.2013-15.05.2013、20.05.2013-24.05.2013、27.05.2013-31.05.2013 （94 个字符）

  • V1 使用最佳模式匹配：

    P1-P3 01.05.2013-19.05.2013，P4 20.05.2013-31.05.2013 （54 个字符）

主要目标是创建最短的结果字符串。据我了解，我们可以通过找到最佳匹配模式/模式来实现这一点。

目前我正在尝试适应背包问题和最长公共子序列问题，但我不确定这是否是正确的方向。

我会很感激任何想法。

更新

感谢Jan Dvorak对我的问题的简短描述：

目标是使用预定义的字典（P1..Pn 以及所有间隔和单个日期）来描述 V，其中交集、并集和减法都允许，并且每个操作和原子都有预定义的成本（结果字符串中的字符数）。

4

2 回答 2

1

经过长时间的搜索，我们终于找到了非常接近我们想要的解决方案。

http://www.fpz.unizg.hr/traffic/index.php/PROMTT/article/view/1287

感谢大家的参与。

于 2013-09-26T08:55:10.690 回答
0

这只是一个建议，但如果你想要一个非常短的字符串来表示日期数组，你可以用完全不同的方式解决这个问题，这种方式非常简单有效。

让 1 代表“选定”的一天，让 0 代表“未选定”的一天，然后你可以构造一个二进制数来表示一个月中的自定义日期数组，例如，对于 V1 的情况，你可以生成这个二进制数：

V1 = 0000011100001110000111110011111

所以第一个 0 表示日期 1.5.2013 是“未选择”，下一个 0 表示日期 2.5.2013 是“未选择”，等等。如果将此数字分成 8 位组（以字节为单位除二进制数）然后你可以创建这个字节数组：

V1(starting in May 1, 2013) = 00000111 - 00001110 - 00011111 - 00111110  (4 bytes)

使用此方法，您仅使用 4 个字节来表示 V1，如果您知道 V1 从 1.5.2013 开始，这是您需要的唯一信息，因此您还需要存储初始日期，以便您可以表示月份和年份仅使用 3 个字节，因此例如 2013 年 5 月的日期可以这样表示：

5 月 = 第 5 个月，所以二进制中的 5 是 101

二进制的 2013 是 11111011101 所以使用 3 个字节可以表示 2013 年 5 月，如下所示：

0000101 00000111 11011101
[  5  ] [     2013      ]

所以你可以将 V1 表示为

V1= 0000101 - 00000111 - 11011101  00000111 - 00001110 - 00011111 - 00111110
    [Month]   [     Year        ]  [      V1 custom array of dates         ]

所以 V1 可以完全用 7 个字节来表示！！

如果您需要一个字符串而不是字节数组，那么您可以将此字节数组转换为 Base64 字符串，以便 V1 可以表示为字符串

V1 in Base64 is Cg+6Dhw+Pg== (using just 12 characters!!)

在 V2 的情况下：

V2 = 0000101 - 00000111 - 11011101  11111111 - 11111111 - 11111111 - 11101110
     [Month]   [     Year        ]  [      V2 custom array of dates         ]

V2 in Base64 is Cg+7////bg== (using just 12 characters again!!)

通过这种方法，您知道月份自定义日期信息数组可以用 7 个字节（如果使用基本 64 字符串，则为 12 个字符）表示。

要在一年中存储自定义数组信息，您只需要：开始月份和年份的 3 个字节，加上 365/8 = 45.625（四舍五入为 46 个字节），即 49 个字节！全年，以 64 为基数的最大长度为 69 个字符！！！

这很容易实现，易于在代码中维护，比复杂的模式匹配算法更好，这对我来说是一个很好的解决方案。我希望这个建议符合您的要求。

于 2013-07-11T17:33:38.430 回答