ਇੱਕ ਡੰਡਾ ਕੱਟਣਾ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਦਿਸ਼ਾ ਫਲਿੱਪਕਾਰਟ ਗੂਗਲ JP Morgan Microsoft ਦੇ
ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

“ਇੱਕ ਰਾਡ ਕੱਟਣਾ” ਸਮੱਸਿਆ ਦੱਸਦੀ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਕੁਝ ਖਾਸ ਲੰਬਾਈ ਦੀ ਡੰਡੇ ਦਿੱਤੀ ਜਾਂਦੀ ਹੈ ਅਤੇ ਸਾਰੇ ਆਕਾਰ ਦੀਆਂ ਡੰਡੀਆਂ ਦੀਆਂ ਕੀਮਤਾਂ ਜਿਹੜੀਆਂ ਇੰਪੁੱਟ ਲੰਬਾਈ ਤੋਂ ਛੋਟੀਆਂ ਜਾਂ ਬਰਾਬਰ ਹੁੰਦੀਆਂ ਹਨ. ਇਹ ਹੀ ਹੈ ਕਿ ਅਸੀਂ ਜਾਣਦੇ ਹਾਂ ਕਿ ਡੰਡੇ ਦੀ ਲੰਬਾਈ ਨੂੰ ਐਨ ਤੋਂ ਲੈ ਕੇ 1 ਤੋਂ ਲੈ ਕੇ ਲੰਬਾਈ ਦੀਆਂ ਸਲਾਖਾਂ ਦੀ ਕੀਮਤ ਹੈ. ਇੱਥੇ ਇਕ ਧਿਆਨ ਦੇਣ ਵਾਲੀ ਗੱਲ ਇਹ ਹੈ ਕਿ ਵੱਖ ਵੱਖ ਲੰਬਾਈ ਦੇ ਡੰਡੇ ਦੀ ਕੀਮਤ ਬਰਾਬਰ ਵੰਡ ਨਹੀਂ ਕੀਤੀ ਜਾਂਦੀ. ਕੁਝ ਲੰਬੜਾਂ ਵਾਲੀਆਂ ਕੁਝ ਡੰਕੀਆਂ ਦੀ ਕੀਮਤ ਦੂਜੇ ਨਾਲੋਂ ਵਧੇਰੇ ਹੁੰਦੀ ਹੈ. ਇਹ ਡੰਡੇ ਵੱਖ-ਵੱਖ ਲੰਬਾਈ ਦੀਆਂ ਹੋਰ ਡੰਕਿਆਂ ਦੇ ਮੁਕਾਬਲੇ ਵਧੇਰੇ ਲੰਬਾਈ ਦੇ ਸਕਦੇ ਹਨ ਜਾਂ ਹੋ ਸਕਦੇ ਹਨ.

ਉਦਾਹਰਨ

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

 

ਇੱਕ ਡੰਡਾ ਕੱਟਣਾਵਿਆਖਿਆ: ਸਭ ਤੋਂ ਵਧੀਆ ਅਸੀਂ ਕਰ ਸਕਦੇ ਹਾਂ ਲੰਬਾਈ ਦੀਆਂ 7 ਡਾਂਗਾਂ ਜੋ ਸਾਨੂੰ 28 ਦੀ ਕੀਮਤ ਦਾ ਵਧੀਆ ਨਤੀਜਾ ਦੇ ਸਕਦੀਆਂ ਹਨ.

ਪਹੁੰਚ

