كيفية حل مشكلة الحقيبة مع البرمجة الديناميكية

تحديث: اقرأ عن تحسين تعقيد مساحة حل البرمجة الديناميكية في مقالتي للمتابعة هنا.

مشكلة Knapsack مشكلة مثيرة للاهتمام حقًا في المجموعات التوافقية - على سبيل المثال Wikipedia ،

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

من ويكيبيديا ، نرى أن هناك بعض الاختلافات في مشكلة Knapsack: 0-1 knapsack ، knapsack knetack ، و knackack غير محدود. اليوم ، سنركز على أكثر الأشكال شيوعًا (وأبسطها): مشكلة حقيبة الظهر من 0 إلى 1.

الصياغة الأكثر إثارة للاهتمام والقليلة لمشكلة الحقيبة 0-1 هي:

ضع في اعتبارك أن لصًا دخل إلى المنزل لسرقة وهو يحمل حقيبة ظهر. يوجد عدد ثابت من العناصر في المنزل - لكل منها وزنه وقيمته - المجوهرات ، مع وزن أقل وأعلى قيمة مقابل الجداول ، مع قيمة أقل ولكن ثقيل للغاية. لإضافة الوقود إلى النار ، يمتلك اللص حقيبة ظهر قديمة ذات سعة محدودة. من الواضح أنه لا يستطيع تقسيم الطاولة إلى نصف أو مجوهرات إلى 3/4. هو إما يأخذها أو يتركها. مصدر

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

البرمجة الديناميكية

سنحل هذه المشكلة من خلال البرمجة الديناميكية. تتطلب البرمجة الديناميكية بنية أساسية مثالية ومشاكل فرعية متداخلة ، وكلاهما موجود في مشكلة حقيبة الظهر 0-1 ، كما سنرى.

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

تفاصيل المشكلة

افترض أن لدينا حقيبة تحمل على الظهر والتي يمكن أن تعقد كثافة وزنها = 10 وحدات الوزن. لدينا ما مجموعه int = 4 عناصر للاختيار من بينها ، والتي يتم تمثيل قيمها بواسطة صفيف int [] val = {10 ، 40 ، 30 ، 50} والأوزان الممثلة بمصفوفة int [] wt = {5، 4 ، 63}.

نظرًا لأن هذه هي مشكلة حقيبة الظهر 0-1 ، يمكننا إما تضمين عنصر في حقيبة الظهر الخاصة بنا أو استبعادها ، ولكن لا يمكننا تضمين جزء منها أو تضمينها عدة مرات.

المحلول

الخطوة 1:

أولاً ، نقوم بإنشاء صفيف ثنائي الأبعاد (أي جدول) من الصفوف n + 1 والأعمدة w + 1.

يمثل رقم الصف الأول مجموعة جميع العناصر من الصفوف 1 - i. على سبيل المثال ، تفترض القيم في الصف 3 أن لدينا فقط العناصر 1 و 2 و 3.

يمثل رقم العمود j قدرة وزن الحقيبة الخاصة بنا. لذلك ، فإن القيم الموجودة في العمود 5 ، على سبيل المثال ، تفترض أن حقيبة الظهر يمكن أن تحتوي على 5 وحدات وزن.

عند تجميع كل شيء معًا ، يمثل إدخال في الصف i ، العمود j الحد الأقصى للقيمة التي يمكن الحصول عليها باستخدام العناصر 1 و 2 و 3 ... i في حقيبة تحمل على الظهر تحمل وحدات وزن j.

دعنا ندعو حصيرة الجدول لدينا للمصفوفة. لذلك ، int [] [] mat = int جديدة [n + 1] [w + 1].

الخطوة 2:

يمكننا على الفور البدء في ملء بعض الإدخالات في جدولنا: الحالات الأساسية ، والتي يكون الحل تافها. على سبيل المثال ، في الصف 0 ، عندما لا يكون لدينا عناصر للاختيار من بينها ، يجب أن تكون القيمة القصوى التي يمكن تخزينها في أي حقيبة ظهر هي 0. وبالمثل ، في العمود 0 ، في حقيبة تحمل على الظهر يمكن أن تحتوي على 0 وحدة من الوزن ، القيمة القصوى التي يمكن تخزينها في 0. (نحن نفترض أنه لا توجد عناصر قيمة ، لا قيمة لها.)

يمكننا القيام بذلك مع 2 للحلقات:

الخطوة 3 (جوهر المشكلة):

الآن ، نريد أن نبدأ نشر جدول أعمالنا. كما هو الحال مع جميع حلول البرمجة الديناميكية ، في كل خطوة ، سوف نستفيد من حلولنا للمشاكل الفرعية السابقة.

سأقوم أولاً بوصف المنطق ، قبل عرض مثال ملموس.

العلاقة بين القيمة في الصف الأول والعمود ي والقيم إلى المشكلات الفرعية السابقة هي كما يلي:

تذكر أنه في الصف الأول والعمود j ، نتصدى لمشكلة فرعية تتكون من العناصر 1 و 2 و 3 ... i مع حقيبة تحمل على الظهر سعة j. هناك خياران في هذه المرحلة: يمكننا إما تضمين العنصر i أو لا. لذلك ، نحتاج إلى مقارنة الحد الأقصى للقيمة التي يمكننا الحصول عليها مع أو بدون العنصر i.

