إصلاح ترتيب طبقات البرمجة الديناميكية المضغوطة

افهم الأسباب المحتملة

• أزال ضغط التخزين بُعد العنصر، لكن ترتيب الحلقة يقرأ طبقة العنصر الحالي بدلا من الطبقة السابقة.
• لم تعد تهيئة حالات الأساس أو طريقة حفظ السابقات توافق عقود المقدار الدقيق أو الحد الأقصى وإعادة الاستخدام المعلنة. وقد يحل جدول يبدو صحيحا مسألة مختلفة.

صِف الحالة غير المضغوطة بالكلمات

في حقيبة صفر-واحد، عرّف best[i,c] بأنها أقصى قيمة باستخدام أول i عناصر فقط، بوزن كلي لا يتجاوز c. يجب أن يقرأ أخذ العنصر i الخانة best[i-1,c-weight]، لأن ذلك العنصر لم يُستخدم بعد في طبقة المصدر. ويقرأ تجاوز العنصر best[i-1,c]. يحدد هذا الوصف الاعتماد قبل أي تحسين. وإذا سمحت المسألة بنسخ غير محدودة أو اشترطت وزنا دقيقا، فأعد وصف الحالة وحالات الأساس أولا. لا تستنتج الدلالة من اتجاه حلقة تركها تنفيذ سابق.

تتبّع الطبقة المفهومية التي تمثلها كل قراءة

يحدث تنفيذ الصف الواحد السعات تنازليا، حتى لا تكون خانة c-weight قد استُبدلت للعنصر الحالي بعد. يتيح التكرار التصاعدي للعنصر ذي الوزن 2 تحسين السعة 2، ثم قراءة تلك القيمة الجديدة أثناء تحديث السعة 4، فيستخدم العنصر نفسه مرة أخرى. يقارن البرنامج مرجعا واضحا ذا بُعدين بالصف التنازلي المصحح. وكلاهما حساب محلي صحيح؛ ويساعد اتفاقهما على كشف أخطاء الضغط دون تقديم النسخة التصاعدية المعيبة كحل تعليمي قابل للتشغيل. يبقي هذا التشخيص العنصر والسعة صغيرين وبسيطين بما يكفي لفحصهما يدويا.

def table_reference(items, capacity):
    previous = [0] * (capacity + 1)
    for weight, value in items:
        current = previous[:]
        for c in range(weight, capacity + 1):
            current[c] = max(previous[c], previous[c - weight] + value)
        previous = current
    return previous[capacity]

def compressed(items, capacity):
    best = [0] * (capacity + 1)
    for weight, value in items:
        for c in range(capacity, weight - 1, -1):
            best[c] = max(best[c], best[c - weight] + value)
    return best[capacity]

fixture = [(2, 3)]
print(table_reference(fixture, 4))
print(compressed(fixture, 4))

3
3

افحص التهيئة واستعادة الحل كعقدين منفصلين

تصح التهيئة بالصفر لمسألة قيمة قصوى بوزن لا يتجاوز السعة عندما يُسمح بالاختيار الفارغ. أما الوزن الدقيق فيحتاج إلى علامة منفصلة للسعات الموجبة غير القابلة للوصول؛ وإلا أمكن للجدول اختلاق حل بتمديد حالة مستحيلة. وتحتاج مسائل الكلفة الدنيا كذلك إلى اللانهاية إلا عند حالات الأساس الصحيحة. تضيف الاستعادة التزاما آخر: يجب أن تحدد السابقات الانتقال وطبقة العناصر اللذين أنشآ كل قيمة. قد يكتب الصف المضغوط فوق ذلك التاريخ حتى لو بقي الهدف النهائي صحيحا. احفظ الطبقات المناسبة، أو أعد حساب الاختيارات عن قصد، أو استخدم طريقة استعادة مبرهنة، بدلا من اتباع أي قيمة سابقة بقيت عرضا.

عد المجموعات الجزئية باستقلال على عينات صغيرة

ولّد قوائم عناصر صغيرة، وعد كل مجموعة جزئية، واجمع وزنها وقيمتها مباشرة. قارن أفضل قيمة مقبولة بالتنفيذين. أدرج عنصرا واحدا، وعناصر مختلفة ذات قيم متساوية، وسعة صفرا، وعنصرا أثقل من السعة، وعناصر اختيارية سالبة القيمة عندما يُسمح بالاختيار الفارغ. ولأي نتيجة مستعادة، تحقّق من عدم استخدام أي نسخة من المدخل أكثر من مرة، ومن صلاحية الوزن الكلي، ومن مساواة القيمة للهدف. قد تفوت اختبارات القيم الفريدة وحدها إعادة استخدام نسخة عرضا. أبق العد كله محدودا؛ فلا يحتاج التشخيص إلى اختبار معياري توافقي كبير.

امنع تكرار المشكلة

• أبق وصف الحالة وثابت قراءة الطبقات وترتيب الحلقة والتهيئة معا أثناء المراجعة. احتفظ بالمثال المضاد لإعادة استخدام عنصر واحد، وتحقّق من سلاسل السابقات مستقلة عن قيم الهدف.