ਇਸ ਲਈ ਇਸ ਸਮੱਸਿਆ ਦੇ ਹੱਲ ਲਈ, ਕੋਈ ਵਿਅਕਤੀ ਇਸ ਸਮੱਸਿਆ ਨੂੰ ਲਗਾਤਾਰ ਹੱਲ ਕਰਨ ਬਾਰੇ ਸੋਚ ਸਕਦਾ ਹੈ. ਅਤੇ ਪਹੁੰਚ ਕਾਫ਼ੀ ਸਹੀ ਹੈ. ਇਸ ਲਈ ਆਓ ਵਿਚਾਰੀਏ ਕਿ ਅਸੀਂ ਦੁਹਰਾਓ ਦੀ ਵਰਤੋਂ ਨਾਲ ਸਮੱਸਿਆ ਨੂੰ ਕਿਵੇਂ ਹੱਲ ਕਰ ਸਕਦੇ ਹਾਂ. ਅਸੀਂ ਵੱਖ-ਵੱਖ ਲੰਬਾਈ ਦੇ ਹਿੱਸਿਆਂ ਵਿਚ ਡੰਡੇ ਨੂੰ ਕੱਟਣ ਦੀ ਕੋਸ਼ਿਸ਼ ਕਰ ਸਕਦੇ ਹਾਂ. ਫਿਰ ਅਸੀਂ ਉਨ੍ਹਾਂ ਡੰਡੇ ਦੀ ਕੀਮਤ ਦੀ ਗਣਨਾ ਕਰਦੇ ਹਾਂ ਜੋ ਸਾਰੇ ਡੰਡੇ ਕੱਟਣ ਤੋਂ ਬਾਅਦ ਬਣਦੇ ਹਨ. ਪਰ ਜਦੋਂ ਅਸੀਂ ਕਹਿ ਰਹੇ ਹਾਂ ਕਿ ਸਾਨੂੰ ਡੰਡੇ ਕੱਟਣ ਦੇ ਸਾਰੇ allੰਗਾਂ ਨੂੰ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਇਹ ਓਪਰੇਸ਼ਨ ਬਹੁਤ ਮਹਿੰਗਾ ਹੈ ਅਤੇ ਸਮੇਂ ਦੀ ਗੁੰਝਲਦਾਰਤਾ ਹੈ. ਇਸ ਲਈ ਸਾਨੂੰ ਕਿਸੇ ਤਰ੍ਹਾਂ ਇਨ੍ਹਾਂ ਗਣਨਾਵਾਂ ਨੂੰ ਘਟਾਉਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਇੱਕ ਅਨੁਕੂਲਤਾ ਹੋ ਸਕਦੀ ਹੈ ਜੇ ਅਸੀਂ ਕੱਟਣ ਵੇਲੇ ਡੰਡੇ ਦੇ ਇੱਕ ਹਿੱਸੇ ਦੀ ਲਾਗਤ ਸ਼ਾਮਲ ਕਰੀਏ. ਫਿਰ ਸਮੱਸਿਆ ਨੂੰ ਫਿਰ ਇਕ ਛੋਟੀ ਜਿਹੀ ਡੰਡੇ ਨਾਲ ਹੱਲ ਕਰੋ. ਪਰ ਇਹ ਕਾਫ਼ੀ ਚੰਗਾ ਨਹੀਂ ਹੈ, ਇਹ ਐਲਗੋਰਿਦਮ ਅਜੇ ਵੀ ਘਾਤਕ ਸਮਾਂ ਲੈਂਦਾ ਹੈ.

ਇੱਕ ਡੰਡੇ ਦੀ ਸਮੱਸਿਆ ਨੂੰ ਕੱਟਣ ਲਈ ਆਵਰਤੀ ਫਾਰਮੂਲਾ ਹੈ

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

ਇਸ ਲਈ, ਜੇ ਅਸੀਂ ਇਹ ਵੇਖਣ ਲਈ ਇੱਕ ਛੋਟਾ ਜਿਹਾ ਪਲ ਕੱ takeੀਏ ਕਿ ਐਲਗੋਰਿਦਮ ਕਿਵੇਂ ਕੰਮ ਕਰ ਰਿਹਾ ਹੈ. ਅਸੀਂ ਵੇਖ ਸਕਦੇ ਹਾਂ ਕਿ ਅਸੀਂ ਕਟਿੰਗਰਡ (ਐਨ -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), ਕਿਉਂਕਿ ਅਸੀਂ ਇਕ ਡਾ bottomਨ-ਅਪ ਡੀਪੀ ਪਹੁੰਚ ਦੀ ਵਰਤੋਂ ਕਰ ਰਹੇ ਹਾਂ ਅਤੇ ਛੋਟੇ ਲੰਬਾਈ ਦੀਆਂ ਸਲਾਖਾਂ ਦੀ ਕੀਮਤ ਨੂੰ ਅਪਡੇਟ ਕਰਦੇ ਰਹਿੰਦੇ ਹਾਂ. ਇਹ ਸਮੱਸਿਆ ਨੂੰ ਘਟਾਉਣ ਦੀ ਇਜਾਜ਼ਤ ਦਿੰਦਾ ਹੈ ਜੋ ਘਟੀਆ ਸਮੇਂ ਵਿੱਚ ਬਹੁ-ਵਕਤ ਦੇ ਸਮੇਂ ਵਿੱਚ ਹੱਲ ਕੀਤਾ ਗਿਆ ਸੀ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਕਿਉਂਕਿ ਸਪੇਸ ਦੀ ਵਰਤੋਂ ਡੀ ਪੀ ਟੇਬਲ ਵਿੱਚ ਵੈਲਯੂਜ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਕੀਤੀ ਜਾ ਰਹੀ ਹੈ.