الحقيبة هنا تشبه الحاوية أو الحقيبة. لنفترض أننا قدمنا ​​بعض العناصر التي لها بعض الأوزان أو الأرباح. علينا أن نضع بعض العناصر في الحقيبة بطريقة تؤدي القيمة الإجمالية إلى تحقيق أقصى قدر من الربح.

على سبيل المثال، وزن الحاوية 20 كجم. علينا أن نختار العناصر بطريقة تجعل مجموع وزن العناصر إما أصغر من أو يساوي وزن الحاوية، ويجب أن يكون الربح هو الحد الأقصى.

هناك نوعان من مشاكل الحقيبة:

• 0/1 مشكلة الحقيبة
• مشكلة الحقيبة الكسرية

سنناقش كلا المشكلتين واحدة تلو الأخرى. أولاً، سوف نتعرف على مشكلة الحقيبة 0/1.

ما هي مشكلة الحقيبة 0/1؟

تعني مشكلة حقيبة الظهر 0/1 أن العناصر إما مملوءة بالكامل أو لا توجد عناصر مملوءة في الحقيبة. على سبيل المثال، لدينا عنصرين بوزن 2 كجم و3 كجم على التوالي. إذا اخترنا عنصرًا بوزن 2 كجم، فلا يمكننا اختيار عنصر بوزن 1 كجم من عنصر بوزن 2 كجم (العنصر غير قابل للقسمة)؛ علينا أن نختار العنصر 2 كجم بالكامل. هذه مشكلة حقيبة 0/1 حيث إما أن نختار العنصر بالكامل أو نختار هذا العنصر. تم حل مشكلة حقيبة الظهر 0/1 عن طريق البرمجة الديناميكية.

ما هي مشكلة الحقيبة الكسرية؟

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

مثال على مشكلة حقيبة الظهر 0/1.

النظر في مشكلة وجود الأوزان والأرباح هي:

الأوزان: {3، 4، 6، 5}

الأرباح: {2، 3، 1، 4}

وزن الحقيبة 8 كجم

عدد العناصر هو 4

يمكن حل المشكلة المذكورة أعلاه باستخدام الطريقة التالية:

س_أنا= {1، 0، 0، 1}

= {0، 0، 0، 1}

اجمل ابتسامة في العالم

= {0، 1، 0، 1}

ما ورد أعلاه هو المجموعات الممكنة. يشير الرقم 1 إلى أنه تم اختيار العنصر بالكامل، بينما يعني الرقم 0 أنه لم يتم اختيار أي عنصر. نظرًا لوجود 4 عناصر، فإن المجموعات الممكنة ستكون:

2⁴= 16؛ لذا. هناك 16 مجموعة محتملة يمكن إجراؤها باستخدام المشكلة المذكورة أعلاه. بمجرد الانتهاء من جميع المجموعات، علينا أن نختار المجموعة التي توفر أقصى قدر من الربح.

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

كيف يمكن حل هذه المشكلة باستخدام منهج البرمجة الديناميكية؟

أولاً،

نقوم بإنشاء مصفوفة كما هو موضح أدناه:

في المصفوفة أعلاه، تمثل الأعمدة الوزن، أي 8. وتمثل الصفوف أرباح العناصر وأوزانها. هنا لم نأخذ الوزن 8 مباشرة، فقد تم تقسيم المشكلة إلى مسائل فرعية، أي 0، 1، 2، 3، 4، 5، 6، 7، 8. وسيتم حفظ حل المسائل الفرعية في الملف سيتم تخزين الخلايا والإجابة على المشكلة في الخلية النهائية. أولاً نكتب الأوزان ترتيباً تصاعدياً والأرباح حسب أوزانها الموضحة أدناه:

في_أنا= {3، 4، 5، 6}

ص_أنا= {2، 3، 4، 1}

سيكون الصف الأول والعمود الأول 0 لأنه لا يوجد عنصر لـ w=0

عندما i = 1، W = 1

في₁= 3؛ نظرًا لأن لدينا عنصرًا واحدًا فقط في المجموعة بوزن 3، لكن سعة الحقيبة هي 1. لا يمكننا ملء العنصر الذي يبلغ 3 كجم في الحقيبة ذات السعة 1 كجم، لذا أضف 0 عند M[1] [1] كما هو موضح أدناه :

