मान लीजिए हमारे पास लंबाई n की एक रॉड दी गई है। हमारे पास एक सूची भी है, जिसमें प्रत्येक आकार के लिए अलग-अलग आकार और कीमत है। हमें रॉड को काटकर और उन्हें बाजार में बेचकर अधिकतम कीमत ढूंढनी है। रॉड को अलग-अलग स्थितियों पर काटकर और काटने के बाद कीमतों की तुलना करके सर्वोत्तम कीमत प्राप्त करना है।
इसलिए, यदि इनपुट prices = [1, 5, 8, 9, 10, 17, 17, 20], n = 8 जैसा है, तो आउटपुट 22 होगा, क्योंकि रॉड को लंबाई 2 और 6 में काटकर। लाभ 5 + 17 = 22 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
आकार n+1 का एक सरणी profit परिभाषित करें।
profit[0] := 0
i := 1 से आरंभ करें, जब i <= n, अपडेट करें (i को 1 से बढ़ाएं), करें -
maxProfit := नकारात्मक अनंत
j := 0 से आरंभ करें, जब j < i, अपडेट करें (j को 1 से बढ़ाएं), करें -
maxProfit := maxProfit और price[j] + profit[i - j - 1] का अधिकतम
profit[i] := maxProfit
maxProfit लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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
