C++ में लंबाई p, q और r के खंडों की संख्या को अधिकतम करें

समस्या कथन

लंबाई L की एक छड़ को देखते हुए, कार्य छड़ को इस तरह से काटना है कि लंबाई p, q और r के खंडों की कुल संख्या अधिकतम हो। खंड केवल लंबाई p, q, और r के हो सकते हैं

यदि l =15, p =2, q =3 और r =5 तो हम निम्नानुसार 7 खंड बना सकते हैं -

{2, 2, 2, 2, 2, 2, 3}

एल्गोरिदम

हम डायनेमिक प्रोग्रामिंग का उपयोग करके इस समस्या को हल कर सकते हैं

1. Initialize dp[] array to 0
2. Iterate till the length of the rod. For every i, a cut of p, q and r if possible is done.
3. Initialize ans[i+p] = max( ans[i+p], 1 + ans[i]), ans[i+q] = max(ans[i+q], 1 + ans[i]) and ans[i+r] = max(ans[i+r], 1 + ans[i]) for all the possible cuts.
4. ans[i] will be 0 if a cut at i-th index is not possible. ans[l] will give the maximum number of cuts possible

उदाहरण

#include <bits/stdc++.h>
using namespace std;
int getMaximumSegments(int l, int p, int q, int r){
   int dp[l + 1];
   memset(dp, -1, sizeof(dp));
   dp[0] = 0;
   for (int i = 0; i <= l; ++i) {
      if (dp[i] == -1) {
         continue;
      }
      if (i + p <= l) {
         dp[i + p] = max(dp[i + p], dp[i] + 1);
      }
      if (i + q <= l) {
         dp[i + q] = max(dp[i + q], dp[i] + 1);
      }
      if (i + r <= l) {
         dp[i + r] = max(dp[i + r], dp[i] + 1);
      }
   }
   return dp[l];
}
int main(){
   int l = 15, p = 2, q = 3, r = 5;
   cout << "Number of segments = " << getMaximumSegments(l, p, q, r) << endl;
   return 0;
}

आउटपुट

जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है-

Number of segments = 7