C++에서 주어진 합계의 최대 크기 하위 집합

문제 설명

N 요소의 배열과 합계가 주어집니다. 합이 주어진 합과 같은 최대 크기 부분집합의 크기를 찾아야 합니다.

예시

입력 배열이 arr ={ 2, 3, 5, 10 }이고 sum =20이면 출력은 −

2 + 3 + 5 + 10 =20 이는 주어진 합계와 같습니다.

알고리즘

동적 프로그래밍을 사용하여 이 문제를 해결할 수 있습니다.

최대 부분 집합을 계산하기 위해 count[i][j]가 최대인 다른 DP 배열('count 배열'이라고 함)을 사용합니다.

• 카운트[i][j-1]. 여기에서 현재 요소는 고려되지 않습니다.
• count[i- X][j-1] + 1. 여기서 X는 하위 집합에 대해 선택된 현재 요소의 값입니다.

예시

#include<bits/stdc++.h>
using namespace std;
int isSubsetSum(int set[], int n, int sum) {
   bool subset[sum + 1][n + 1];
   int count[sum + 1][n + 1];
   for (int i = 0; i <= n; i++) {
   subset[0][i] = true;
      count[0][i] = 0;
   }
   for (int i = 1; i <= sum; i++) {
      subset[i][0] = false;
      count[i][0] = -1;
   }
   for (int i = 1; i <= sum; i++) {
      for (int j = 1; j <= n; j++) {
         subset[i][j] = subset[i][j - 1];
         count[i][j] = count[i][j - 1];
         if (i >= set[j - 1]) {
            subset[i][j] = subset[i][j] || subset[i - set[j - 1]][j - 1];
            if (subset[i][j]) {
               count[i][j] = max(count[i][j - 1], count[i - set[j - 1]][j - 1] + 1);
            }
         }
      }
  }
  return count[sum][n];
}
int main() {
   int set[] = { 2, 3, 5, 10 };
   int sum = 20;
   int n = 4;
   cout<< "Result = " << isSubsetSum(set, n, sum) << endl;
}

출력

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

Result = 4