서브 세트의 합계를 이해하십시오.

Question

저는 대학에서 알고리즘을 Backtracking 학습하기 시작했습니다. 어쨌든 Subset-Sum 문제에 대한 프로그램을 만들었습니다. 잘 작동하지만 그 다음 내 프로그램 이 가능한 모든 조합을 알려주지 않는다는 것을 발견했습니다.

예 : 대상 합계에 100 가지 조합이 있지만 프로그램에서 30 만 제공됩니다. 다음은 코드입니다. 누군가 내 실수를 지적 할 수 있다면 큰 도움이 될 것입니다.

int tot=0;//tot is the total sum of all the numbers in the set. 
int prob[500], d, s[100], top = -1, n; // n = number of elements in the set. prob[i] is the array with the set. 
void subset() 
{ 
    int i=0,sum=0; //sum - being updated at every iteration and check if it matches 'd' 
    while(i<n) 
    { 
     if((sum+prob[i] <= d)&&(prob[i] <= d)) 
     { 
      s[++top] = i; 
      sum+=prob[i]; 
     } 
     if(sum == d) // d is the target sum 
     { 
      show(); // this function just displays the integer array 's' 
      top = -1; // top points to the recent number added to the int array 's' 
      i = s[top+1]; 
      sum = 0; 
     } 
     i++; 
     while(i == n && top!=-1) 
     { 
      sum-=prob[s[top]]; 
      i = s[top--]+1; 
     } 
    } 
} 

int main() 
{ 
    cout<<"Enter number of elements : ";cin>>n; 
    cout<<"Enter required sum : ";cin>>d; 
    cout<<"Enter SET :\n"; 
    for(int i=0;i<n;i++) 
    { 
     cin>>prob[i]; 
     tot+=prob[i]; 
    } 
    if(d <= tot) 
    { 
     subset(); 
    } 
    return 0; 
} 

내가 프로그램을 실행하면 : 8도 솔루션입니다

Enter number of elements : 7 
Enter the required sum : 12 
Enter SET : 
4 3 2 6 8 12 21 

SOLUTION 1 : 4, 2, 6 
SOLUTION 2 : 12 

, 4 만을, 내 프로그램을 보여 나던. 입력 수가 100 개 이상인 경우가 훨씬 더 나쁩니다. 이이어야 10000 개 조합,하지만 내 프로그램은 100

내가 따라하려고 로직 표시됩니다의 합만큼 주요 SET의 요소

1. 테이크를 하위 집합으로 부분 집합은 목표 합계보다 작거나 같습니다.
2. 서브 세트 sum에 특정 숫자를 더하면 목표보다 더 큰 숫자가 이됩니다.
3. 집합의 끝에 에 도달하고 대답을 찾지 못하면 최근에 찍은 숫자가 집합에서 제거되고 최근 번호가 제거 된 위치의 숫자 이 시작됩니다. (배열의 's'에 저장 한 값은 의 기본 SET에서 선택된 숫자의 위치입니다.) 때문에 당신이만큼 그들은 '돈으로 항목을 경우 1 단계

   에 "만큼"절에

Answer 1

당신이 세트에서 항목의 순서에 따라 달라을 찾아 가고있는 솔루션을 예를 들어, 일단 당신이 표적에 너를 얻으면 '4'와 '2', '8'은 목표를 넘어서게되므로 '8'앞에 '2'가 놓여있는 한 '4'와 '8'을 사용하지 않을 것입니다.

항목 추가를 건너 뛰거나 (하나의 하위 집합에 추가하고 다른 하위 집합에 추가하지 않을 수도 있음) 설정을 변경하고 다시 검사해야합니다.

Answer 2

이 될 스택이없는 솔루션이 가능하지만, 보통 (일반적으로 쉬운!) 역 추적 알고리즘을 구현하는 방법입니다 재귀를 통해, 예를 들어 수

int i = 0, n; // i needs to be visible to show() 
int s[100]; 

// Considering only the subset of prob[] values whose indexes are >= start, 
// print all subsets that sum to total. 
void new_subsets(int start, int total) { 
    if (total == 0) show(); // total == 0 means we already have a solution 

    // Look for the next number that could fit 
    while (start < n && prob[start] > total) { 
     ++start; 
    } 

    if (start < n) { 
     // We found a number, prob[start], that can be added without overflow. 
     // Try including it by solving the subproblem that results. 
     s[i++] = start; 
     new_subsets(start + 1, total - prob[start]); 
     i--; 

     // Now try excluding it by solving the subproblem that results. 
     new_subsets(start + 1, total); 
    } 
} 

그런 다음 main()에서이 부를 것이다 new_subsets(0, d);. 재귀는 처음에는 이해하기가 어려울 수 있지만, 머리를 감싸는 것이 중요합니다. 위의 내용이 이해가되지 않는 경우 문제를 쉽게 풀어보십시오 (예 : 피보나치 수를 재귀 적으로 생성).

주어진 해결책을 사용하는 대신 내가 알 수있는 한 가지 문제점은 솔루션을 찾자 마자이를 제거하고 첫 번째 숫자의 오른쪽에서 새로운 솔루션을 찾는 것입니다 이 솔루션에 포함되었습니다 (top = -1; i = s[top+1];은 i = s[0]을 의미하고 그 다음은 i++;입니다). 동일한 첫 번째 숫자로 시작하는 솔루션이 누락됩니다.대신 if (sum == d) { show(); }을 사용하여 모두 확인해야합니다.

처음에는 내 속인 while 루프가 혼란 스럽다는 것을 알았지 만 실제로는 올바른 일을하고 있다고 생각합니다. i은 배열 끝에 도달하면 부분 솔루션에 추가 된 마지막 번호를 삭제합니다. 배열의 마지막 숫자이면 부분 솔루션에서 두 번째 - 마지막 숫자를 삭제하기 위해 다시 반복됩니다. 부분 솔루션에 포함 된 숫자가 모두 별개의 위치에 있기 때문에 두 번 이상 반복 할 수 없습니다.

Answer 3

알고리즘을 자세히 분석하지는 못했지만 알고리즘을 사용하여 숫자 X로 시작하는 하나의 솔루션을 만든 후에 해당 숫자로 시작하는 솔루션이 여러 개있을 수 있다는 가능성을 설명하지 못했습니다. .

첫 번째 개선은 솔루션을 인쇄 한 후 스택 s 및 누적 합계를 다시 설정하지 않는 것입니다.