查找低于或等于某个值的最大子序列

我在学习动态编程，并且在理解更复杂的问题时遇到了很多麻烦。当遇到问题时，我被教会找到一个递归算法，记忆递归算法，然后创建一个迭代的，自下而上的版本。几乎在每一步我都有一个问题。就递归算法而言，我写了不同的方法来执行递归算法，但只有一种方法通常适用于动态编程，而且我无法区分递归算法的哪些方面使记忆更容易。就memoization而言，我不明白哪些值用于指数。为了转换为自下而上的版本，我无法确定填充阵列/双数组的顺序。查找低于或等于某个值的最大子序列

这是我的理解： - 它应该是可以分割的主要问题子问题

中提到的问题来看，我想出了一个递归算法有代码的这些重要品系：

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

如果我不清楚或这不是正确的qa网站，请告诉我。

编辑：

实例：假设数组x：[4,5,6,9,11]和max值m：20

x中最大特亚或等于m。将[4 ，5,11] as 4 + 5 + 11 = 20

来源

2013-10-13 John

如果你举一个例子，最好给我们展示一下你的意思是“最大子序列低于一定值”。 – Shashank

我认为你所描述的问题是一个0-1背包问题，其中值相等。动态规划解决方案在这里给出.http：//en.wikipedia.org/wiki/Knapsack_problem –

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

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

这种减少需要多项式时间，因为子集和是NP难，你的问题也是NP难。因此，我怀疑有多项式时间算法。

这就是说 - 有一个subset-sum的pseudopolynomial-time算法，它是described on Wikipedia。该算法在两个变量中使用DP，并不是严格的多项式时间，但它可能适用于您的情况。

希望这会有所帮助！

来源

2013-10-13 19:09:20 templatetypedef

查找低于或等于某个值的最大子序列

回答

相关问题