Rod Cutting Problem

Q: لماذا تُعدّ مسألة تقطيع القضيب مسألة حقيبة ظهر غير محدودة؟

تعامل مع طول كل قطعة k على أنه عنصر وزنه k وقيمته prices[k-1] ، مع توفر عدد غير محدود من النسخ، ومع القضيب على أنه حقيبة سعتها n يجب ملؤها بالكامل. عندئذٍ تكون أفضل قيمة إجمالية للعناصر هي أفضل سعر للقضيب.

Q: كيف تجد الموضع الذي تقطع عنده القضيب؟

خزّن، لكل طول، أول قطعة k حققت أفضل سعر له. ابدأ من الطول n: اقطع قطعة بالطول المخزّن، وانتقل إلى الطول المتبقي، وكرّر ذلك حتى يصل إلى 0. تشكّل القطع خطة مثلى واحدة.

متوسطالبرمجة الديناميكية

+10

لديك قضيب طوله n، حيث n = prices.length. تُباع قطعة طولها k مقابل prices[k-1]. يمكنك تقطيع القضيب إلى قطع ذات أطوال صحيحة كما تشاء، أو بيعه قطعة واحدة. أرجِع أكبر مبلغ يمكنك كسبه من بيع القضيب كله.

الدالة

cutRod(prices: integer-array) → integer

pricesinteger-array: ‏<code>prices[k-1]</code> هو سعر قطعة طولها <code>k</code>؛ طول القضيب هو <code>prices.length</code>
تُرجعinteger: أكبر مبلغ من المال يمكن للقضيب بأكمله أن يجنيه

القيود

1 ≤ prices.length ≤ 1000
1 ≤ prices[i] ≤ 10⁵

أمثلة

المدخلات: prices = [2, 5, 7, 8]
المخرجات: 10
الشرح: يُباع قطعتان طول كل منهما 2 مقابل 5 + 5 = 10. يدرّ بيع القضيب كاملًا 8، بينما تدرّ قطعة بطول 1 وأخرى بطول 3 مبلغ 2 + 7 = 9.

سؤال إضافي

ماذا لو كان بإمكانك قطع القضيب m مرات كحد أقصى؟ ما الذي تحتاج كل خانة في الجدول إلى معرفته عندئذ؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

يمكن تقطيع قضيب طوله n بـ 2^(n-1) طريقة. لا تحتاج أبدًا إلى تجربة جميع الطرق: فمهما كان طول القطعة الأولى، يكون الباقي قضيبًا أقصر يطرح السؤال نفسه. لذلك لا يوجد سوى n+1 إجابة، واحدة لكل طول، وحسابها بدءًا من الأقصر يستغرق O(n²) خطوة.

جرّب كل طول للقطعة الأولى

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

مهما كانت الخطة، يكون طول القطعة عند الطرف الأيسر هو k، من 1 إلى طول القضيب، وتحقق ربحًا قدره prices[k-1]؛ أما الجزء المتبقي من الخطة فيقطع قضيبًا طوله length-k. لذلك تكون قيمة best(length) هي 0 عندما يكون الطول 0، وإلا فهي أكبر قيمة لـ prices[k-1] + best(length-k) لجميع قيم k، حيث تعني k = length بيع القضيب كاملًا. لكل خطة قطعة أولى، لذا تشمل هذه القيمة العظمى جميع الخطط.

يتفرع كل استدعاء إلى جميع الأطوال الأقصر، لذا يتضاعف عدد الاستدعاءات مع كل وحدة من الطول: ينتج عن قضيب طوله 40 نحو 2^40، أو 10^12، استدعاء.

الخوارزمية

اكتب best(length)، التي تُرجع 0 عندما يكون الطول 0.
لكل قطعة أولى k من 1 إلى length، احسب prices[k-1] + best(length-k).
أعِد أكبر قيمة من هذه القيم.
أعِد best(n).

def cutRod(prices):
    # The most money a rod of this length can earn
    def best(length):
        top = 0
        for piece in range(1, length + 1):
            # sell a first piece of this length, then cut the rest as well as possible
            top = max(top, prices[piece - 1] + best(length - piece))
        return top

    return best(len(prices))

أفضل سعر لكل طول، بدءًا من الأقصر

الفكرة

تعيد الاستدعاءات العودية حساب القيم نفسها: يطلب best(2) كلٌّ من best(3) وbest(4) وكل طول أكبر. لا يوجد سوى n+1 طولًا، لذا احسب كلًّا منها مرة واحدة وخزّنها في مصفوفة best. لا يقرأ الطول إلا أطوالًا أقصر منه، لذا فإن ملء المصفوفة بدءًا من 0 تصاعديًا يعني أن كل قيمة ستكون جاهزة عند قراءتها.

