قطع قضيب


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون Directi Flipkart جوجل JP مورغان 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

لذا ، إذا أخذنا لحظة وجيزة لنرى كيف تعمل الخوارزمية. يمكننا أن نرى أننا نطلق على cutRod (n-1) ، cutRod (n-2) ، ... ، cutRod (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

كود جافا لقضيب القطع

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 تصاعديًا ونواصل تحديث تكلفة قضبان الطول الأصغر. هذا يسمح بتقليل المشكلة التي تم حلها في الوقت الأسي إلى وقت كثير الحدود.

تعقيد الفضاء

على)، لأنه يتم استخدام المساحة لتخزين القيم في جدول DP.