Algorithms/minimum coins to value

تفترض هذه المسألة وجود مبلغ من المال (ليكن V) والمطلوب هو تصريف هذا المبلغ إلى عملات أصغر على فرض أن هناك عددًا غير محدود من هذه العملات C = {C1, C2, ... Cm}‎، بشرط الحصول على أصغر عدد من العملات.

مثال:

Input: coins[] = {25, 10, 5}, V = 30
Output: Minimum 2 coins required
يمكن استخدام عملة واحدة من فئة 25 وعملة واحدة من فئة 5

Input: coins[] = {9, 6, 5, 1}, V = 11
Output: Minimum 2 coins required
يمكن استخدام عملة واحدة من فئة 5 وعملة واحدة من فئة 6

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

الطريقة التعاودية

يمكن حساب أقل عدد ممكن من العملات V باستخدام الصيغة التعاودية التالية:

If V == 0, سنحتاج إلى 0 عملة
If V > 0

   minCoins(coins[0..m-1], V) = min {1 + minCoins(V-coin[i])} 
                               تتراوح قيمة i بين 0 و m-1
                               و coin[i] <= V 

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

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

• C++‎:

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

// m: حجم مصفوفة العملات
int minCoins(int coins[], int m, int V) 
{ 
// الحالة الأساس
if (V == 0) return 0; 

// تهيئة النتيجة
int res = INT_MAX; 

// V تجربة جميع العملات التي تمتلك قيمة أصغر من
for (int i=0; i<m; i++) 
{ 
	if (coins[i] <= V) 
	{ 
		int sub_res = minCoins(coins, m, V-coins[i]); 

		// INT_MAX التحقق من
		// لتجنب حدوث حالة الفيضان
		// ولمعرفة ما إذا كان بالإمكان تصغير النتيجة
		if (sub_res != INT_MAX && sub_res + 1 < res) 
			res = sub_res + 1; 
	} 
} 
return res; 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int coins[] = {9, 6, 5, 1}; 
	int m = sizeof(coins)/sizeof(coins[0]); 
	int V = 11; 
	cout << "Minimum coins required is "
		<< minCoins(coins, m, V); 
	return 0; 
}

• بايثون:

import sys 

# m: حجم مصفوفة العملات 
def minCoins(coins, m, V): 

	# الحالة الأساس 
	if (V == 0): 
		return 0

	# تهيئة النتيجة
	res = sys.maxsize 
	
	# V تجربة جميع العملات التي تمتلك قيمة أصغر من 
	for i in range(0, m): 
		if (coins[i] <= V): 
			sub_res = minCoins(coins, m, V-coins[i]) 

			# INT_MAX التحقق من 
			# لتجنب حدوث حالة الفيضان
			# ولمعرفة ما إذا كان بالإمكان تصغير النتيجة
			if (sub_res != sys.maxsize and sub_res + 1 < res): 
				res = sub_res + 1

	return res 

# اختبار الدالة السابقة
coins = [9, 6, 5, 1] 
m = len(coins) 
V = 11
print("Minimum coins required is",minCoins(coins, m, V))

• جافا:

class coin 
{ 
	// m: حجم مصفوفة العملات 
	static int minCoins(int coins[], int m, int V) 
	{ 
	// الحالة الأساس
	if (V == 0) return 0; 
	
	// تهيئة النتيجة
	int res = Integer.MAX_VALUE; 
	
	// V تجربة جميع العملات التي تمتلك قيمة أصغر من
	for (int i=0; i<m; i++) 
	{ 
		if (coins[i] <= V) 
		{ 
			int sub_res = minCoins(coins, m, V-coins[i]); 
	
			// INT_MAX التحقق من
			// لتجنب حدوث حالة الفيضان
			// ولمعرفة ما إذا كان بالإمكان تصغير النتيجة
			if (sub_res != Integer.MAX_VALUE && sub_res + 1 < res) 
				res = sub_res + 1; 
		} 
	} 
	return res; 
	} 
	
	// اختبار التابع السابق
	public static void main(String args[]) 
	{ 
	int coins[] = {9, 6, 5, 1}; 
	int m = coins.length; 
	int V = 11; 
	System.out.println("Minimum coins required is "+ minCoins(coins, m, V) ); 
	} 
}

