dynamic-programming => रॉड काटना

अधिकतम लाभ प्राप्त करने के लिए रॉड को काटना

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

       +---+---+---+---+---+---+---+---+
 (price)| 1 | 5 | 8 | 9 | 10| 17| 17| 20|
        +---+---+---+---+---+---+---+---+

हम एक 2 डी सरणी डीपी [एम] [एन + 1] का उपयोग करेंगे जहां एन रॉड की लंबाई है और एम मूल्य सरणी की लंबाई है। हमारे उदाहरण के लिए, हमें dp [8] [९] की आवश्यकता होगी। यहाँ dp [i] [j] लंबाई की रॉड को बेचकर अधिकतम मूल्य का निरूपण किया जाएगा। हमारे पास लंबाई j का अधिकतम मान हो सकता है या हम लाभ को अधिकतम करने के लिए लंबाई को तोड़ सकते हैं।

सबसे पहले, 0 कॉलम के लिए, यह कुछ भी योगदान नहीं करेगा इसलिए सभी मानों को 0. के रूप में चिह्नित किया जाएगा। इसलिए 0 वें कॉलम के सभी मान 0. होंगे। dp [0] [1] के लिए , हम अधिकतम मूल्य प्राप्त कर सकते हैं। बेचने की लंबाई की लंबाई 1. यह लंबाई के लिए 1.Similarly 2 डीपी की रॉड के लिए होगा [0] [2] हमारे पास 2 (1 + 1) हो सकता है। यह डीपी तक जारी है [0] [8] । पहली पुनरावृत्ति के बाद। हमारी डीपी [] सरणी की तरह दिखेगा।

      +---+---+---+---+---+---+---+---+---+
 (price)| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
        +---+---+---+---+---+---+---+---+---+
  (1) 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 |
        +---+---+---+---+---+---+---+---+---+
  (5) 2 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
  (8) 3 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
  (9) 4 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (10) 5 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (17) 6 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (17) 7 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (20) 8 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+

Dp [2] [2] के लिए हम खुद से पूछते हैं कि अगर मैं रॉड को दो टुकड़ों (1,1) में तोड़ता हूं या पूरी (लंबाई = 2) के रूप में रॉड ले रहा हूं तो हम क्या देख सकते हैं। अगर मैं रॉड को दो टुकड़ों में तोड़ता हूं तो अधिकतम लाभ जो मैं कर सकता हूं वह 2 है और अगर मेरे पास रॉड है तो मैं इसे 5. के लिए बेच सकता हूं। दूसरी पुनरावृत्ति के बाद डीपी [] सरणी की तरह दिखेगा:

     +---+---+---+---+---+---+---+---+---+
 (price)| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
        +---+---+---+---+---+---+---+---+---+
  (1) 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 |
        +---+---+---+---+---+---+---+---+---+
  (5) 2 | 0 | 1 | 5 | 6 | 10| 11| 15| 16| 20|
        +---+---+---+---+---+---+---+---+---+
  (8) 3 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
  (9) 4 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (10) 5 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (17) 6 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (17) 7 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (20) 8 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+

तो dp [i] [j] की गणना करने के लिए हमारा सूत्र दिखेगा:

if j>=i
    dp[i][j] = Max(dp[i-1][j], price[i]+arr[i][j-i]);
else
    dp[i][j] = dp[i-1][j];

अंतिम पुनरावृत्ति के बाद हमारा dp [] एरे जैसा दिखेगा

       +---+---+---+---+---+---+---+---+---+
 (price)| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
        +---+---+---+---+---+---+---+---+---+
  (1) 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 |
        +---+---+---+---+---+---+---+---+---+
  (5) 2 | 0 | 1 | 5 | 6 | 10| 11| 15| 16| 20|
        +---+---+---+---+---+---+---+---+---+
  (8) 3 | 0 | 1 | 5 | 8 | 10| 13| 16| 18| 21|
        +---+---+---+---+---+---+---+---+---+
  (9) 4 | 0 | 1 | 5 | 8 | 10| 13| 16| 18| 21|
        +---+---+---+---+---+---+---+---+---+
 (10) 5 | 0 | 1 | 5 | 8 | 10| 13| 16| 18| 21|
        +---+---+---+---+---+---+---+---+---+
 (17) 6 | 0 | 1 | 5 | 8 | 10| 13| 17| 18| 22|
        +---+---+---+---+---+---+---+---+---+
 (17) 7 | 0 | 1 | 5 | 8 | 10| 13| 17| 18| 22|
        +---+---+---+---+---+---+---+---+---+
 (20) 8 | 0 | 1 | 5 | 8 | 10| 13| 17| 18| 22|
        +---+---+---+---+---+---+---+---+---+

हम परिणाम dp [n] [m + 1] पर होगा ।

जावा में कार्यान्वयन

public int getMaximumPrice(int price[],int n){
        int arr[][] = new int[n][price.length+1];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<price.length+1;j++){
                if(j==0 || i==0)
                    arr[i][j] = 0;
                else if(j>=i){
                    arr[i][j] = Math.max(arr[i-1][j], price[i-1]+arr[i][j-i]);
                }else{
                    arr[i][j] = arr[i-1][j];
                }
            }
        }
        return arr[n-1][price.length];
    }

समय जटिलता

O(n^2)

Modified text is an extract of the original Stack Overflow Documentation

के तहत लाइसेंस प्राप्त है CC BY-SA 3.0

से संबद्ध नहीं है Stack Overflow

dynamic-programming
रॉड काटना

खोज…

अधिकतम लाभ प्राप्त करने के लिए रॉड को काटना