दिए गए कार्य को देखते हुए लंबाई a, b और c के रेखाखंडों की अधिकतम संख्या ज्ञात करना है जो दिए गए धनात्मक पूर्णांक N से बन सकते हैं।
आइए अब समझते हैं कि हमें एक उदाहरण का उपयोग करके क्या करना है -
इनपुट - एन=8, ए=3, बी=1, सी=2
आउटपुट - 8
स्पष्टीकरण - एन को बी के 8 खंडों में विभाजित किया जा सकता है जो कि अधिकतम संख्या में खंड बनाए जा सकते हैं।
इनपुट - एन=13, ए=2, बी=7, सी=3
आउटपुट -6
निम्नलिखित कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है
-
फ़ंक्शन में MaxSegment() एक सरणी MaxSeg[N +1] प्रकार int घोषित करें और इसे मान -1 के साथ प्रारंभ करें।
-
शून्य-वें सूचकांक को 0 के बराबर रखें क्योंकि इसमें कोई खंड नहीं होगा।
-
i=0 से i
-
उपरोक्त के अंदर यदि कथन एक और कथन रखता है यदि (i + a <=N) और putMaxSeg[i + a] =max(MaxSeg[i] + 1, MaxSeg[i + a]);
-
उपरोक्त चरण को b और c दोनों के लिए दोहराएं।
-
लूप के बाहर, MaxSeg[N] लौटाएं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int MaxSegment(int N, int a,int b, int c){
/* It will store the maximum number of segments each index can have*/
int MaxSeg[N + 1];
// initialization
memset(MaxSeg, -1, sizeof(MaxSeg));
// 0th index will have 0 segments
MaxSeg[0] = 0;
// traversing for every segments till n
for (int i = 0; i < N; i++){
if (MaxSeg[i] != -1){
if(i + a <= N ){
MaxSeg[i + a] = max(MaxSeg[i] + 1, MaxSeg[i + a]);
}
if(i + b <= N ){
MaxSeg[i + b] = max(MaxSeg[i] + 1, MaxSeg[i + b]);
}
if(i + c <= N ){
MaxSeg[i + c] = max(MaxSeg[i] + 1, MaxSeg[i + c]);
}
}
}
return MaxSeg[N];
}
int main(){
int N = 13, a = 2, b = 7, c = 3;
cout << MaxSegment(N, a, b, c);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो हमें निम्न आउटपुट मिलेगा -
6