السلام عليكم

واجهتني مشكلة في إيجاد حل لهده المسألة

والله قضيت أكتر من أسبوعين وأن أحاول حلها ولم أفلح في ذالك

المرجو المساعدة جزاكم الله خيرا

المسألة:A جدول مكون من n سطر m عمود

كل سطر وكل عمود يحتوي على x خانة مملوءة

x>=2

خانة مملوءة تمثل 1

خانة فارغة تمثل 0

المطلوب

تغيير قيمة بعض الخانات من الواحد الى الصفر وليس من الصفر الى الواحد لتحقيق الشرط الأول مع تغيير أقل عدد ممكن من الخانات(الشرط الثاني)

الشرط الأول

يجب أن يكون عدد الخانات المملوءة في كل سطر وعمود عددا زوجيا أو بمعنى آخر أن يكون المجموع في كل سطر وعمود قيمة زوجية وممكن أن يكون الصفر

يعني سيصبح x=2k / k>=0

الشرط الثاني

يجب أن تغير أقل عدد ممكن من الخانات أو بمعنى آخر أن تحصل على أكبر مجموع للخانات التي تمثل واحد في الجدول

مثال

لدينا هدا الجدول

نلاحظ أن العمود الثاني والثالث يحتويان على عدد فردي

الحل هو

مجموع الخانات التي تحتوي على القيمة واحد يساوي 10

يمكن أن يكون أكثر من حل

وهدا حل خاطئ لأنه يحقق الشرط الأول فقط يعني تم تغيير عدد من الخانات أكثر من الازم أي مجموع الخانات التي تحتوي على القيمة واحد يساوي 6 و6 ليست أكبر قيمة ممكن أن تحصل عليها (الحل الصحيح هو دو القيمة 10)

ملاحظة

في بعض الحالات يمكن أن يكون الحل الوحيد هو الجدول فارغ