रॉड कटिंग समस्या

परिचय

एक रॉड (छड़) दी गई है जिसकी लंबाई n है। साथ ही एक टेबल भी दिया गया है जिसमें विभिन्न आकारों और उनकी कीमतों का विवरण है। लक्ष्य रॉड को काटकर और बेचकर अधिकतम मूल्य प्राप्त करना है।

समस्या विवरण

रॉड को विभिन्न स्थितियों पर काटकर और कटाई के बाद की कीमतों की तुलना करके सर्वोत्तम मूल्य प्राप्त किया जा सकता है। मान लीजिए f(n) लंबाई n की रॉड को काटने के बाद अधिकतम संभव मूल्य लौटाता है। हम इस फंक्शन को इस प्रकार लिख सकते हैं:

f(n) := price[i] + f(n – i – 1) से अधिकतम मूल्य, जहाँ i 0 से (n – 1) की सीमा में है।

इनपुट और आउटपुट

इनपुट: विभिन्न लंबाईयों की कीमतें, और रॉड की लंबाई। यहाँ लंबाई 8 है।

आउटपुट: बेचने के बाद अधिकतम लाभ 22 है।

रॉड को लंबाई 2 और 6 में काटें। लाभ = 5 + 17 = 22

एल्गोरिदम

rodCutting(price, n)
इनपुट: कीमत सूची, सूची में विभिन्न कीमतों की संख्या
आउटपुट: रॉड काटकर अधिकतम लाभ

Begin
    n+1 आकार का profit सरणी परिभाषित करें
    profit[0] := 0
    i := 1 से n तक, करें
        maxProfit := -∞
        j := 0 से i-1 तक, करें
            maxProfit := max(maxProfit, price[j] + profit[i-j-1])
        done
        profit[i] := maxProfit
    done
    maxProfit लौटाएं
End

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

int max(int a, int b) {
    return (a > b) ? a : b;
}

int rodCutting(int price[], int n) {
    int profit[n+1];
    profit[0] = 0;
    int maxProfit;
    
    for (int i = 1; i <= n; i++) {
        maxProfit = INT_MIN;
        for (int j = 0; j < i; j++)
            maxProfit = max(maxProfit, price[j] + profit[i-j-1]);
        profit[i] = maxProfit;
    }
    return maxProfit;
}

int main() {
    int priceList[] = {1, 5, 8, 9, 10, 17, 17, 20};
    int rodLength = 8;
    cout << "Maximum Price: " << rodCutting(priceList, rodLength);
}

आउटपुट

Maximum Price: 22