Tuyên bố vấn đề
Cho một mảng gồm N phần tử và tính tổng. Chúng ta cần tìm kích thước của tập con kích thước lớn nhất có tổng bằng tổng đã cho
Ví dụ
Nếu mảng đầu vào là arr ={2, 3, 5, 10} và sum =20 thì đầu ra sẽ là 4 dưới dạng -
2 + 3 + 5 + 10 =20 bằng tổng đã cho
Thuật toán
Chúng tôi có thể sử dụng lập trình động để giải quyết vấn đề này.
Để đếm tập hợp con cực đại, chúng tôi sử dụng một mảng DP khác (được gọi là 'mảng đếm') trong đó count [i] [j] là cực đại.
- đếm [i] [j-1]. Ở đây phần tử hiện tại không được xem xét.
- scount [i- X] [j-1] + 1. Ở đây X là giá trị của phần tử hiện tại được chọn cho tập hợp con.
Ví dụ
#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;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra tiếp theo -
Result = 4