ರಾಡ್ ಕತ್ತರಿಸುವುದು


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಡೈರೆಕ್ಟಿ ಫ್ಲಿಪ್ಕಾರ್ಟ್ ಗೂಗಲ್ JP ಮೋರ್ಗಾನ್ ಮೈಕ್ರೋಸಾಫ್ಟ್
ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

ಇನ್ಪುಟ್ ಉದ್ದಕ್ಕಿಂತ ಚಿಕ್ಕದಾದ ಅಥವಾ ಸಮನಾಗಿರುವ ಎಲ್ಲಾ ಗಾತ್ರದ ರಾಡ್‌ಗಳಿಗೆ ನಿಮಗೆ ಕೆಲವು ನಿರ್ದಿಷ್ಟ ಉದ್ದ ಮತ್ತು ಬೆಲೆಗಳ ರಾಡ್ ನೀಡಲಾಗಿದೆ ಎಂದು “ರಾಡ್ ಕಟಿಂಗ್” ಸಮಸ್ಯೆ ಹೇಳುತ್ತದೆ. ಅಂದರೆ 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

ಆದ್ದರಿಂದ, ಅಲ್ಗಾರಿದಮ್ ಹೇಗೆ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತಿದೆ ಎಂಬುದನ್ನು ನೋಡಲು ನಾವು ಸ್ವಲ್ಪ ಸಮಯ ತೆಗೆದುಕೊಂಡರೆ. ನಾವು ಕಟಿಂಗ್ ರಾಡ್ (ಎನ್ -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), ಏಕೆಂದರೆ ನಾವು ಬಾಟಪ್-ಅಪ್ ಡಿಪಿ ವಿಧಾನವನ್ನು ಬಳಸುತ್ತಿದ್ದೇವೆ ಮತ್ತು ಸಣ್ಣ ಉದ್ದದ ರಾಡ್‌ಗಳ ವೆಚ್ಚವನ್ನು ನವೀಕರಿಸುತ್ತಲೇ ಇರುತ್ತೇವೆ. ಘಾತೀಯ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಲಾದ ಸಮಸ್ಯೆಯನ್ನು ಬಹುಪದ ಸಮಯಕ್ಕೆ ಕಡಿಮೆ ಮಾಡಲು ಇದು ಅನುಮತಿಸುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಏಕೆಂದರೆ ಡಿಪಿ ಕೋಷ್ಟಕದಲ್ಲಿ ಮೌಲ್ಯಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ಜಾಗವನ್ನು ಬಳಸಲಾಗುತ್ತಿದೆ.