समस्या कथन
एन तत्वों और योग की एक सरणी को देखते हुए। हमें अधिकतम आकार के सबसेट का आकार खोजने की जरूरत है जिसका योग दिए गए योग के बराबर है
उदाहरण
यदि इनपुट सरणी arr ={ 2, 3, 5, 10} और योग =20 है तो आउटपुट 4 के रूप में होगा -
2 + 3 + 5 + 10 =20 जो दिए गए योग के बराबर है
एल्गोरिदम
हम इस समस्या को हल करने के लिए गतिशील प्रोग्रामिंग का उपयोग कर सकते हैं।
अधिकतम उपसमुच्चय की गणना करने के लिए, हम एक अन्य DP सरणी (जिसे 'गिनती सरणी' कहा जाता है) का उपयोग करते हैं, जहाँ गिनती [i] [j] अधिकतम होती है।
- गिनती[i][j-1]। यहां वर्तमान तत्व पर विचार नहीं किया गया है।
- scount[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