algorithm - C/C++/ java /C# : help parsing numbers

Question

我有一个真正的问题(这不是作业，你可以查看我的个人资料)。我需要解析格式不受我控制的数据。

数据看起来像这样:

6,852:6,100,752

因此首先是一个最多由 9 位数字组成的数字，后跟一个冒号。

那么我肯定知道，在冒号之后:

• 至少有一个有效的数字组合加起来等于该列前的数字
• 我确切地知道冒号前的数字加起来有多少(在这种情况下是两个，但最多可以达到十个)

在这种情况下，6852 是 6100 + 752。

我的问题:我需要找到这些数字(在本例中为 6100 + 752)。

不幸的是，在我被迫解析的数据中，数字之间的分隔符(逗号)也是数字本身内部使用的分隔符(6100 写为 6,100)。

再一次:不幸的格式化不在我的控制之下，再一次，这不是家庭作业。

我需要解决最多 10 个需要相加的数字。

这是一个三个数字相加为 6855 的示例:

6,855:360,6,175,320

我担心在某些情况下会有两种可能的不同解决方案。 但是如果我得到一个“在大多数情况下”有效的解决方案就足够了。

在 C 风格的括号语言中，您通常如何解决此类问题？

Answer 1

好吧，我将从蛮力方法开始，然后应用一些启发式方法来修剪搜索空间。只需用逗号分隔右侧的列表，并遍历所有可能的方法将它们分组为 n 个项(其中 n 是解决方案中的项数)。您可以使用以下两个规则来跳过无效的可能性。

(1) 您知道任何 1 位或 2 位数字的组合都必须开始一个术语。

(2) 你知道在你的逗号分隔列表中没有候选词可以大于左边的总数。 (这还会告诉您任何候选术语可以拥有的最大数字组数。)