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. dp[] ऐरे को 0 से प्रारंभ करें।
2. रॉड की लंबाई तक पुनरावृति करें। प्रत्येक i के लिए, यदि संभव हो तो p, q और r का कट करें।
3. सभी संभावित कट्स के लिए ans[i+p] = max(ans[i+p], 1 + ans[i]), ans[i+q] = max(ans[i+q], 1 + ans[i]) और ans[i+r] = max(ans[i+r], 1 + ans[i]) प्रारंभ करें।
4. ans[i] 0 होगा यदि i-वें इंडेक्स पर कट संभव नहीं है। ans[l] अधिकतम संभव कट्स की संख्या देगा।

उदाहरण

#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