如何找到與列表中最大號碼相同的所有號碼集合

Question

如何查找所有號碼集合的添加與列表中的最大號碼相同。 例如： 輸入數組= {2,3,4,9-} 輸出= {2,3,4} {9}

Answer 1

你所要求實際上是SubsetSum problem.First找出最大值然後應用動態規劃來生成其總和爲列表的最大值的一組數字。

爲了實現動態編程針對你在Java中使用遞歸和HashTable的問題。 HashTable通過存儲計算來提高性能。

Answer 2

它實際上是一個子集總和問題。我們在哪裏檢查一個子集是否存在一個特定的總和。

這裏說的特定數額=最大元素

所以先找到列表的最大元素，並把它等於總結

子集和問題 這是一個動態規劃算法，它告訴，如果有子集，其總和等於給定的數字。

下面的示例代碼是explained and detailed here

#include <cstdio> 
#include <vector> 
using namespace std; 

bool** dp; 

void display(const vector<int>& v) { 
    for (int i = 0; i < v.size(); ++i) 
     printf("%d ", v[i]); 
    printf("\n"); 
} 

void output(const vector<int>& a, int i, int sum, vector<int>& p) { 
    if (i == 0 && sum != 0 && dp[0][sum]) { 
     p.push_back(a[i]); 
     display(p); 
     return; 
    } 
    if (i == 0 && sum == 0) { 
     display(p); 
     return; 
    } 
    if (dp[i - 1][sum]) { 
     vector<int> b = p; 
     output(a, i - 1, sum, b); 
    } 
    if (sum >= a[i] && dp[i - 1][sum - a[i]]) { 
     p.push_back(a[i]); 
     output(a, i - 1, sum - a[i], p); 
    } 
} 

void find(const vector<int>& a, int sum) { 
    if (a.size() == 0 || sum < 0) return; 
    dp = new bool*[a.size()]; 
    for (int i = 0; i < a.size(); ++i) { 
     dp[i] = new bool[sum + 1]; 
     dp[i][0] = true; 
    } 
    for (int i = 1; i < sum + 1; ++i) 
     dp[0][i] = (a[0] == i) ? true : false; 
    for (int i = 1; i < a.size(); ++i) 
     for (int j = 0; j < sum + 1; ++j) 
      dp[i][j] = (a[i] <= j) ? dp[i - 1][j] || dp[i - 1][j - a[i]] : dp[i - 1][j]; 
    if (!dp[a.size() - 1][sum]) { 
     printf("There are no subsets with sum %d\n", sum); 
     return; 
    } 
    vector<int> p; 
    output(a, a.size()-2, sum, p); 
} 

int main() { 
    vector<int> a = {1,2,3,4,5,6,10}; 
    int max = 10; 
    find(a, max); 
    return 0; 
} 

輸出

4 3 2 1 
5 3 2 
5 4 1 
6 3 1 
6 4 

所以，現在我們有一組和該組我們都子集，其總和等於列表的max_element。 實際上，我們需要開始動態編程，以在排序之後找到子集，因此上面示例中提供的輸入是排序列表。

在O（2^n）時間內實際上是窮舉搜索結果，因此我們需要使用動態規劃和上述方法來改進它。