रॉड काटना

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

विभिन्न पदों पर कटौती करके और रॉड काटने के बाद कीमतों की तुलना करके सर्वोत्तम मूल्य प्राप्त करने के लिए।

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

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

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

इनपुट :

विभिन्न लंबाई की कीमत, और छड़ की लंबाई। यहाँ लंबाई 8 है।

आउटपुट :

बेचने के बाद अधिकतम लाभ 22 है।

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

एल्गोरिदम

rodCutting(price, n)

इनपुट: मूल्य सूची, सूची में विभिन्न कीमतों की संख्या।

आउटपुट: छड़ काटने से अधिकतम लाभ।

Begin
   define profit array of size n + 1
   profit[0] := 0
   for i := 1 to n, do
      maxProfit := - ∞
      for j := 0 to i-1, do
         maxProfit := maximum of maxProfit and (price[j] + profit[i-j-1])
      done

      profit[i] := maxProfit
   done
   return maxProfit
End

उदाहरण

#include <iostream>
using namespace std;

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

int rodCutting(int price[], int n) {    //from price and length of n, find max profit
   int profit[n+1];
   profit[0] = 0;
   int maxProfit;

   for (int i = 1; i<=n; i++) {
      maxProfit = INT_MIN;    //initially set as -ve infinity
      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