عندما أنا = 1، ث = 2

في₁= 3؛ نظرًا لأن لدينا عنصرًا واحدًا فقط في المجموعة بوزن 3، ولكن سعة الحقيبة هي 2. لا يمكننا ملء العنصر الذي يبلغ 3 كجم في الحقيبة ذات السعة 2 كجم، لذا أضف 0 عند M[1] [2] كما هو موضح أدناه :

عندما i=1، W=3

في₁= 3؛ نظرًا لأن لدينا عنصرًا واحدًا فقط في المجموعة بوزن يساوي 3، ووزن الحقيبة أيضًا 3؛ لذلك، يمكننا ملء الحقيبة بعنصر وزنه يساوي 3. ونضع ربحًا يتوافق مع الوزن 3، أي 2 عند M[1][3] كما هو موضح أدناه:

عندما = 1، W = 4

_W1= 3؛ نظرًا لأن لدينا عنصرًا واحدًا فقط في المجموعة بوزن يساوي 3، ووزن الحقيبة هو 4؛ لذلك، يمكننا ملء الحقيبة بعنصر وزنه يساوي 3. ونضع ربحًا يتوافق مع الوزن 3، أي 2 عند M[1][4] كما هو موضح أدناه:

عندما = 1، W = 5

_W1= 3؛ نظرًا لأن لدينا عنصرًا واحدًا فقط في المجموعة بوزن يساوي 3، ووزن الحقيبة هو 5؛ لذلك، يمكننا ملء الحقيبة بعنصر وزنه يساوي 3. ونضع ربحًا يتوافق مع الوزن 3، أي 2 عند M[1][5] كما هو موضح أدناه:

عندما =1، W=6

_W1= 3؛ نظرًا لأن لدينا عنصرًا واحدًا فقط في المجموعة بوزن يساوي 3، ووزن الحقيبة هو 6؛ لذلك، يمكننا ملء الحقيبة بعنصر وزنه يساوي 3. ونضع ربحًا يتوافق مع الوزن 3، أي 2 عند M[1][6] كما هو موضح أدناه:

عندما = 1، W = 7

_W1= 3؛ نظرًا لأن لدينا عنصرًا واحدًا فقط في المجموعة بوزن يساوي 3، ووزن الحقيبة هو 7؛ لذلك، يمكننا ملء الحقيبة بعنصر وزنه يساوي 3. ونضع ربحًا يتوافق مع الوزن 3، أي 2 عند M[1][7] كما هو موضح أدناه:

عندما =1، ث =8

_W1= 3؛ نظرًا لأن لدينا عنصرًا واحدًا فقط في المجموعة بوزن يساوي 3، ووزن الحقيبة هو 8؛ لذلك، يمكننا ملء الحقيبة بعنصر وزنه يساوي 3. ونضع ربحًا يتوافق مع الوزن 3، أي 2 عند M[1][8] كما هو موضح أدناه:

الآن تزداد قيمة 'i' وتصبح 2.

عندما = 2، W = 1

الوزن المقابل للقيمة 2 هو 4، أي ث₂= 4. نظرًا لأن لدينا عنصرًا واحدًا فقط في المجموعة وزنه يساوي 4، ووزن الحقيبة هو 1. لا يمكننا وضع العنصر الذي وزنه 4 في الحقيبة، لذلك نضيف 0 عند M[2] [1] ] كما هو موضح أدناه:

عندما =2، ث = 2

الوزن المقابل للقيمة 2 هو 4، أي ث₂= 4. بما أن لدينا عنصرًا واحدًا فقط في المجموعة وزنه يساوي 4، ووزن الحقيبة هو 2. لا يمكننا وضع العنصر الذي وزنه 4 في الحقيبة، لذلك نضيف 0 عند M[2] [2] ] كما هو موضح أدناه:

عندما =2، ث = 3

الوزن المقابل للقيمة 2 هو 4، أي ث₂= 4. بما أن لدينا عنصرين في المجموعة بوزن 3 و4، ووزن الحقيبة هو 3. يمكننا وضع العنصر ذو الوزن 3 في الحقيبة، لذلك نضيف 2 عند M[2][3] كما هو موضح أدناه:

