Таяк кесүү  


Кыйынчылык деңгээли жеңил
Көп суралган Amazon Directi Flipkart Гугл 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 баасынын эң жакшы натыйжасын берет.

жакындоо  

Демек, бул көйгөйдү чечүү үчүн, маселени рекурсивдүү чечүүнү ойлонсо болот. Жана мамиле кыйла туура. Ошентип, рекурсияны колдонуп, көйгөйдү кантип чечсек болорун талкуулайлы. Чыбыкты ар кандай узундуктагы сегменттерге кескенге аракет кылсак болот. Андан кийин бардык таяктарды кескенден кийин пайда болгон таякчалардын баасын эсептейбиз. Бирок биз таяктарды кесүүнүн бардык жолдорун табышыбыз керек деп жатканда. Бул операция өтө кымбатка турат жана убакыттын экспоненциалдык татаалдыгына ээ. Демек, биз ушул эсептөөлөрдү кандайдыр бир деңгээлде азайтышыбыз керек. Эгерде кесүү учурунда таякча сегментинин баасын кошсок, оптимизация болушу мүмкүн. Андан кийин маселени дагы кичинекей таяк менен чечип алыңыз. Бирок бул жетиштүү эмес, бул алгоритм экспоненциалдуу убакытты талап кылат.

ошондой эле
Ири суммадагы туташ Subarray

Таяк маселесин кесүү үчүн рекурсивдүү формула

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

Ошентип, алгоритмдин кандайча иштеп жаткандыгын көрүү үчүн кыска убакыт алсак. CutRod (n-1), CutingRod (n-2),…, CutingRod (1) деп атагандыгыбызды байкап жатабыз, андан кийин дагы CutRod деп атоону уланта беребиз. CutRod (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

Комплекстик анализ  

Убакыт татаалдыгы

O (N ^ 2), анткени биз ылдыйдан өйдө DP ыкмасын колдонуп, кичирээк таякчалардын наркын жаңыртып турабыз. Бул экспоненциалдуу убакытта чечилген маселени полиномдук убакытка чейин азайтууга мүмкүндүк берет.

Космостун татаалдыгы

O (N), анткени боштук DP столундагы баалуулуктарды сактоо үчүн колдонулуп жатат.