কয়েন চেঞ্জ এর অনেক
ধরনের প্রব্লেম আছে । ডাইনামিক প্রোগ্রামিং অথবা রিকার্সন ব্যবহার করে এই প্রব্লেম
গুলো সমাধান করা যায় । এই টিউটোরিয়াল এ বিভিন্ন কয়েন এর থেকে একটা টাকার পরিমান কে
কত উপায়ে বানানো যায় সেটা নিয়ে আলোচনা করা হবে ।
ধরা যাক, আমার কাছে 3 ধরনের কয়েন আছে ।
coin[]={1,2,3}
এখন কেউ যদি 3 টাকা দেয় আমাকে তাহলে এই কয়েন গুলো থেকে 3 টাকা কত উপায়ে বানানো সম্ভব ?
সম্ভাব্য কম্বিনেশন ঃ
1. ৩ টি ১ টাকা দিয়ে ৩
টাকা বানানো সম্ভব
2. ১ টি ২ টাকা ও ১ টি ১ টাকা দিয়ে ৩ টাকা বানানো সম্ভব
3. ১ টি ৩ টাকা দিয়ে ৩ টাকা বানানো সম্ভব ।
তাহলে উপরের কয়েন গুলো দিয়ে
৩ ভাবে ৩ টাকা বানানো সম্ভব ।
এখন যদি আমরা ১ নম্বর
থেকে ৩ নম্বর পর্যন্ত প্রতি কয়েন এর ক্ষেত্রে রেজাল্ট বের করে রাখি তাহলে সবার
শেষে আমরা আসল রেজাল্ট পেয়ে যাব । নিচের টেবিল এর সাহায্যে বর্নানা করা হল ঃ
টেবিল এর সারি তে থাকবে কয়েন
এর ভ্যালুগুলো এবং কলাম এ থাকবে ০ থেকে যত টাকার কম্বিনেশন চাওয়া হবে সেই পর্যন্ত
।
n-->
i
|
0
|
1
|
2
|
3
|
1
|
1
|
1
|
1
|
1
|
2
|
1
|
1
|
2
|
2
|
3
|
1
|
1
|
1
|
3
|
প্রথমে table[0]=1 হবে ।
যখন i=1 (১টাকার কয়েন) তখন n=1 হলে (১ টাকা বানাতে হলে)
table[1]=1 হবে কারন ১
টাকা থাকলে ১ বার এ 1 টাকা বানানো যায় ।
table[2]=1 হবে কারন ১
টাকা থাকলে ১ বার এ 2 (1+1) টাকা বানানো যায় ।
table[3]=1 হবে কারন ১
টাকা থাকলে ১ বার এ 3 (1+1+1) টাকা বানানো যায় ।
যখন i=2 (আগের 1 টাকা সহ 2
টাকার কয়েন)
table[2]=2 হবে কারন 2 টাকা থাকলে 2 বার (১ম- (১+১),
২য়- ১টি ২ টাকার কয়েন দিয়ে) ২ টাকা বানানো যায় ।
table[3]=2 কারন 3 টাকা -(1+1+1) এবং 3 টাকা -
2+1
যখন i=3 (এখন ১ , ২, ৩ সব কয়েন আছে )
table[3]=3 কারন 3
টাকা -(1+1+1) এবং 3
টাকা - 2+1 এবং 3 টাকা – 1 টি 3 টাকার কয়েন ।
তাহলে আমরা আমাদের লাস্ট ইন্ডেক্স i=3 and table[3] তে উত্তর
পেয়ে গেলাম ।
কোড :
#include<bits/stdc++.h>
using namespace std;
int coinchange(int S[], int m, int n )
{
int table[n+1];
memset(table, 0, sizeof(table));
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];
}
int main()
{
int coin[] = {1,5,10,25,50};
int m =5;
int n;
while(cin>>n)
{
cout<<coinchange(coin,m,n)<<endl;
}
return 0;
}
0 comments:
Post a Comment