عندما =2، ث = 4

الوزن المقابل للقيمة 2 هو 4، أي ث₂= 4. بما أن لدينا عنصرين في المجموعة بوزن 3 و4، ووزن الحقيبة هو 4. يمكننا وضع قطعة بوزن 4 في الحقيبة لأن الربح المقابل للوزن 4 أكبر من القطعة التي لها وزن 3، لذلك نضيف 3 عند M[2][4] كما هو موضح أدناه:

عندما أنا = 2، ث = 5

الوزن المقابل للقيمة 2 هو 4، أي ث₂= 4. بما أن لدينا عنصرين في المجموعة بوزن 3 و4، ووزن الحقيبة هو 5. يمكننا أن نضع قطعة وزنها 4 في الحقيبة ويكون الربح المقابل للوزن 3، لذلك نضيف 3 عند M [2] [5] هو مبين على النحو التالي:

عندما = 2، W = 6

الوزن المقابل للقيمة 2 هو 4، أي ث₂= 4. بما أن لدينا عنصرين في المجموعة بوزن 3 و4، ووزن الحقيبة هو 6. يمكننا أن نضع قطعة وزنها 4 في الحقيبة ويكون الربح المقابل للوزن 3، لذلك نضيف 3 عند M [2] [6] هو مبين على النحو التالي:

عندما أنا = 2، ث = 7

الوزن المقابل للقيمة 2 هو 4، أي ث₂= 4. بما أن لدينا عنصرين في المجموعة بوزن 3 و4، ووزن الحقيبة هو 7. يمكننا أن نضع قطعة من الوزن 4 و3 في حقيبة وتكون الأرباح المقابلة للأوزان هي 2 و3؛ وبالتالي يكون إجمالي الربح 5، لذلك نضيف 5 عند M[2][7] كما هو موضح أدناه:

عندما = 2، W = 8

الوزن المقابل للقيمة 2 هو 4، أي ث₂= 4. بما أن لدينا عنصرين في المجموعة بوزن 3 و4، ووزن الحقيبة هو 7. يمكننا أن نضع قطعة من الوزن 4 و3 في حقيبة وتكون الأرباح المقابلة للأوزان هي 2 و3؛ وبالتالي يكون إجمالي الربح 5، لذلك نضيف 5 عند M[2][7] كما هو موضح أدناه:

الآن تزداد قيمة 'i' وتصبح 3.

عندما = 3، W = 1

dateformat.format جافا

الوزن المقابل للقيمة 3 هو 5، أي ث₃= 5. بما أن لدينا ثلاثة عناصر في المجموعة بأوزان 3 و4 و5، ووزن الحقيبة هو 1. لا يمكننا وضع أي من العناصر في الحقيبة، لذلك نضيف 0 عند M[3][ 1] كما هو موضح أدناه:

عندما أنا = 3، ث = 2

الوزن المقابل للقيمة 3 هو 5، أي ث₃= 5. بما أن لدينا ثلاثة عناصر في المجموعة بوزن 3 و4 و5، ووزن الحقيبة هو 1. لا يمكننا وضع أي من العناصر في الحقيبة، لذلك نضيف 0 عند M[3][ 2] كما هو موضح أدناه:

عندما كنت = 3، ث = 3

الوزن المقابل للقيمة 3 هو 5، أي ث₃= 5. بما أن لدينا ثلاثة عناصر في مجموعة الوزن 3 و4 و5 على التوالي ووزن الحقيبة هو 3. يمكن وضع العنصر الذي وزنه 3 في الحقيبة ويكون الربح المقابل للعنصر 2، لذلك نضيف 2 عند M[3][3] كما هو موضح أدناه:

عندما أنا = 3، ث = 4

الوزن المقابل للقيمة 3 هو 5، أي ث₃= 5. نظرًا لأن لدينا ثلاثة عناصر في مجموعة الوزن 3 و4 و5 على التوالي، ووزن الحقيبة هو 4. يمكننا الاحتفاظ بالعنصر الذي يحمل أيًا من الوزن 3 أو 4؛ الربح (3) الموافق للوزن 4 أكبر من الربح المقابل للوزن 3 لذلك نضيف 3 عند M[3][4] كما هو موضح أدناه:

