Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userمشكلة حقيبة الظهر هي إحدى مسائل تحسين الموارد في نظرية التعقيد، حيث يتم تحديد مجموعة من العناصر لكل منها وزن وقيمة، ويجب اختيار العناصر بحيث لا يتجاوز الوزن الإجمالي حدًا معينًا وتكون القيمة الإجمالية أكبر ما يمكن.
الخوارزمية الجشعة لحل مشكلة حقيبة الظهر تتضمن ترتيب العناصر بترتيب تنازلي لقيمتها النسبية (Di = vi/wi) ومن ثم تعبئة حقيبة الظهر بالوحدات بدءًا من الأعلى قيمة حتى الوصول إلى الحد الأقصى للوزن.
الحل الجشع يعتمد على اتخاذ قرارات محلية لتحقيق أفضل قيمة نسبية في كل خطوة، بينما البرمجة الديناميكية تعتمد على بناء الحلول الجزئية من الحلول السابقة باستخدام صيغة تكرارية لتحقيق الحل الأمثل.
الخوارزمية الجشعة تكون أسرع وأسهل في التنفيذ ولكنها قد لا تعطي الحل الأمثل في جميع الحالات. البرمجة الديناميكية تضمن الوصول إلى الحل الأمثل ولكنها تتطلب وقتًا وذاكرة أكبر.