المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:الگوریتم:خرد کردن‌ پول

مسئله‌ی خرد کردن پول

تعریف سوال

فرض کنید کسی می‌خواهد یک مقدار خاص پول از یک دستگاه خودپرداز برداشت کند. این دستگاه خودپرداز $n$ نوع اسکناس مختلف دارد اما از هر کدام به هر مقدار که بخواهد در اختیار دارد. این دستگاه می‌خواهد بداند آیا می‌تواند با استفاده از این اسکناس‌ها آن مقدار خاص از پول را به فرد تقاضا کننده بدهد یا نه. تمام مقادیر اعداد طبیعی‌اند. اگر می‌تواند، از کدام اسکناس‌ها و به چه مقدار؟

بررسی اولیه

جواب مسئله بستگی به خواص اسکناس‌هایی دارد که در اختیار داریم. مثلا اگر اسکناس واحد داشته باشیم، می‌توانیم تمام مقادیر را پرداخت کنیم یا اگر تمام اسکناس‌ها به یک عدد خاص مثلا پنج بخش‌پذیر باشند، نمی‌توان مقادیری که به آن عدد بخش‌پذیر نیستند را پرداخت یا در حالت‌های خاص جواب را با فرمولی ریاضی ساده‌ای به دست آورد اما در حالت کلی کار سخت‌تر می‌شود.
این سوال راه حلی کارآمدتر و پیچیده‌تر از روشی که در اینجا آمده دارد که از روش برنامه‌ریزی پویا استفاده نمی‌کند. در قسمت مسائل نمونه، صورت سوال این مدل پیچیده‌تر آمده.

الگوریتم

برای حل این مسئله از روش برنامه‌ریزی پویا استفاده می‌کنیم.
بیایید ابتدا مدل ساده‌تر مسئله را حل کنیم که فقط باید بگوییم می‌شود پول را داد یا نه.
آرایه‌ی $d$ یک آرایه‌ی دو بعدی به ابعاد $(n+1) * (w+1)$ است که در آن $n$ تعداد انواع اسکناس‌ها و $w$ مقدار پولی که می‌خواهیم به تقاضا کننده بدهیم.
مقدار $d_{i,j}$ را برابر با یک قرار می‌دهیم، اگر و تنها اگر بشود با $i$ نوع اسکناس اول مقدار پول $j$ را پرداخت کرد.

مقدار اولیه: برای $ i = 0 $ فقط $d_{0,0}$ برابر ۱ است و بقیه صفر اند، چون بدون اسکناس نمی‌توان پولی داد (یا صفر واحد پول می‌توان داد).
به روز رسانی: اگر مقدار اسکناس $i$ ام برابر $a_i$ باشد، $d_{i,j}$ فقط در صورتی می‌تواند ۱ باشد که یا از اسکناس $i$ ام استفاده نکنیم، یعنی $d_{i-1,j}$ یک باشد. یا این که حتما از اسکناس $i$ ام استفاده کنیم که یعنی $d_{i,j-a_i}$ با شرط $ j \geq a_i $ برابر ۱ باشد.
حال اگر $w$ مقدار پولی که باید پرداخت کنیم باشد، جواب مسئله، $d_{n,w}$ است. یعنی اگر این مقدار برابر ۱ باشد، می‌توانیم پول را پرداخت کنیم، اگر هم صفر بود، نمی‌توانیم.

d = {0} 
d[0][0] = 1 

for i from 1 to n 
	for j from 0 to W 
		d[i][j] = d[i-1][j] 
		if j >= a[i] and d[i][j-a[i]] == 1 
			d[i][j] = 1

اما اگر کمی دقت کنید متوجه می‌شوید که نیازی به نگه داشتن بعد اول نیست. پس می‌توان کد را به صورت زیر تغییر داد:

d = {0} 
d[0] = 1 

for i from 1 to n 
	for j from 0 to W 
		if j >= a[i] and d[j-a[i]] == 1 
			d[j] = 1

حال برای این که ترکیب اسکناس‌هایی که این مقدار پول را می‌سازند را هم خروجی بدهیم، می‌توانیم مانند بقیه‌ی سوال‌ها یک آرایه نگه‌داریم که بگوید هر خانه که مقدار ۱ دارد از چه خانه‌ای از جدول به روز رسانی شده.

پیچیدگی‌ الگوریتم

حافظه از $O(w)$ و پیچیدگی زمانی هم $O(n*w)$ است.

پیاده‌سازی اولیه

coins.cpp
#include<iostream> 
using namespace std; 
 
const int MAXN = 10*1000; 
const int MAXW = 100*1000; 
 
bool d[MAXW+10]; 
int p[MAXW+10]; 
int a[MAXN+10]; 
 
int main(){ 
	ios::sync_with_stdio(false); 
	int n, w; 
	cin >> n >> w; 
	for(int i=0; i<n; i++) 
		cin >> a[i]; 
 
	d[0] = 1; 
	for(int i=0; i<n; i++) 
		for(int j=1; j<=w; j++) 
			if( j>=a[i] && d[j-a[i]] == 1 ){ 
				d[j] = 1; 
				p[j] = j-a[i]; 
			} 
 
	if( d[w] == 0 ) 
		cout << "no" << endl; 
	else{ 
		cout << "yes" << endl; 
		int value = w; 
		while( value != 0 ){ 
			cout << value-p[value] << " "; 
			value = p[value]; 
		} 
		cout << endl; 
	} 
	return 0; 
}

مسائل نمونه

  • sums [سطح: سخت]

ابزار صفحه