Саваа огтлох  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Directi Flipkart Google-ийн JP Morgan Microsoft-
Динамик програмчлал

Асуудлын мэдэгдэл  

“Саваа хайчлах” асуудалд танд тодорхой урттай саваа, оролтын уртаас бага эсвэл тэнцүү бүх хэмжээтэй савааны үнийг өгсөн гэж заасан байдаг. Энэ нь савааны уртыг n гэж тооцвол 1-ээс n хүртэлх урттай савааны үнийг бид мэднэ. Энд анзаарагдах нэг зүйл бол янз бүрийн урттай савааны үнэ тэгш хуваарилагдаагүй явдал юм. Тодорхой урттай зарим саваа бусадтай харьцуулахад өндөр үнэтэй байдаг. Эдгээр саваа нь өөр урттай бусад саваатай харьцуулахад илүү урт эсвэл урт байж болно.

Жишээ нь  

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

 

Саваа огтлохPinТайлбар: Бидний хийж чадах хамгийн сайн зүйл бол 7 саваа авах хамгийн сайн үр дүнг өгч чадах 28 саваа авах явдал юм.

арга барил  

Тиймээс энэ асуудлыг шийдэхийн тулд асуудлыг давтаж шийдвэрлэх талаар бодож болно. Энэ арга нь нэлээд зөв юм. Тиймээс recursion ашиглан асуудлыг хэрхэн шийдвэрлэх талаар ярилцъя. Бид саваагаа янз бүрийн урттай сегментээр таслахыг оролдож болно. Дараа нь бид бүх саваа хайчилж авсны дараа үүссэн савааны үнийг тооцоолно. Гэхдээ бид саваа огтлох бүх аргыг хайх хэрэгтэй гэж хэлэх үед. Энэ ажиллагаа нь маш их өртөгтэй бөгөөд цаг хугацааны хувьд нарийн төвөгтэй байдаг. Тиймээс эдгээр тооцооллыг ямар нэгэн байдлаар багасгах хэрэгтэй. Хэрэв бид огтлох үед бариулын сегментийн зардлыг нэмбэл оновчлол байж болох юм. Дараа нь жижиг саваагаар асуудлыг дахин шийдээрэй. Гэхдээ энэ нь тийм ч сайн биш, энэ алгоритм нь экспоненциал цаг хугацаа шаарддаг хэвээр байна.

мөн үзнэ үү
Хамгийн том нийлбэр дэд дэд хэсэг

Савааны асуудлыг огтлох рекурсив томъёо нь

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)Учир нь бид АН-ын доороос дээш хандлагыг ашиглаж байгаа бөгөөд жижиг урттай савааны үнийг үргэлжлүүлэн шинэчилж байна. Энэ нь экспоненциаль хугацаанд шийдсэн асуудлыг олон гишүүнт цаг болгон багасгах боломжийг олгодог.

Сансрын нарийн төвөгтэй байдал

O (N), орон зайг DP хүснэгтэд хадгалахад ашиглаж байгаа тул.