ஒரு தடி வெட்டுதல்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் டைரக்டி , Flipkart கூகிள் ஜேபி மோர்கன் மைக்ரோசாப்ட்
டைனமிக் புரோகிராமிங்

சிக்கல் அறிக்கை

உள்ளீட்டு நீளத்தை விட சிறியதாகவோ அல்லது சமமாகவோ இருக்கும் அனைத்து அளவிலான தண்டுகளுக்கான சில குறிப்பிட்ட நீளம் மற்றும் விலைகள் உங்களுக்கு வழங்கப்படுவதாக “ஒரு தடியை வெட்டுதல்” சிக்கல் கூறுகிறது. அதாவது 1 முதல் n வரையிலான நீள தண்டுகளின் விலை நமக்குத் தெரியும், தடியின் நீளம் n ஆக இருப்பதைக் கருத்தில் கொள்ளுங்கள். இங்கே கவனிக்க வேண்டிய ஒரு விஷயம் என்னவென்றால், வெவ்வேறு நீளங்களின் தடிக்கான விலை சமமாக விநியோகிக்கப்படவில்லை. ஒரு குறிப்பிட்ட நீளம் கொண்ட சில தண்டுகள் மற்றவர்களை விட அதிக விலைகளைக் கொண்டுள்ளன. வெவ்வேறு தண்டுகளின் மற்ற தண்டுகளுடன் ஒப்பிடும்போது இந்த தண்டுகள் அதிக நீளத்தைக் கொண்டிருக்கலாம் அல்லது கொண்டிருக்கலாம்.

உதாரணமாக

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

 

ஒரு தடி வெட்டுதல்விளக்கம்: 7 தண்டுகளின் நீளத்தை எடுத்துக்கொள்வதுதான் நாம் செய்யக்கூடியது, இது செலவு 28 இன் சிறந்த முடிவை நமக்குத் தரும்.

அணுகுமுறை

எனவே இந்த சிக்கலை தீர்க்க, ஒருவர் மீண்டும் மீண்டும் சிக்கலை தீர்க்க யோசிக்க முடியும். அணுகுமுறை மிகவும் சரியானது. எனவே மறுநிகழ்வைப் பயன்படுத்தி சிக்கலை எவ்வாறு தீர்ப்பது என்று விவாதிப்போம். வெவ்வேறு நீளங்களின் பிரிவுகளில் தடியை வெட்ட முயற்சி செய்யலாம். அனைத்து தண்டுகளையும் வெட்டிய பின் உருவாகும் தண்டுகளுக்கான விலையை நாம் கணக்கிடுகிறோம். ஆனால் தண்டுகளை வெட்டுவதற்கான அனைத்து வழிகளையும் நாம் கண்டுபிடிக்க வேண்டும் என்று சொல்லும்போது. இந்த செயல்பாடு மிகவும் விலை உயர்ந்தது மற்றும் அதிவேக நேர சிக்கலைக் கொண்டுள்ளது. எனவே இந்த கணக்கீடுகளை நாம் எப்படியாவது குறைக்க வேண்டும். வெட்டும் நேரத்தில் தடியின் ஒரு பிரிவின் விலையைச் சேர்த்தால் ஒரு தேர்வுமுறை இருக்கும். பின்னர் ஒரு சிறிய தடியால் மீண்டும் சிக்கலை தீர்க்கவும். ஆனால் இது போதுமானதாக இல்லை, இந்த வழிமுறை இன்னும் அதிவேக நேரத்தை எடுக்கும்.

ஒரு தடி சிக்கலை வெட்டுவதற்கான சுழல்நிலை சூத்திரம்

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

எனவே, வழிமுறை எவ்வாறு செயல்படுகிறது என்பதைப் பார்க்க சிறிது நேரம் எடுத்துக் கொண்டால். நாம் கட்டிங்ரோட் (n-1), கட்டிங்ரோட் (n-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), ஏனென்றால் நாங்கள் கீழே உள்ள டிபி அணுகுமுறையைப் பயன்படுத்துகிறோம், மேலும் சிறிய நீள தண்டுகளின் விலையை புதுப்பித்துக்கொண்டே இருக்கிறோம். இது அதிவேக நேரத்தில் தீர்க்கப்பட்ட சிக்கலை பல்லுறுப்புறுப்பு நேரத்திற்கு குறைக்க அனுமதிக்கிறது.

விண்வெளி சிக்கலானது

ஓ (என்), ஏனெனில் டிபி அட்டவணையில் மதிப்புகளை சேமிக்க இடம் பயன்படுத்தப்படுகிறது.