একটি রড কাটা


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক ডাইরেক্টি Flipkart গুগল জেপি মরগান মাইক্রোসফট
ডায়নামিক প্রোগ্রামিং

সমস্যা বিবৃতি

"একটি রড কাটিং" সমস্যাটি বলে যে আপনাকে সমস্ত আকারের রডগুলির জন্য কিছু নির্দিষ্ট দৈর্ঘ্যের দাম এবং দাম দেওয়া হয় যা ইনপুট দৈর্ঘ্যের চেয়ে ছোট বা সমান। এটিই আমরা জানি যে রডের দৈর্ঘ্য n ছিল, বিবেচনা করে 1 থেকে n এর দৈর্ঘ্যের রডের দাম। এখানে একটি বিষয় লক্ষ্য করুন যে বিভিন্ন দৈর্ঘ্যের রডের জন্য দাম সমানভাবে বিতরণ করা হয় না। নির্দিষ্ট দৈর্ঘ্যের কয়েকটি রডের দাম অন্যদের চেয়ে বেশি থাকে। এই রডগুলি বিভিন্ন দৈর্ঘ্যের অন্যান্য রডের তুলনায় বেশি দৈর্ঘ্য থাকতে পারে বা থাকতে পারে।

উদাহরণ

length = 1 2 3 4 5 6 7
price = 4 5 6 7 7 1 1
28

 

একটি রড কাটাব্যাখ্যা: আমরা সবচেয়ে ভাল করতে পারি দৈর্ঘ্যের rod রড নেওয়া যা আমাদের ব্যয়ের ২৮ দামের সেরা ফলাফল দিতে পারে।

অভিগমন

সুতরাং এই সমস্যাটি সমাধানের জন্য, কেউ সমস্যাটি পুনরাবৃত্তভাবে সমাধান করার কথা ভাবতে পারে। এবং পদ্ধতির মোটামুটি সঠিক। সুতরাং আসুন আমরা কীভাবে পুনরাবৃত্তি ব্যবহার করে সমস্যাটি সমাধান করতে পারি তা আলোচনা করা যাক। আমরা বিভিন্ন দৈর্ঘ্যের অংশগুলিতে রডটি কাটতে চেষ্টা করতে পারি। তারপরে আমরা সমস্ত রডগুলি কাটার পরে তৈরি হওয়া রডগুলির জন্য মূল্য গণনা করি। তবে যখন আমরা বলছি যে আমাদের রডগুলি কাটার সমস্ত উপায় খুঁজে বের করা দরকার। এই অপারেশনটি অত্যন্ত ব্যয়বহুল এবং সময়সীমাগত জটিলতা রয়েছে। সুতরাং আমাদের একরকম এই গণনাগুলি হ্রাস করা দরকার। একটি অপ্টিমাইজেশন হতে পারে যদি আমরা কাটার সময় রডের একটি অংশের ব্যয় যুক্ত করি। তারপরে আরও একটি ছোট রড দিয়ে সমস্যার সমাধান করুন। তবে এটি যথেষ্ট ভাল নয়, এই অ্যালগরিদমটি এখনও ক্ষতিকারক সময় নেয়।

রড সমস্যা কাটার জন্য পুনরাবৃত্ত সূত্রটি

cuttingRod(n) = max(cost[i] + cuttingRod(n-i-1)) where i is in range from 0 to n-1

সুতরাং, আমরা যদি অ্যালগরিদমটি কীভাবে কাজ করছে তা দেখার জন্য যদি একটি সংক্ষিপ্ত সময় নিই। আমরা দেখতে পাচ্ছি যে আমরা কাটারিং রড (এন -1), কাটারডোড (এন -2),…, কাটারড্রড (1) যা আবার আবার কাটারডকে কল করে চলেছি। যেহেতু কাটরড (i) একাধিকবার বলা হয়। আমরা যদি এই মানগুলি সঞ্চয় করি তবে এটি আরও ভাল। সুতরাং আমরা ব্যবহার করতে যাচ্ছি ডায়নামিক প্রোগ্রামিং এই অপ্রয়োজনীয় গণনা কমাতে।

কোড

রড কাটার জন্য সি ++ কোড

#include<bits/stdc++.h>
using namespace std;

int cuttingRod(vector<int> &cost) 
{
  int n = cost.size();
  int dp[n+1]; dp[0] = 0;

  for(int i=1;i<=n;i++){
    dp[i] = INT_MIN;
    for(int j=0;j<i;j++)
      dp[i] = max(dp[i], cost[j]+dp[i-j-1]);
  }
  return dp[n];
} 

int main(){
  // length of input rod
  int n;cin>>n;
  // store prices for length 1 to n
  vector<int> cost(n);
  for(int i=0;i<n;i++)
    cin>>cost[i];
  int maxCost = cuttingRod(cost);
  cout<<maxCost;
}
7
4 5 6 7 7 1 1
28

রড কাটার জন্য জাভা কোড

import java.util.*;
class Main{
  
  static int cuttingRod(ArrayList<Integer> cost){
    int n = cost.size();
    int dp[] = new int[n+1];
    dp[0] = 0;

    for(int i=1;i<=n;i++){
      dp[i] = Integer.MIN_VALUE;
      for(int j=0;j<i;j++)
        dp[i] = Math.max(dp[i], cost.get(j)+dp[i-j-1]);
    }
    return dp[n];
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    // length of input rod
    int n = sc.nextInt();
    // store prices for length 1 to n
    ArrayList<Integer> cost = new ArrayList<Integer>();
    for(int i=0;i<n;i++){
      int a = sc.nextInt();
      cost.add(a);
    }
    int maxCost = cuttingRod(cost);
    System.out.println(maxCost);
  }
}
7
4 5 6 7 7 1 1
28

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন ^ 2), কারণ আমরা একটি ডাউন-আপ ডিপি পদ্ধতির ব্যবহার করছি এবং ছোট দৈর্ঘ্যের রডগুলির মূল্য আপডেট করতে থাকি। এটি বহনযোগ্য সময়ে ক্ষণস্থায়ী সময়ে সমাধান করা সমস্যা হ্রাস করতে দেয়।

স্পেস জটিলতা ity

চালু), কারণ স্থানটি ডিপি টেবিলে মানগুলি সংরক্ষণের জন্য ব্যবহৃত হচ্ছে।