يمكن العثور على الحد الأقصى للقيمة التي يمكننا الحصول عليها دون عنصر i في الصف i-1 ، العمود j. هذا الجزء سهل. التعليل واضح ومباشر: أيًا كان الحد الأقصى للقيمة التي يمكننا الحصول عليها باستخدام العناصر 1 و 2 و 3 ... يجب أن أكون واضحًا بنفس القيمة القصوى التي يمكننا الحصول عليها مع العناصر 1 و 2 و 3 ... i - 1 ، إذا اخترنا عدم تضمين العنصر i .

لحساب الحد الأقصى للقيمة التي يمكننا الحصول عليها مع العنصر i ، نحتاج أولاً إلى مقارنة وزن العنصر i بسعة وزن الحقيبة. من الواضح ، إذا كان العنصر الأول يزن أكثر مما يمكن أن تحمله الحقيبة ، فلن نتمكن من تضمينه ، لذلك ليس من المنطقي إجراء الحساب. في هذه الحالة ، يكون حل هذه المشكلة ببساطة هو الحد الأقصى للقيمة التي يمكن الحصول عليها دون العنصر الأول (أي القيمة الموجودة في الصف أعلاه ، في نفس العمود).

ومع ذلك ، لنفترض أن العنصر الذي أزنه أقل من قدرة الحقيبة. وبالتالي ، لدينا خيار تضمينه ، إذا كان من المحتمل أن يزيد الحد الأقصى للقيمة التي يمكن الحصول عليها. الحد الأقصى للقيمة التي يمكن الحصول عليها عن طريق تضمين العنصر i هو = قيمة العنصر i نفسه + الحد الأقصى للقيمة التي يمكن الحصول عليها مع السعة المتبقية من الحقيبة. من الواضح أننا نريد الاستفادة الكاملة من قدرة حقيبة الظهر الخاصة بنا ، وعدم ترك أي سعة متبقية تضيع.

لذلك ، في الصف الأول والعمود j (الذي يمثل الحد الأقصى للقيمة التي يمكن أن نحصل عليها هناك) ، سنختار إما الحد الأقصى للقيمة التي يمكننا الحصول عليها دون العنصر i ، أو الحد الأقصى للقيمة التي يمكننا الحصول عليها مع العنصر i ، أيهما أكبر .

إليك مثال ملموس على ما أقصده.

في الصف 3 (البند 2) ، والعمود 5 (سعة حقيبة الظهر 4) ، يمكننا اختيار إما تضمين البند 2 (الذي يزن 4 وحدات) أم لا. إذا اخترنا عدم إدراجه ، فإن القيمة القصوى التي يمكننا الحصول عليها هي نفسها كما لو كان لدينا البند 1 فقط للاختيار من بينها (الموجود في الصف أعلاه ، أي 0). إذا أردنا تضمين العنصر 2 ، فإن الحد الأقصى للقيمة التي يمكننا الحصول عليها مع البند 2 هو قيمة البند 2 (40) + القيمة القصوى التي يمكن الحصول عليها مع السعة المتبقية (والتي هي 0 ، لأن حقيبة الظهر ممتلئة تمامًا بالفعل) .

في الصف 3 (البند 2) ، والعمود 10 (سعة الحقيبة 9) ، مرة أخرى ، يمكننا اختيار إما تضمين البند 2 أو لا. إذا اخترنا عدم القيام بذلك ، فستكون القيمة القصوى التي يمكننا الحصول عليها هي نفسها الموجودة في الصف أعلاه في نفس العمود ، أي 10 (من خلال تضمين البند 1 فقط ، والذي له قيمة 10). إذا قمنا بتضمين البند 2 ، فلدينا سعة حقيبة متبقية تبلغ 9 - 4 = 5. يمكننا معرفة الحد الأقصى للقيمة التي يمكن الحصول عليها بسعة 5 من خلال النظر في الصف أعلاه ، في العمود 5. وبالتالي ، الحد الأقصى القيمة التي يمكن الحصول عليها من خلال تضمين العنصر 2 هي 40 (قيمة العنصر 2) + 10 = 50.

نختار العدد الأكبر من 50 مقابل 10 ، وبالتالي فإن الحد الأقصى للقيمة التي يمكننا الحصول عليها باستخدام البندين 1 و 2 ، بسعة حقيبة تبلغ 9 ، هي 50.

يمكن التعبير عن الخوارزمية بلغة Java مثل هذا:

الخطوة 4 (الحل النهائي):

بمجرد ملء الجدول ، يمكن العثور على الحل النهائي في الصف الأخير في العمود الأخير ، والذي يمثل الحد الأقصى للقيمة التي يمكن الحصول عليها مع جميع العناصر والقدرة الكاملة لحقيبة الظهر.

عودة حصيرة [ن] [ث] ؛

كود العمل:

ملاحظة: هنا ، قمت بطباعة الإجابة النهائية بدلاً من إعادتها ، لأن كل شيء موجود تحت الفراغ الثابت العام الرئيسي.

شكرا للقراءة!