리스트에서 최대 숫자와 같은 숫자의 모든 콜렉션을 찾는 방법

Question

리스트에서 최대 숫자와 동일한 숫자의 모든 콜렉션을 찾는 방법. 예를 들어 : 입력 배열 = {2,3,4,9-} 출력 = {2,3,4}는 {9}

Answer 1

는 당신이 요구하는 것은 실제로 SubsetSum problem.First이 최대 값을 찾을 수 있습니다 동적 프로그래밍을 적용하여 합계가 목록의 최대 값 인 숫자 집합을 생성합니다.

구현하려면 동적 재 프로그래밍을 사용하여 Java 재귀 및 HashTable 문제를 해결하십시오. HashTable은 계산을 저장하여 성능을 향상시킵니다.

Answer 2

실제로는 부분 집합 합계 문제입니다. 특정 합계에 대해 부분 집합이 존재하는지 확인하는 곳. 특히 합 = 최대 요소

그래서 제리스트의 최대 요소를 찾아 내고 동일 그것은 그 합계 서브 세트가 있는지 알려주는 동적 프로그래밍 알고리즘

부분 합계 문제점 합계를 넣어 다음

주어진 숫자와 같습니다. 예제 코드 아래

지금 우리가 세트가 그 세트에 대해 우리가 누구의 합이 목록의 max_element 동일 모든 부분 집합을 가지고, 그래서 출력 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 

입니다. 정렬 후 정렬 이후에 하위 집합을 찾으려면 동적 프로그래밍을 시작해야하므로 위 예제에서 제공된 입력은 정렬 된 목록입니다.

실제로 철저한 검색 결과는 O (2^n) 시간이되므로 동적 프로그래밍을 사용하여 위의 방법으로 개선해야합니다.