কয়েন চেঞ্জ – সেট ১






কয়েন চেঞ্জ এর অনেক ধরনের প্রব্লেম আছে । ডাইনামিক প্রোগ্রামিং অথবা রিকার্সন ব্যবহার করে এই প্রব্লেম গুলো সমাধান করা যায় । এই টিউটোরিয়াল এ বিভিন্ন কয়েন এর থেকে একটা টাকার পরিমান কে কত উপায়ে বানানো যায় সেটা নিয়ে আলোচনা করা হবে ।

ধরা যাক, আমার কাছে 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] তে উত্তর পেয়ে গেলাম । 


Related Problem : UVA 674 Coin Change
                   UVA 357 Let Me Count The Ways

 

কোড :
  
#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;
}
 









Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge.
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment