Ձող կտրելը


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Դիրեկտի Flipkart Google JP Morgan Microsoft
Դինամիկ ծրագրավորում

Խնդիրի հայտարարություն

«Ձող կտրելը» խնդրում նշվում է, որ ձեզ տրվում է որոշակի երկարության և գնի մի գավազան ձողերի բոլոր չափսերի համար, որոնք մուտքային երկարությունից փոքր են կամ հավասար են: Այսինքն `մենք գիտենք 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

Այսպիսով, եթե մի փոքր պահ անենք, թե ինչպես է աշխատում ալգորիթմը: Մենք կարող ենք տեսնել, որ մենք կոչում ենք cuttingRod (n-1), կտրումRod (n-2),…, կտրումRod (1), որն այնուհետև շարունակում է զանգահարել CutRod: Քանի որ կտրումըRod (i) կոչվում է մի քանի անգամ: Ավելի լավ է, եթե մենք պահենք այս արժեքները: Այսպիսով, մենք պատրաստվում ենք օգտագործել Դինամիկ ծրագրավորում նվազեցնել այս անհարկի հաշվարկները:

Կոդ

C ++ կոդը գավազան կտրելու համար

#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

Ձողի կտրման Java կոդ

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

Բարդության վերլուծություն

Timeամանակի բարդություն

Ո (N ^ 2), քանի որ մենք օգտագործում ենք «ներքևից վերև» DP մոտեցում և շարունակում ենք թարմացնել փոքր երկարության ձողերի արժեքը: Սա թույլ է տալիս կրճատել էքսպոնենտալ ժամանակում լուծված խնդիրը բազմանդամ ժամանակից:

Տիեզերական բարդություն

ՎՐԱ), քանի որ տարածությունն օգտագործվում է DP աղյուսակում արժեքները պահելու համար: