تصريف العملة

تفترض هذه المسألة وجود مبلغ من المال (ليكن N)، والمطلوب هو إيجاد عدد الطرق التي يمكن فيها تصريف هذا المبلغ إلى وحدات أصغر على فرض أن هناك عددًا غير محدود من هذه الوحدات S = {S1, S2, S3, .. Sm}.

فعلى سبيل المثال إن كان N = 4 و S = {1, 2, 3,}‎ فسيكون هناك أربعة حلول لهذه المسألة:

{1, 1, 1, 1}
{1, 1, 2}
{2, 2}
{1, 3}

وبهذا يكون جواب المسألة هو 4.

أما إن كان N = 10 و S = {2, 5, 3, 6} فإن الحلول ستكون:

{2, 2, 2, 2, 2}
{2, 2, 3, 3}
{2, 2, 6}
{2, 3, 5}
{5, 5}

وبهذا يكون جواب المسألة هو 5.

البنية الفرعية المثالية

يمكن تقسيم مجموعة الحلول الكلية إلى مجموعتين وذلك لحساب العدد الكلي للحلول:

1. الحلول التي لا تحتوي على الوحدة ذات الترتيب m (أو Sm).
2. الحلول التي تحتوي على Sm واحد على الأقل.

ولو فرضنا أن الدالة count(S[], m, n)‎ هي الدالة المسؤولة عن حساب عدد الحلول، فيمكن حينئذٍ إعادة كتابة هذه الدالة كمجموع للدالتين count(S[], m-1, n)‎ و count(S[], m, n-Sm)‎.

تتمتّع المسألة إذن المسألة بخاصية البنية الفرعية المثالية، وهذا يعني إمكانية إيجاد حلّ لهذه المسألة بإيجاد حلول للمسائل المتفرّعة عنها.

مسائل فرعية متداخلة

تعرض الشيفرات التالية طريقة حلّ مسألة تصريف العملة تعاوديًا.

• C++‎:

#include<stdio.h> 

// تعيد الدالة عدد الطرق التي يمكن فيها جميع
// S[0...m-1] عملة
// n للحصول على المجموع
int count( int S[], int m, int n ) 
{ 
	// n إن كان الصفر هو قيمة 
	// فهذا يعني وجود حل واحد
	// (عدم إضافة أي عملة)
	if (n == 0) 
		return 1; 
	
	// إن كانت قيمة n أقل من الصفر
	// لا وجود لأي حل لهذه المسألة
	if (n < 0) 
		return 0; 

	// إن لم يكن هناك أي عملة
	// وكانت قيمة n أكبر من 0
	// فهذا يعني عدم وجود أي حل لهذه المسألة
	if (m <=0 && n >= 1) 
		return 0; 

	// count مجموع الحلول
	// (1) S[m -1] من ضمنها
	// (2) S[m - 1] ليس من ضمنها
	return count( S, m - 1, n ) + count( S, m, n-S[m-1] ); 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int i, j; 
	int arr[] = {1, 2, 3}; 
	int m = sizeof(arr)/sizeof(arr[0]); 
	printf("%d ", count(arr, m, 4)); 
	getchar(); 
	return 0; 
}

• بايثون:

# تعيد الدالة عدد الطرق التي يمكن فيها جميع
# S[0...m-1] عملة
# n للحصول على المجموع
def count(S, m, n ): 

# n إن كان الصفر هو قيمة 
	# فهذا يعني وجود حل واحد
	# (عدم إضافة أي عملة)
	if (n == 0): 
		return 1

	# إن كانت قيمة n أقل من الصفر 
	# لا وجود لأي حل لهذه المسألة 
	if (n < 0): 
		return 0; 

	# إن لم يكن هناك أي عملة
	# وكانت قيمة n أكبر من 0
	# فهذا يعني عدم وجود أي حل لهذه المسألة
	if (m <=0 and n >= 1): 
		return 0

	# count مجموع الحلول 
	# (1) S[m -1] من ضمنها
	# (2) S[m - 1] ليس من ضمنها
	return count( S, m - 1, n ) + count( S, m, n-S[m-1] ); 

# اختبار الدالة السابقة 
arr = [1, 2, 3] 
m = len(arr) 
print(count(arr, m, 4))

• جافا:

import java.io.*; 

class GFG { 
	
    // تعيد الدالة عدد الطرق التي يمكن فيها جميع
    // S[0...m-1] عملة
    // n للحصول على المجموع
	static int count( int S[], int m, int n ) 
	{ 
		// n إن كان الصفر هو قيمة  
		// فهذا يعني وجود حل واحد
		// (عدم إضافة أي عملة)
		if (n == 0) 
			return 1; 
		
		// إن كانت قيمة n أقل من الصفر
		// لا وجود لأي حل لهذه المسألة
		if (n < 0) 
			return 0; 
	
		// إن لم يكن هناك أي عملة
		// وكانت قيمة n أكبر من 0
		// فهذا يعني عدم وجود أي حل لهذه المسألة
		if (m <=0 && n >= 1) 
			return 0; 
	
		// count مجموع الحلول
		// (1) S[m -1] من ضمنها
		// (2) S[m - 1] ليس من ضمنها
		return count( S, m - 1, n ) + 
			count( S, m, n-S[m-1] ); 
	} 
	
	// اختبار التابع السابق
	public static void main(String[] args) 
	{ 
		int arr[] = {1, 2, 3}; 
		int m = arr.length; 
		System.out.println( count(arr, m, 4)); 
		
		
	} 

}

يلاحظ أنّ الشيفرة السابقة تحسب المسائل الفرعية نفسها مرارًا وتكرارًا. يعرض الشكل التالي شجرة التعاود للقيم S = {1, 2, 3}‎ و N = 5.

C() --> count()
                             C({1,2,3}, 5)                     
                           /             \    
                         /                 \                  
             C({1,2,3}, 2)                 C({1,2}, 5)
            /       \                      /      \         
           /         \                    /         \   
C({1,2,3}, -1)  C({1,2}, 2)        C({1,2}, 3)    C({1}, 5)
               /    \             /     \           /     \
             /       \           /       \         /        \
    C({1,2},0)  C({1},2)   C({1,2},1) C({1},3)    C({1}, 4)  C({}, 5)
                   / \     / \        /\         /     \         
                  /   \   /   \     /   \       /       \  
                .      .  .     .   .     .   C({1}, 3) C({}, 4)
                                               / \ 
                                              /   \   
                                             .      .

يلاحظ أن الدالة C({1}, 3) تستدعى مرتين، وإن عُرضت شجرة التعاود كاملة فستكون هناك استدعاءات متكرّرة للعديد من المسائل الفرعية، وهذا يعني أنّ هذه المسألة تتمتّع بخاصية المسائل الفرعية المتداخلة.

ولمّا كانت هذه المسألة تتمتع بالخاصيتين الرئيسيتين لمسائل البرمجة الديناميكية، فيمكن حلّ هذه المسألة باستخدام أسلوب البرمجة الديناميكية، ويمكن تجنّب تكرار حساب المسائل الفرعية بإنشاء مصفوفة مؤقتة (لتكن table[][]‎) بطريقة (أسفل إلى أعلى bottom up).

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

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

• C++‎:

#include<bits/stdc++.h> 

using namespace std; 

int count( int S[], int m, int n ) 
{ 
	int i, j, x, y; 

	// n + 1 سنحتاج إلى
	// من الصفوف لأنّ الجدول سيُبنى من الأسفل إلى الأعلى
	// باستخدام الحالة الأساس التي تساوي 0
	int table[n + 1][m]; 
	
	// جعل جميع قيم المصفوفة أصفارًا
	for (i = 0; i < m; i++) 
		table[0][i] = 1; 

	// تغيير بقية العناصر في الجدول من الأسفل إلى الأعلى
	for (i = 1; i < n + 1; i++) 
	{ 
		for (j = 0; j < m; j++) 
		{ 
			// S[j] عدّ الحلول إضافة إلى الحل
			x = (i-S[j] >= 0) ? table[i - S[j]][j] : 0; 

			// S[j] عدّ الحلول من دون الحل
			y = (j >= 1) ? table[i][j - 1] : 0; 

			// التعداد الكلي
			table[i][j] = x + y; 
		} 
	} 
	return table[n][m - 1]; 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int arr[] = {1, 2, 3}; 
	int m = sizeof(arr)/sizeof(arr[0]); 
	int n = 4; 
	cout << count(arr, m, n); 
	return 0; 
}

• بايثون:

def count(S, m, n): 
	# n + 1 سنحتاج إلى
	# iمن الصفوف لأنّ الجدول سيُبنى من الأسفل إلى الأعلى 
	# باستخدام الحالة الأساس التي تساوي 0
	table = [[0 for x in range(m)] for x in range(n+1)] 

	# جعل جميع قيم المصفوفة أصفارًا 
	for i in range(m): 
		table[0][i] = 1

	#  تغيير بقية العناصر في الجدول من الأسفل إلى الأعلى 
	for i in range(1, n+1): 
		for j in range(m): 

			# S[j] عدّ الحلول إضافة إلى الحل 
			x = table[i - S[j]][j] if i-S[j] >= 0 else 0

			# S[j] عدّ الحلول من دون الحل 
			y = table[i][j-1] if j >= 1 else 0

			# التعداد الكلي
			table[i][j] = x + y 

	return table[n][m-1] 

# اختبار الدالة السابقة 
arr = [1, 2, 3] 
m = len(arr) 
n = 4
print(count(arr, m, n))

• جافا:

import java.util.Arrays; 

class CoinChange 
{ 
	static long countWays(int S[], int m, int n) 
	{ 

		// n + 1 سنحتاج إلى
		// من الصفوف لأنّ الجدول سيُبنى من الأسفل إلى الأعلى
		//  باستخدام الحالة الأساس التي تساوي 0 
		long[] table = new long[n+1]; 

		// جعل جميع قيم المصفوفة أصفارًا 
		Arrays.fill(table, 0);

		// الحالة ألأساس (إن كانت القيمة المعطاة صفرًا)
		table[0] = 1; 

		// تغيير بقية العناصر في الجدول من الأسفل إلى الأعلى 
		for (int i=0; i<m; i++) 
			for (int j=S[i]; j<=n; j++) 
				table[j] += table[j-S[i]]; 

		return table[n]; 
	} 

	// اختبار التابع السابق
	public static void main(String args[]) 
	{ 
		int arr[] = {1, 2, 3}; 
		int m = arr.length; 
		int n = 4; 
		System.out.println(countWays(arr, m, n)); 
	} 
}

التعقيد الزمني

يبلغ التعقيد الزمني لطريقة البرمجة الديناميكية المقدار O(mn)‎.

مصادر

• صفحة Coin Change في توثيق الخوارزميات في موقع GeeksforGeeks.