Різання стрижня  


Рівень складності Легко
Часто запитують у Амазонка Directi 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

 

Різання стрижняPinПояснення: Найкраще, що ми можемо зробити, це взяти 7 стрижнів довжини, що може дати нам найкращий результат із вартості 28.

Підхід  

Отже, для вирішення цієї проблеми можна думати про її рекурсивне вирішення. І підхід досить правильний. Тож давайте обговоримо, як ми можемо вирішити проблему за допомогою рекурсії. Ми можемо спробувати розрізати стрижень на відрізки різної довжини. Потім ми розраховуємо ціну на стрижні, які утворюються після обрізання всіх стрижнів. Але коли ми говоримо, що нам потрібно знайти всі способи розрізання стрижнів. Ця операція дуже затратна і має експоненціальну складність у часі. Тож нам потрібно якось зменшити ці обчислення. Оптимізацією може бути, якщо додати вартість сегмента стрижня на момент різання. Потім вирішіть проблему ще раз меншим стрижнем. Але це недостатньо добре, цей алгоритм все одно займає експоненціальний час.

Дивись також
Найбільша сума суміжного підмасиву

Рекурсивна формула для проблеми різання стрижня така

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

Отже, якщо взяти короткий момент, щоб побачити, як працює алгоритм. Ми бачимо, що ми викликаємо cuttingRod (n-1), cuttingRod (n-2),…, cuttingRod (1), який потім знову продовжує викликати cuttingRod. Оскільки cutRod (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

Код 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.