كيفية حل مشكلة الحقيبة الكسرية في لغة C++

تشير مشكلة الحقيبة الكسرية في لغة C++ إلى تحديد طريقة لملء الحقيبة بعناصر ذات وزن معين وربح معين بحيث تحتوي الحقيبة على الحد الأقصى للقيمة دون تجاوز الحد الأقصى.

كيفية حل مشكلة الحقيبة الكسرية في لغة C++

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

خوارزمية لتنفيذ مشكلة الحقيبة الكسرية

يمكن فهم عمل خوارزمية Knapsack من خلال النقاط التالية:

• خذ صفيفين من الوزن والربح.
• اضبط الحد الأقصى لقيمة الكيس على W.
• تحديد الكثافة عن طريق أخذ نسبة كلا المعلمتين.
• فرز العناصر بترتيب تنازلي من حيث الكثافة.
• أضف القيم حتى تصبح <=W.

المنهج الجشع لحل مشكلة الحقيبة الكسرية

يهدف النهج الجشع إلى اتخاذ خيارات مثالية في كل خطوة، مما يؤدي إلى الحل المثالي في النهاية. فهو يحل المشكلات خطوة بخطوة مما يؤدي إلى الاستنتاجات بدلاً من التوصل إلى النتائج في النهاية فقط. هذا هو الكود المصدري لتنفيذ حل لمشكلة الحقيبة الكسرية في لغة C++:

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

الحد الأقصى للربح الذي تم تخزينه في الوجبة الخفيفة هو 580.

خاتمة

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