1

我正在学习动态编程，但在理解更复杂的问题时遇到了很多麻烦。当给定一个问题时，我被教导要找到一个递归算法，记住递归算法，然后创建一个迭代的、自下而上的版本。几乎每一步我都有一个问题。在递归算法方面，我编写了不同的方法来执行递归算法，但只有一种方法通常最适合用于动态编程，我无法区分递归算法的哪些方面使记忆更容易。在记忆方面，我不明白哪些值用于索引。为了转换为自下而上的版本，我无法确定填充数组/双精度数组的顺序。

这就是我的理解：-应该可以将主要问题拆分为子问题

就提到的问题而言，我提出了一个递归算法，它具有以下重要的代码行：

int optionOne = values[i] + find(values, i+1, limit - values[i]);
int optionTwo = find(values, i+1, limit);

如果我不清楚或者这不是正确的质量保证网站，请告诉我。

编辑：

示例：给定数组 x：[4,5,6,9,11] 和最大值 m：20

x 中小于或等于 m 的最大子序列为 [4,5,11] 为 4+5+11 = 20

4

1 回答 1

1

我认为这个问题是 NP 难的，这意味着除非 P = NP，否则没有多项式时间算法可以解决这个问题。

从子集和问题到这个问题有一个简单的简化。在子集和中，给定一组 n 个数字和一个目标数字 k，并想确定这些数字中是否有一个子集加起来正好为 k。您可以使用求解器为您的问题求解子集和，如下所示：创建集合中的数字数组并找到总和小于或等于 k ​​的最大子序列。如果加起来正好为 k，则该集合有一个加起来为 k 的子集。否则，它不会。

这种减少需要多项式时间，因此因为子集和是 NP 难的，所以您的问题也是 NP 难的。因此，我怀疑是否存在多项式时间算法。

也就是说 - 有一个用于子集和的伪多项式时间算法，在 Wikipedia 上有描述。该算法在两个变量中使用 DP，并且不是严格的多项式时间，但它可能适用于您的情况。

希望这可以帮助！

于 2013-10-13T19:09:20.780 回答