حقيبة محسّنة من حيث المساحة

يستهلك الجدول الكامل ذاكرة مقدارها n مضروبة في cap، وقد يتضخم ذلك مع المدخلات الكبيرة. ويقلّل تحسين الذاكرة هذا الاستخدام إلى صف واحد تعيد استخدامه.

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

احتفظ بمصفوفة dp واحدة طولها cap+1. وأثناء معالجة كل عنصر، اكتب فوق قيمها في مواضعها لتمثيل الصف الجديد.

إذا مررت على السعة من اليسار إلى اليمين، فقد تكون dp[w - wt[i]] قد حُدّثت للعنصر نفسه. وهذا سيسمح لك بأخذ العنصر i مرتين.

الحل هو تكرار السعة من الأعلى إلى الأسفل. ويضمن المرور بالعكس أن dp[w - wt[i]] ما زالت تحتوي على قيمة العنصر السابق.

عند حساب dp[w]، يظل الفهرس الأصغر w - wt[i] من دون تحديث في هذه الجولة، ولذلك يعكس الصف السابق كما هو مطلوب.

لا يمكن للسعات الأصغر من wt[i] استيعاب العنصر، لذا تتوقف الحلقة عند wt[i]. ويوفّر تخطيها بعض الدورات غير الضرورية.

الحل الكامل هو حلقتان متداخلتان تعملان على مصفوفة واحدة. العناصر في الخارج، والسعة بالعكس في الداخل، وستظهر الإجابة تلقائيًا.

بعد معالجة جميع العناصر، تحتوي dp[cap] على القيمة القصوى. وهي القيمة نفسها التي سيعطيها الجدول ثنائي الأبعاد، لكن باستخدام ذاكرة أقل بكثير.

لم تسرّع الخوارزمية؛ فما زالت تنفّذ عملًا من رتبة n مضروبة في cap. لقد قلّلت فقط الذاكرة من تربيعية إلى خطية.

تنقذك هذه الحيلة عندما تكون cap كبيرة، وعندما تتجاوز الشبكة ثنائية الأبعاد حد الذاكرة. إنها من أساسيات المسابقات التي تستحق الحفظ.

اختبر القاعدة الأساسية لحقيبة الظهر أحادية البعد.

اختزلت الجدول ثنائي الأبعاد إلى مصفوفة واحدة، وكرّرت على السعة بالعكس للحفاظ على صحة الحل، فاستبدلت الذاكرة التربيعية بالخطية. 🚀