Kích thước tập con lớn nhất với tổng cho trước trong C++

Đề bài

Cho mảng N phần tử và giá trị sum. Tìm kích thước tập con lớn nhất có tổng bằng sum cho trước.

Ví dụ

Mảng arr = {2, 3, 5, 10}, sum = 20 → Output: 4 (vì 2+3+5+10 = 20).

Thuật toán quy hoạch động

Sử dụng 2 bảng DP:

• subset[i][j]: có thể tạo tổng i từ j phần tử đầu không?
• count[i][j]: kích thước tập con lớn nhất tạo được tổng i từ j phần tử đầu.

Công thức truy hồi:

• Không chọn phần tử j: count[i][j-1]
• Chọn phần tử j (giá trị X): count[i-X][j-1] + 1

Ví dụ minh họa

#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;
}

Kết quả

Result = 4

Độ phức tạp: O(sum × n) thời gian và không gian. Phù hợp khi sum không quá lớn.