मान लीजिए कि हमारे पास एक छड़ है जिसकी लंबाई n है। हमारे पास एक सूची भी है, जिसमें प्रत्येक आकार के लिए अलग-अलग आकार और मूल्य शामिल हैं। हमें छड़ को काटकर बाजार में बेचकर अधिकतम मूल्य ज्ञात करना होता है। विभिन्न पदों पर कटौती करके और रॉड काटने के बाद कीमतों की तुलना करके सर्वोत्तम मूल्य प्राप्त करने के लिए।
इसलिए, यदि इनपुट कीमतों की तरह है =[1, 5, 8, 9, 10, 17, 17, 20], n =8, तो आउटपुट 22 होगा, जैसे कि रॉड को लंबाई 2 और 6 में काटने से। लाभ 5 + 17 =22 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
आकार के सरणी लाभ को परिभाषित करें:n+1.
-
लाभ [0] :=0
-
इनिशियलाइज़ i :=1 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), करें -
-
maxProfit :=ऋणात्मक अनंत
-
इनिशियलाइज़ j :=0 के लिए, जब j
-
maxProfit :=अधिकतम लाभ और कीमत का अधिकतम[j] + लाभ[i − j − 1]
-
-
लाभ [i] :=अधिकतम लाभ
-
-
अधिकतम लाभ लौटाएं
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
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 << rodCutting(priceList, rodLength);
} इनपुट
{1, 5, 8, 9, 10, 17, 17, 20}, 8 आउटपुट
22