مسئله‌ی خرد کردن پول با رویکرد حریصانه

مسئله‌ی خرد کردن پول سوال زیر را مطرح می‌کند:

فرض کنید می‌خواهیم مبلغ $c$ واحد پول را با $n$ سکه $a_1\lt a_2...\lt a_n $ خرد کنیم، چگونه می‌توانیم با استفاده از تعدادی دلخواه از سکه‌های $a_1...,a_n$ مبلغ $c$ را تشکیل دهیم ، به صورتی که تعداد سکه‌های استفاده شده تا حد امکان کم باشد؟

در حالت حریصانه‌ی مسئله فرض می شود $(a_1=1)$ است.

یک الگوریتم برای این مسئله ، خرد کردن پول به وسیله‌ی برنامه‌ریزی پویا است.

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

جواب این الگوریتم در حالت های زیادی از جواب بهینه‌ی مسثله بزرگ تر است. برای مثال روش حریصانه برای مجموعه سکه‌های $\{1,5,6\}$ و $10$ واحد پول جواب غیر بهینه زیر را می‌دهد.

10=6+1+1+1+1  (Greedy=5)   
10=5+5        (Optimal=2)

پیچیدگی این الگوریتم از $O(n)$ است. همان طور که در پیاده سازی سریع کد خواهید دید هر سکه یک بار دیده می‌شود.

مطابق الگوریتم کد زیر در هر مرحله مقدار ماکسیمم را از مبلغ خواسته شده کم و جواب را در $ans$ ذخیره می‌کند.

A.cpp

while(c > 0)                                        // تا جایی که مبلغ باقی مانده 0 نشده
{
	for(int i = n-1; i>=0 ;--i)                 // سکه ها را از مقدار زیاد به کم پیمایش کن
  		if( a[i] < c ){                     // اگر مقدار سکه از مبلغ باقی مانده کمتر باشد 
			c-=a[i];
			ans.push_back(a[i]);        // سکه را به جواب  اضافه کن
 			break;                      // به ابتدای حلقه ی وایل برگرد
		}
}

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

‌‌B.cpp

ans=0;
for(int i = n-1 ; i >= 0 ; --i)
{
	count[i]=c/a[i];
        ans+=count[i];
	c%=a[i];
}