بالنسبة إلى [2, 5, 7, 8]: قيمة best[1] هي 2، وقيمة best[2] هي الأكبر بين 2 + 2 و5، أي 5، وقيمة best[3] هي 7، أما قيمة best[4] فهي الأكبر بين 2 + 7 و5 + 5 و7 + 2 و8، أي 10.

على عكس مسألة حقيبة الظهر 0/1، قد تحتوي best[len-k] بالفعل على قطع بطول k، وهذا ما تريده، لأن بإمكانك تقطيع الطول إلى قطع بهذا الطول أي عدد من المرات. يجرّب الطول len أولى القطع بطول len: أي n(n+1)/2 خطوة إجمالًا، ونحو 5 × 10^5 لقضيب طوله 1000.

الخوارزمية

أنشئ best بحيث يحتوي على n + 1 خانة، جميعها 0.
لكل length من 1 إلى n، جرّب كل قطعة أولى k من 1 إلى length.
احسب prices[k-1] + best[length-k] واحتفظ بأكبر قيمة في best[length].
أعِد best[n].

def cutRod(prices):
    n = len(prices)
    # best[length]: the most money a rod of that length can earn
    best = [0] * (n + 1)
    for length in range(1, n + 1):
        for piece in range(1, length + 1):
            # a first piece of this length, then the best for what is left
            earned = prices[piece - 1] + best[length - piece]
            if earned > best[length]:
                best[length] = earned
    return best[n]

أخطاء شائعة وحالات حدّية

قراءة prices[k] عند الطول k. يؤدي ذلك إلى تسعير كل قطعة بطول يزيد وحدة واحدة، ويتجاوز نهاية المصفوفة عند k = n؛ استخدم prices[k-1].
إغفال k = length، أي القطعة غير المقطوعة. عندها تظل best[1] تساوي 0، وتكون قيمة [1, 3, 8] هي 3 بدلًا من 8.
التقطيع جشعًا وفق أفضل سعر لكل وحدة. في [2, 7, 11, 13]، يحقق الطول 3 أعلى سعر لكل وحدة، لكن الحصول على 11 منه و2 من الباقي يعطي 13، بينما تعطي قطعتان بطول 2 قيمة 14.
استخدام التخزين المؤقت بطريقة تنازلية في Python. يظل التكرار متداخلًا بعمق يساوي طول القضيب: فقضيب طوله 1000 يؤدي إلى 1001 استدعاء متداخل، متجاوزًا الحد الافتراضي البالغ 1000. املأ المصفوفة تصاعديًا من الأسفل إلى الأعلى.

أسئلة شائعة4

ما هو التعقيد الزمني لمسألة تقطيع القضيب؟

يستغرق الجدول زمنًا مقداره O(n²) وذاكرة مقدارها O(n): يجرب الطول len أولى القطع len، أي n(n+1)/2 محاولة إجمالًا. من دون تخزين الإجابات، يُجري الاستدعاء التكراري 2^n استدعاءً بالضبط لقضيب طوله n، إذ يستدعي كل طول جميع الأطوال الأقصر منه.

لماذا تُعدّ مسألة تقطيع القضيب مسألة حقيبة ظهر غير محدودة؟

تعامل مع طول كل قطعة k على أنه عنصر وزنه k وقيمته prices[k-1]، مع توفر عدد غير محدود من النسخ، ومع القضيب على أنه حقيبة سعتها n يجب ملؤها بالكامل. عندئذٍ تكون أفضل قيمة إجمالية للعناصر هي أفضل سعر للقضيب.

كيف تجد الموضع الذي تقطع عنده القضيب؟

خزّن، لكل طول، أول قطعة k حققت أفضل سعر له. ابدأ من الطول n: اقطع قطعة بالطول المخزّن، وانتقل إلى الطول المتبقي، وكرّر ذلك حتى يصل إلى 0. تشكّل القطع خطة مثلى واحدة.

كيف يتغير الحل إذا كان كل قطعٍ يكلّف مالًا؟

بيع القضيب كاملًا لا يتطلب أي قطع، بينما تستلزم كل قطعة أولى أخرى إجراء قطع واحد. لذا تصبح best[len] القيمة الأكبر بين prices[len-1] وأكبر قيمة لـ prices[k-1] + best[len-k] - cost عندما تكون k أقل من len. ويبقى باقي الجدول كما هو.

def cutRod(prices):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

وسيط

prices = [2, 5, 7, 8]

الإخراج المتوقع