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