عندما أنا = 3، ث = 5

الوزن المقابل للقيمة 3 هو 5، أي ث₃= 5. نظرًا لأن لدينا ثلاثة عناصر في مجموعة الوزن 3 و4 و5 على التوالي، ووزن الحقيبة هو 5. يمكننا الاحتفاظ بالعنصر الذي يحمل أيًا من الوزن 3 أو 4 أو 5؛ الربح (3) الموافق للوزن 4 أكبر من الربح المقابل للوزن 3 و5 لذلك نضيف 3 عند M[3][5] كما هو موضح أدناه:

عندما =3، ث = 6

الوزن المقابل للقيمة 3 هو 5، أي ث₃= 5. نظرًا لأن لدينا ثلاثة عناصر في مجموعة الوزن 3 و4 و5 على التوالي، ووزن الحقيبة هو 6. يمكننا الاحتفاظ بالعنصر الذي يحمل أيًا من الوزن 3 أو 4 أو 5؛ الربح (3) الموافق للوزن 4 أكبر من الربح المقابل للوزن 3 و5 لذلك نضيف 3 عند M[3][6] كما هو موضح أدناه:

عندما =3، ث = 7

الوزن المقابل للقيمة 3 هو 5، أي ث₃= 5. بما أن لدينا ثلاثة عناصر في مجموعة الوزن 3 و4 و5 على التوالي، ووزن الحقيبة هو 7. في هذه الحالة، يمكننا الاحتفاظ بكل من العناصر ذات الوزن 3 و4، وهو مجموع الربح سيكون مساوياً لـ (2 + 3)، أي 5، لذلك نضيف 5 عند M[3][7] كما هو موضح أدناه:

عندما أنا = 3، ث = 8

الوزن المقابل للقيمة 3 هو 5، أي ث₃= 5. بما أن لدينا ثلاثة عناصر في مجموعة الوزن 3 و4 و5 على التوالي، ووزن الحقيبة هو 8. في هذه الحالة، يمكننا الاحتفاظ بكل من عنصري الوزن 3 و4، أي مجموع الوزن سيكون الربح مساوياً لـ (2 + 3) أي 5، لذلك نضيف 5 عند M[3][8] كما هو موضح أدناه:

الآن تزداد قيمة 'i' وتصبح 4.

123فيلم

عندما = 4، W = 1

الوزن المقابل للقيمة 4 هو 6، أي ث₄= 6. بما أن لدينا أربعة عناصر في مجموعة الأوزان 3 و4 و5 و6 على التوالي، ووزن الحقيبة هو 1. وزن جميع العناصر أكبر من وزن الحقيبة، لذلك لا يمكننا إضافة أي عنصر في الحقيبة؛ لذلك، نضيف 0 عند M[4][1] كما هو موضح أدناه:

عندما كنت = 4، ث = 2

الوزن المقابل للقيمة 4 هو 6، أي ث₄= 6. بما أن لدينا أربعة عناصر في مجموعة الأوزان 3 و4 و5 و6 على التوالي، ووزن الحقيبة هو 2. وزن جميع العناصر أكبر من وزن الحقيبة، لذلك لا يمكننا إضافة أي عنصر في الحقيبة؛ لذلك، نضيف 0 عند M[4][2] كما هو موضح أدناه:

عندما كنت = 4، ث = 3

الوزن المقابل للقيمة 4 هو 6، أي ث₄= 6. بما أن لدينا أربعة عناصر في مجموعة الأوزان 3 و4 و5 و6 على التوالي، ووزن الحقيبة هو 3. يمكن وضع السلعة التي لها وزن 3 في الحقيبة والربح المقابل للحقيبة الوزن 4 هو 2، لذلك سنضيف 2 عند M[4][3] كما هو موضح أدناه:

عندما = 4، W = 4

