查找低於或等於某個值的最大子序列

我在學習動態編程，並且在理解更復雜的問題時遇到了很多麻煩。當遇到問題時，我被教會找到一個遞歸算法，記憶遞歸算法，然後創建一個迭代的，自下而上的版本。幾乎在每一步我都有一個問題。就遞歸算法而言，我寫了不同的方法來執行遞歸算法，但只有一種方法通常適用於動態編程，而且我無法區分遞歸算法的哪些方面使記憶更容易。就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

查找低於或等於某個值的最大子序列

回答

相關問題