يبلغ التعقيد الزمني للطريقة السابقة مقدارًا أسّيًا، ولو رسمنا شجرة التعاودة كاملة للاحظنا أن هناك عددًا من المسائل الفرعية التي يجري حلّها مرارًا وتكرارًا، فعلى سبيل المثال عند البدء من V = 11 يمكن الوصول إلى 6 بطرح الرقم 1 خمس مرات وبطرح الرقم 5 مرة واحدة، وهذا يعني أن المسألة الفرعية الخاصة بالرقم 6 ستستدعى مرتين، وهذا يعني أن هذه المسألة تتمتع بخاصية المسائل الفرعية المتداخلة.

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

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

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

• C++‎:

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

// m: حجم مصفوفة العملات 
int minCoins(int coins[], int m, int V) 
{ 
	// i سيخزن أقل عدد من العملات تحتاجه القيمة
	// table[i] في
	// table[V] لذا ستكون النتيجة مخزّنة في
	int table[V+1]; 

	// الحالة الأساس
	table[0] = 0; 

	// تهيئة جميع قيم الجدول لتكون ما لا نهاية
	for (int i=1; i<=V; i++) 
		table[i] = INT_MAX; 

	// V حساب أقل عدد مطلوب من العملات لجميع القيم من 1 إلى
	for (int i=1; i<=V; i++) 
	{ 
		// i المرور على جميع العملات التي تكون قيمتها أصغر من 
		for (int j=0; j<m; j++) 
		if (coins[j] <= i) 
		{ 
			int sub_res = table[i-coins[j]]; 
			if (sub_res != INT_MAX && sub_res + 1 < table[i]) 
				table[i] = sub_res + 1; 
		} 
	} 
	return table[V]; 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int coins[] = {9, 6, 5, 1}; 
	int m = sizeof(coins)/sizeof(coins[0]); 
	int V = 11; 
	cout << "Minimum coins required is "
		<< minCoins(coins, m, V); 
	return 0; 
}

• بايثون:

import sys 
def minCoins(coins, m, V): 
	
	# i سيخزن أقل عدد من العملات تحتاجه القيمة
	# table[i] في
	# table[V] لذا ستكون النتيجة مخزّنة في
	table = [0 for i in range(V + 1)] 

	# الحالة الأساس
	table[0] = 0

	# تهيئة جميع قيم الجدول لتكون ما لا نهاية 
	for i in range(1, V + 1): 
		table[i] = sys.maxsize 

	# V حساب أقل عدد مطلوب من العملات لجميع القيم من 1 إلى
	for i in range(1, V + 1): 
		
		# i المرور على جميع العملات التي تكون قيمتها أصغر من  
		for j in range(m): 
			if (coins[j] <= i): 
				sub_res = table[i - coins[j]] 
				if (sub_res != sys.maxsize and
					sub_res + 1 < table[i]): 
					table[i] = sub_res + 1
	return table[V] 

# اختبار الدالة السابقة
if __name__ == "__main__": 

	coins = [9, 6, 5, 1] 
	m = len(coins) 
	V = 11
	print("Minimum coins required is ", 
				minCoins(coins, m, V))

• جافا:

import java.io.*; 

class GFG 
{ 
	// m: حجم مصفوفة العملات  
	static int minCoins(int coins[], int m, int V) 
	{ 
    	// i سيخزن أقل عدد من العملات تحتاجه القيمة
    	// table[i] في
    	// table[V] لذا ستكون النتيجة مخزّنة في
		int table[] = new int[V + 1]; 

		// الحالة الأساس
		table[0] = 0; 

		//  تهيئة جميع قيم الجدول لتكون ما لا نهاية
		for (int i = 1; i <= V; i++) 
		table[i] = Integer.MAX_VALUE; 

		// V حساب أقل عدد مطلوب من العملات لجميع القيم من 1 إلى
		for (int i = 1; i <= V; i++) 
		{ 
			// i المرور على جميع العملات التي تكون قيمتها أصغر من 
			for (int j = 0; j < m; j++) 
			if (coins[j] <= i) 
			{ 
				int sub_res = table[i - coins[j]]; 
				if (sub_res != Integer.MAX_VALUE 
					&& sub_res + 1 < table[i]) 
					table[i] = sub_res + 1; 
						
				
			} 
			
		} 
		return table[V]; 
		
	} 

	// اختبار الدالة السابقة 
	public static void main (String[] args) 
	{ 
		int coins[] = {9, 6, 5, 1}; 
		int m = coins.length; 
		int V = 11; 
		System.out.println ( "Minimum coins required is "
							+ minCoins(coins, m, V)); 
	} 
}

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

Minimum coins required is 2

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

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

مصادر

• صفحة Find minimum number of coins that make a given value في توثيق الخوارزميات في موقع GeeksforGeeks.