الوزن المقابل للقيمة 4 هو 6، أي ث₄= 6. بما أن لدينا أربعة عناصر في مجموعة الأوزان 3 و4 و5 و6 على التوالي، ووزن الحقيبة هو 4. يمكن وضع السلعة التي لها وزن 4 في الحقيبة والربح المقابل لـ الوزن 4 هو 3، لذلك سنضيف 3 عند M[4][4] كما هو موضح أدناه:

عندما كنت = 4، ث = 5

الوزن المقابل للقيمة 4 هو 6، أي ث₄= 6. بما أن لدينا أربعة عناصر في مجموعة الأوزان 3 و4 و5 و6 على التوالي، ووزن الحقيبة هو 5. يمكن وضع السلعة التي لها وزن 4 في الحقيبة والربح المقابل للحقيبة الوزن 4 هو 3، لذلك سنضيف 3 عند M[4][5] كما هو موضح أدناه:

عندما = 4، W = 6

الوزن المقابل للقيمة 4 هو 6، أي ث₄= 6. بما أن لدينا أربعة عناصر في مجموعة الأوزان 3 و4 و5 و6 على التوالي، ووزن الحقيبة هو 6. في هذه الحالة، يمكننا وضع العناصر في الحقيبة إما بوزن 3، 4 ، 5 أو 6 لكن الربح، أي 4 المقابل للوزن 6، هو الأعلى بين جميع العناصر؛ لذلك نضيف 4 عند M[4][6] كما هو موضح أدناه:

عندما = 4، W = 7

الوزن المقابل للقيمة 4 هو 6، أي ث₄= 6. بما أن لدينا أربعة عناصر في مجموعة الأوزان 3 و4 و5 و6 على التوالي، ووزن الحقيبة هو 7. هنا، إذا أضفنا عنصرين من الأوزان 3 و4 فإنه سينتج الحد الأقصى الربح، أي (2 + 3) يساوي 5، لذلك نضيف 5 عند M[4][7] كما هو موضح أدناه:

عندما كنت = 4، ث = 8

الوزن المقابل للقيمة 4 هو 6، أي ث₄= 6. بما أن لدينا أربعة عناصر في مجموعة الأوزان 3 و4 و5 و6 على التوالي، ووزن الحقيبة هو 8. هنا، إذا أضفنا عنصرين من الأوزان 3 و4 فإنه سينتج الحد الأقصى الربح، أي (2 + 3) يساوي 5، لذلك نضيف 5 عند M[4][8] كما هو موضح أدناه:

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

مرة أخرى، سنقوم بمقارنة القيمة 5 من الصف أعلاه، أي i = 2. وبما أن الصف أعلاه يحتوي على القيمة 5، فسيتم إزاحة المؤشر مرة أخرى للأعلى كما هو موضح في الجدول أدناه:

مرة أخرى، سوف نقوم بمقارنة القيمة 5 من الصف أعلاه، أي i = 1. وبما أن الصف أعلاه لا يحتوي على نفس القيمة لذلك سنأخذ في الاعتبار الصف i=1، والوزن المقابل للصف هو 4. لذلك لقد قمنا باختيار الوزن 4 ورفضنا الوزنين 5 و 6 الموضحين أدناه:

س = { 1، 0، 0}

الربح المقابل للوزن هو 3. وبالتالي فإن الربح المتبقي هو (5 - 3) يساوي 2. والآن سنقارن هذه القيمة 2 مع الصف i = 2. حيث أن الصف (i = 1) يحتوي على القيمة 2 ; وبالتالي تحرك المؤشر لأعلى كما هو موضح أدناه:

مرة أخرى نقارن القيمة 2 مع الصف أعلاه، أي i = 1. نظرًا لأن الصف i = 0 لا يحتوي على القيمة 2، لذلك سيتم تحديد الصف i = 1 والوزن المقابل لـ i = 1 هو 3. أقل:

س = {1، 1، 0، 0}

الربح المقابل للوزن هو 2. وبالتالي فإن الربح المتبقي هو 0. نقوم بمقارنة قيمة 0 مع الصف أعلاه. بما أن الصف أعلاه يحتوي على قيمة 0 ولكن الربح المقابل لهذا الصف هو 0. في هذه المشكلة، يتم اختيار وزنين، أي 3 و4 لتعظيم الربح.