اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدمشكلة حقيبة الظهر هي إحدى مسائل تحسين الموارد في نظرية التعقيد، حيث يتم تحديد مجموعة من العناصر لكل منها وزن وقيمة، ويجب اختيار العناصر بحيث لا يتجاوز الوزن الإجمالي حدًا معينًا وتكون القيمة الإجمالية أكبر ما يمكن.
الخوارزمية الجشعة لحل مشكلة حقيبة الظهر تتضمن ترتيب العناصر بترتيب تنازلي لقيمتها النسبية (Di = vi/wi) ومن ثم تعبئة حقيبة الظهر بالوحدات بدءًا من الأعلى قيمة حتى الوصول إلى الحد الأقصى للوزن.
الحل الجشع يعتمد على اتخاذ قرارات محلية لتحقيق أفضل قيمة نسبية في كل خطوة، بينما البرمجة الديناميكية تعتمد على بناء الحلول الجزئية من الحلول السابقة باستخدام صيغة تكرارية لتحقيق الحل الأمثل.
الخوارزمية الجشعة تكون أسرع وأسهل في التنفيذ ولكنها قد لا تعطي الحل الأمثل في جميع الحالات. البرمجة الديناميكية تضمن الوصول إلى الحل الأمثل ولكنها تتطلب وقتًا وذاكرة أكبر.