السلام عليكم و رحمة الله و بركاته ..
في إحدى البرامج واجهتني مشكلة يمكن تبسيطها في الآتي ..
لدينا عدد N من المجموعات .. كل مجموعة بها عدد M من العناصر .. كل عنصر له 3 أرقام a و b و c .. المطلوب هو أن أختار عنصر واحد من كل مجموعة بحيث يكون مجموع الرقم a لكل العناصر المختارة أقل من X و مجموع b لكل العناصر المختارة أقل من Y و مجموع c لكل العناصر المختارة أقل من Z .. بالطبع سيكون لدينا الكثير من الإحتمالات و التوافيق التي توافق هذا الشرط .. و التوفيق الأفضل هو الذي إذا قمنا بالتعويض في F(A,B,C) و التي هي هذه المعادلة : h*A+i*B+ j*C نحصل على أقل قيمة .. حيث أن A هي مجموع الـ a لكل العناصر و هكذا B و C ..
مثال :
المجموعة الأولى :
عنصر 1 :
a = 7 , b = 5 , c = 11
عنصر 2 :
a = 2 , b = 8 , c = 12
المجموعة الثانية :
عنصر 1 :
a = 3 , b = 5 , c = 22
عنصر 2 :
a = 9 , b = 1 , c = 44
و بقية المدخلات :
X = 15
Y = 14
Z = 50
h = 0.4
i = 0.3
j = 0.3
هنا كل التوافيق ستكون :
عنصر 1 من مجموعة 1 مع عنصر 1 من مجموعة 2:
مجموع الـ A سيكون 10 .. مجموع الـ B سيكون 10 و مجموع الـ C سيكون 33
و الحل مقبول حيث أن A أقل من X و B أقل من Y و C أقل من Z ..
F(A,B,C) = 10*0.4 + 10*0.3 + 33*0.3 = 16.9
عنصر 2 من مجموعة 1 مع عنصر 1 من مجموعة 2
مجموع الـ A سيكون 5 .. مجموع الـ B سيكون 13 و مجموع الـ C سيكون 34
و الحل مقبول أيضاً ..
F(A,B,C) = 5*0.4 + 13*0.3 + 34*0.3 = 11.55
و هنا هذا الحل أفضل من الحل السابق لأن قيمة الـ F أقل
عنصر 1 من مجموعة 1 مع عنصر 2 من مجموعة 2
مجموع الـ A سيكون 16 .. مجموع الـ B سيكون 6 و مجموع الـ C سيكون 55
و هنا الحل غير مقبول حيث أن C أكبر من Z و A أكبر من X ..
عنصر 2 من مجموعة 1 مع عنصر 2 من مجموعة 2
مجموع الـ A سيكون 11 .. مجموع الـ B سيكون 9 و مجموع الـ C سيكون 56
و هذا الحل غير مقبول أيضاً بسبب قيمة الـ C ..
و هنا نكون قد توصلنا إلى أن إختيار عنصر 2 من مجموعة 1 مع عنصر 1 من مجموعة 2 هو الأحل الأفضل ..
قمت بحل هذه المسألة بطريقة أشبه إلى حدٍ ما بالـ Brute Force .. تصل في أسوأ الحالات إلى O(M^N) .. هل لديكم من أفكار أخرى لحل هذه المشكلة ؟؟
و جزاكم الله خيراً ..
