مسألة ملائمة الرفوف على الحائط

لو كان هناك جدار (w) ورفوف ذات طولين مختلفين m و n، فما هو عدد الرفوف من كلا النوعين والذي يجب استخدامه بشرط أن تكون المساحة الفارغة المتبقية قليلة قدر الإمكان، علمًا أن الرفوف الكبيرة أرخص من الصغيرة لذا تكون هي المفضلة، ولكنّ كلفة الرفّ ليست مهمّة مقابل تقليل المساحة الفارغة على الجدار.

أمثلة:

المدخلات : w = 24 m = 3 n = 5
المخرجات : 3 3 0

سنستخدم 3 رفوف من كل نوع ولن يبقى هناك مساحة فارغة
3 * 3 + 3 * 5 = 24
المساحة الفارغة = 24 - 24 = 0

هناك حل آخر لهذه المدخلات وهو 8 0 0 ولكن لما كان الرفّ الطويل أرخص من الرف القصير فإنّ الإجابة الأولى هي الإجابة المثالية.

المدخلات : w = 29 m = 3 n = 9
المخرجات : 0 3 2
0 * 3 + 3 * 9 = 27
29 - 27 = 2

المدخلات : w = 24 m = 4 n = 7
المخرجات : 6 0 0
6 * 4 + 0 * 7 = 24
24 - 24 = 0

خطوات الخوارزمية

أبسط طريقة لحلّ هذه المسألة هو تجربة جميع الاحتمالات الممكنة من الرفوف التي يمكن تلائم طول الجدار.

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

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

void minSpacePreferLarge(int wall, int m, int n) 
{ 
	// سنفرض أنّ قيمة m أصغر من قيمة n دائمًا
	// تهيئة المتغيرات التي ستظهر قيمها في المخرجات
	int num_m = 0, num_n = 0, min_empty = wall; 

	// n و m هما عدد الرفوف ذات الطولين q و p
	// rem المساحة الفارغة
	int p = 0, q = 0, rem; 

	while (wall >= n) { 
		// m وضع أكبر عدد ممكن من الرفوف ذات الطول
		// في الجزء المتبقي
		p = wall / m; 
		rem = wall % m; 

		// تحديث قيم المتغيرات إن تحقق هذا الشرط
		// min_empty <= overall empty 
		if (rem <= min_empty) { 
			num_m = p; 
			num_n = q; 
			min_empty = rem; 
		} 

		// n إضافة رف جديد بطول
		q += 1; 
		wall = wall - n; 
	} 

	cout << num_m << " " << num_n << " "
		<< min_empty << endl; 
} 

// اختبار الدالة السابقة 
int main() 
{ 
	int wall = 24, m = 3, n = 5; 
	minSpacePreferLarge(wall, m, n); 

	wall = 24, m = 4, n = 7; 
	minSpacePreferLarge(wall, m, n); 
	return 0; 
}

• بايثون:

def minSpacePreferLarge(w, m, n): 

	# تهيئة المتغيرات التي ستظهر قيمها في المخرجات
	num_m = 0
	num_n = 0
	rem = w 

	# n و m هما عدد الرفوف ذات الطولين q و p
	# r المساحة المتبقية
	p = 0
	q = 0
	r = 0
	while (w >= n): 
		p = w / m 
		r = w % m 
		if (r <= rem): 
			num_m = p 
			num_n = q 
			rem = r 
		q += 1
		w -= n 
	print( str(int(num_m)) + " " + str(num_n) + " " + str(rem)) 

# اختبار الدالة السابقة 
w = 24
m = 3
n = 5
minSpacePreferLarge(w, m, n) 

w = 24
m = 4
n = 7
minSpacePreferLarge(w, m, n)

• جافا:

public class GFG { 
	static void minSpacePreferLarge(int wall, int m, int n) 
	{ 
	    // سنفرض أنّ قيمة m أصغر من قيمة n دائمًا
	    // تهيئة المتغيرات التي ستظهر قيمها في المخرجات
		int num_m = 0, num_n = 0, min_empty = wall; 

	    // n و m هما عدد الرفوف ذات الطولين q و p
	    // rem المساحة الفارغة
		int p = 0, q = 0, rem; 

		while (wall >= n) { 
        // m وضع أكبر عدد ممكن من الرفوف ذات الطول
		// في الجزء المتبقي
			p = wall / m; 
			rem = wall % m; 

			// تحديث قيم المتغيرات إن تحقق هذا الشرط 
			// min_empty <= overall empty 
			if (rem <= min_empty) { 
				num_m = p; 
				num_n = q; 
				min_empty = rem; 
			} 

			// // n إضافة رف جديد بطول 
			q += 1; 
			wall = wall - n; 
		} 
		System.out.println(num_m + " " + num_n + " " + min_empty); 
	} 

    // اختبار التابع السابق
	public static void main(String[] args) 
	{ 
		int wall = 24, m = 3, n = 5; 
		minSpacePreferLarge(wall, m, n); 

		wall = 24; 
		m = 4; 
		n = 7; 
		minSpacePreferLarge(wall, m, n); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

3 3 0
6 0 0

مصادر

• صفحة Fitting Shelves Problem في توثيق الخوارزميات في موقع GeeksforGeeks.