0

我有一个相对复杂的问题，我需要一种算法来从一个总和为 X 的数组中找到所有可能的子数组，因此对于给定的数组：

{2,8,12,45,32,7,6,5}

假设我们需要总和为 20 的子数组，有些是：

{8,12} {2,7,6,5} {12,6,2}

但是会有如下组合：

{7,7,6} {5,5,5,5} {8,8,2,2}

我需要所有可能的金额。

我已经完成了一个解决方案，对所有可能性进行了蛮力检查，但是它需要很长时间（在某些情况下超过 30 分钟）才能完成，所以我确实需要一个更聪明的解决方案，我一直在努力解决几个问题现在的天。

4

1 回答 1

1

您的问题似乎表明重复数字的答案是可以接受的，并且您不想生成可以对总和进行排序的所有可能方式。我会以此为基础来回答。

我会在 C++ 中实现它。作为数据结构，我可能会使用这样的东西：

struct partial_sum {
  int min_last_summand;
  std::vector< std::pair<partial_sum*, int> > prefixes;
};

std::map<int, partial_sum*> m;

这里的核心部分是地图m。它将总和的值映射到有关如何获得它的一些信息。您将使用0映射到初始化它NULL。该prefixes成员将存储有关获得给定总和的所有可能方式的数据。每对的第一部分给出一个指针，指向除最后一个之外的所有被加数的信息，而第二部分给出最后一个成员。这为您提供了一种有向无环图，因为和可以是许多和的前缀，并且和可以有许多不同的前缀，但每个前缀和的值都小于当前和的值。

中央迭代步骤将从 中删除最小元素m，并生成所有可能的方式，您可以将输入集中的元素添加到刚刚删除的值。因此，您将检查地图是否需要为新总和插入新条目。对于现有的和新的条目，您在prefixes列表中创建一个新项目，将您刚刚从地图中删除的指针作为第一部分，并将您添加的最后一个总和作为第二部分。

我只会按加法的升序（或更确切地说是非降序）生成总和，以避免生成所有排列。为了使事情更容易，我会维护这些min_last_summand信息。它应该始终包含列表中对的所有第二个元素中的最小值prefixes。生成新总和时，您可以跳过最后一个总和小于前缀的最小最后一个总和的那些，因为这意味着一个总和小于其前一个总和。您还可以避免生成总值大于目标总和的总和。

打印结果时，您必须递归从目标总和可到达的 DAG 部分，并列出从那里到 root 的所有路径NULL。因此，在每个递归步骤中，您都会有一个指向当前部分总和的指针。如果该指针是NULL，则发出一个由零和数组成的总和。否则，您将遍历所有prefixes. 对于每个前缀，您递归生成所有可能的方式来编写该前缀，但min_last_summand前提是第一个元素的 不大于当前最后一个被加数，并且只有当第二个元素不大于将跟随它的被和数时. 这意味着您必须将以下 summand 作为参数传递给递归调用。总而言之，这避免了生成带有递减步骤的总和。

上面的方法假设您的程序将在一次运行后终止，因此您不必担心释放内存。如果这样做，您可能必须存储指向您创建的所有对象的指针，以便将它们全部释放。

于 2012-10-19T07:04:05.370 回答