C++에서 주어진 합을 만족하는 최대 크기 부분 집합 구하기

문제 정의

N개의 원소로 이루어진 배열과 하나의 합(sum)이 주어졌을 때, 원소들의 합이 주어진 값과 정확히 일치하는 부분 집합 중에서 가장 크기가 큰 부분 집합의 크기를 구하는 것이 이 문제의 목표입니다.

예시

입력 배열이 arr = { 2, 3, 5, 10 }이고 sum = 20이라면 출력은 4입니다.

2 + 3 + 5 + 10 = 20으로, 배열의 모든 원소를 더한 값이 주어진 합과 일치하기 때문입니다.

알고리즘

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다.

최대 크기의 부분 집합을 구하기 위해 별도의 DP 배열('count 배열')을 추가로 사용하며, count[i][j]에는 다음 두 값 중 더 큰 값이 저장됩니다.

• count[i][j-1]: 현재 원소를 부분 집합에 포함하지 않는 경우
• count[i - X][j-1] + 1: 현재 원소(X는 선택된 원소의 값)를 부분 집합에 포함하는 경우

여기서 subset[i][j]는 처음 j개의 원소만 사용하여 합 i를 만들 수 있는지 여부를 나타내고, count[i][j]는 그 경우 사용되는 원소의 최대 개수를 의미합니다. 합이 0일 때는 빈 부분 집합으로 항상 참이므로 개수를 0으로 초기화하고, 원소를 하나도 사용할 수 없는 상태에서 양수의 합을 만드는 것은 불가능하므로 -1로 초기화합니다.

C++ 구현 예제

#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