কয়েন চেঞ্জ + রক ক্লাইম্বিং

[নোটিস (২১ এপ্রিল ২০২০): ডাইনামিক প্রোগ্রামিং নিয়ে আমি নতুন সিরিজ শুরু করেছি। এই লেখাটির নতুন ভার্সন পাওয়া যাবে এখানে)

আগের পর্বগুলো পড়ে থাকলে তুমি এখন ডাইনামিক প্রোগ্রামিং নিয়ে বেসিক ব্যাপারগুলো কিছুটা শিখে গিয়েছো,যত প্রবলেম সলভ করবে তত দক্ষতা বাড়বে। ডিপিতে আসলে কোনো নির্দিষ্ট অ্যালগোরিদম না থাকায় আমাদের চিন্তা করতে হয় অনেক বেশি,একেকটি ডিপি প্রবলেম একেক ধরণের, তবে তুমি যদি ন্যাপস্যাক,কয়েন চেঞ্জের মতো ক্লাসিক কিছু ডিপি প্রবলেমের সলিউশন জানো তাহলে তুমি বুঝতে পারবে কিভাবে তোমার চিন্তাকে এগিয়ে নিয়ে যেতে হবে,কিভাবে ডিপির স্টেট নির্ধারণ করতে হবে,তখন তুমি নতুন ধরণের ডিপি প্রবলেমও সলভ করে ফেলতে পারবে। আমি এরই মধ্যে $^nC_r$ নির্ণয় আর ০-১ ন্যাপস্যাকের ডিপি সলিউশন নিয়ে আলোচনা করেছি,আরো কিছু ক্লাসিক বা স্ট্যান্ডার্ড প্রবলেম নিয়ে সামনে আলোচনা করবো।

কয়েন চেঞ্জ:

এখন আমরা দেখবো কয়েন চেঞ্জ প্রবলেম। আসলে ন্যাপসাক শেখার পরে কয়েন চেঞ্জ তুমি এমনিই পারবে তারপরেও লিখছি যাতে ব্যাপারগুলো আর পরিস্কার হয়।

তোমার কাছে কিছু কয়েন আছে যাদের মূল্য $5, 8, 11, 15, 18$ ডলার। প্রতিটা কয়েন অসীম সংখ্যকবার আছে, তুমি যেকোনো কয়েন যতবার ইচ্ছা নিতে পারো। তাহলে তোমার coin অ্যারেটা হতে পারে এরকম:

coin[] = {5, 8, 11, 15, 18};

এখন তোমাকে এই কয়েনগুলো নিয়ে নির্দিষ্ট কোনো ভ্যালু বানাতে হবে। ধরি সংখ্যাটি হলো $make$। $make=18$ হলে আমরা $5+5+8$ এভাবে $18$ বানাতে পারি। তোমাকে বলতে হবে কয়েনগুলো দিয়ে ভ্যালুটি বানানো যায় নাকি যায়না।
প্রথমেই আমরা চিন্তা করি ডিপিতে স্টেট কি হবে। আমরা একটি একটি কয়েন নিয়ে সংখ্যাটি বানাতে চেষ্টা করতে থাকবো। তাহলে এই মুহুর্তে কোন কয়েন নিচ্ছি সেটা স্টেট রাখতে হবে, আর আগে যেসব কয়েন নিয়েছি সেগুলোর মোট ভ্যালু কত সেটা রাখতে হবে। ফাংশনটির নাম call হলে প্রোটোটাইপ হবে:

এরপর অনেকটা আগের মতোই কাজ। প্রথমে $i$ নম্বর কয়েন নিতে চেষ্টা করবো:

এখানে $i+1$ কল না করে আবার $i$ কল করছি কারন এক কয়েন অনেকবার নেয়া সম্ভব। যদি এক কয়েন একাধিক বার নেয়া না যেতো তাহলে $i+1$ কে কল দিতাম। $amount + coin[i]$ যদি $make$ এর থেকে বড় হয় তাহলে কয়েনটি নেয়া সম্ভবনা। কয়েন যদি না নেই তাহলে আমরা পরবর্তী কয়েনে চলে যাবো:

$ret1$ আর $ret2$ এর কোনো একটি true হলেও make বানানো যাবে। তাহলে সবশেষে লিখবো:

আর বেসকেস হবে হলো, যদি সব কয়েন নিয়ে চেষ্টা করার পর $make$ বানানো যায় তাহলে return 1, অন্যথায় return 0। সম্পূর্ণ কোড:

 

এখন যদি তোমাকে বলা হতো যে কোনো একটি ভ্যালু কতবার বানাতে হবে বলতে হবে তাহলে কি করতে? যেমন ১৮ বানানো যায় ২ ভাবে, এক্ষেত্রে ret1|ret2 রিটার্ন না করে ret1 + ret2 রিটার্ন করে দাও,তাহলে যত ভাবে বানানো যায় সবগুলো যোগ হয়ে যাচ্ছে। uva-674 প্রবলেমটিতে এটাই করতে বলা হয়েছে,ঝটপট সলভ করে ফেলো।

এবার মজার একটি অপটিমাইজেশন দেখো। আমরা প্রতিবার make ইনপুট নেয়ার পর ডিপি অ্যারে নতুন করে initialize বা ক্লিয়ার করেছি। যদি সেটা করতে না হতো তাহলে অনেক কম সময় লাগতো, কারণ একই মান বারবার হিসাব করা লাগবেনা। কিন্তু ক্লিয়ার করতে হচ্ছে কারণ ফাংশনটি বাইরের একটি গ্লোবাল ভ্যারিয়েবলের উপর নির্ভরশীল, “if(amount==make)return 1;” এই লাইনটাই ঝামেলা করছে, $make$ এর মান প্রতি কেসের জন্য আলাদা, তাই প্রতিবার নতুন করে সব হিসাব করতে হচ্ছে। আমরা যদি $make$ কে একটা স্টেট হিসাবে রাখি তাহলে কাজ হয় কিন্তু স্টেট বিশাল হয়ে যায়। এর থেকে আমরা সমস্যাটাকে উল্টায় ফেলি। মনে করো তোমার কাছে শুরুতে ২০ টাকা আছে, বিভিন্ন অ্যামাউন্টের কয়েন দান করে দিয়ে তোমাকে শুন্য টাকা বানাতে হবে। কোডটা এবার হবে এরকম:

 

খেয়াল করে দেখো ঠিক আগের মতোই কাজ করেছি, শুধু যোগ করার জায়গায় বিয়োগ করে $make$ থেকে শুন্য বানানোর চেষ্টা করেছি। লাভটা হলো এখন ফাংশনটি কোনো পরিবর্তনশীল গ্লোবাল ভ্যারিয়েবলের উপর নির্ভর করেনা, তাই মেইন ফাংশনে ডিপি অ্যারে লুপের মধ্যে ক্লিয়ার করা দরকার নাই। প্রতিবার কয়েন একই থাকছে বলে এই ট্রিকসটা কাজ করছে, কয়েনের মান পরিবর্তন হলে কাজ করবেনা। ডিপির প্রবলেমে অনেকসময় টেস্টকেস অনেক বেশি দেয় যাতে বার বার ক্লিয়ার করলে টাইম লিমিট পাস না করে।

কমপ্লেক্সিটি
ডিপি অ্যারের সাইজ হবে কয়েন সংখ্যা × সর্বোচ্চ যত ভ্যালু বানাতে হবে। তাহলে মেমরি কমপ্লেক্সিটি $O(number of coin \times make)$.
ডিপি অ্যারের প্রতিটা সেলই ভরাট করা লাগতে পারে, তাই টাইম কমপ্লেক্সিটিও এখানে $O(number of coin \times make)$। যদি ভিতরে কোনো এক্সট্রা লুপ চলতো তাহলে সেটাও টাইম কমপ্লেক্সিটির সাথে যোগ হতো।

লাইটওজেতে 1231 – Coin Change (I) প্রবলেমে কিছু কয়েন দিয়ে একটি ভ্যালু কয়ভাবে বানানো যায় সেটা বের করতে বলেছে, তবে প্রতিটি কয়েন সর্বোচ্চ কয়বার ব্যবহার করা যাবে সেটা বলা আছে, i নম্বর কয়েন $C_{i}$ বার ব্যবহার করা যাবে। এই কন্ডিশনটা দুইভাবে তুমি হ্যান্ডেল করতে পারো। ৩য় একটি স্টেট রাখতে পারো $taken_i$ যেটা বলে দিবে $i$ নম্বর তুমি কয়বার নিয়েছো, $C_{i}$ বার ব্যবহার হয়ে গেলে পরবর্তী কয়েনে চলে যাও।

২য় উপায় হলো ফাংশনের ভিতরে $C_i$ পর্যন্ত একটি লুপ চালিয়ে কয়েনটি যতবার নেয়া সম্ভব ততবার নিয়ে অ্যামাউন্টটি বানাতে চেষ্টা করো, এক্ষেত্রে মেমরি কম লাগবে। তাহলে আজকের ২য় কাজ হলো এই প্রবলেমটা সলভ করা।

কয়েন চেঞ্জ প্রবলেমের আরেকটি নাম হলো subset sum problem,কারণ কিছু নম্বরের সেট থেকে একটি সাবসেট আমাদের নিতে হয় যেটার যোগফল এক নির্দিষ্ট ভ্যালুর সমান।

 রক-ক্লাইম্বিং প্রবলেম

তোমাকে একটি ২ডি গ্রিড দেয়া হলো:

-1 2 5
4 -2 3
1 2 10

তুমি শুরুতে আছো (০,০) সেলে। তুমি শুধু ৩দিকে যেতে পারো:

(i + 1, j)
(i + 1,j – 1)
(i + 1, j + 1)

প্রতিটি সেলে গেলে তোমার পয়েন্টের সাথে ওই সেলের সংখ্যাটি যোগ হয়। তুমি সর্বোচ্চ কত পয়েন্ট বানাতে পারবে? এই প্রবলেমকে রক ক্লাইম্বিং প্রবলেমও বলা হয়।
উপরের গ্রিডে সর্বোচ্চ পয়েন্ট 7 = -1+-2+10।  এই প্রবলেমের জন্য:

স্টেট: তুমি এখন কোন সেল এ আছো
এক থেকে অন্য স্টেটে যাওয়ার উপায়: প্রতিটা সেল থেকে ৩দিকে যাবার চেষ্টা করো, যেদিকে সর্বোচ্চ পয়েন্ট পাবে সেটা রিটার্ণ করো।
বেসকেস: যদি গ্রিডের বাইরে চলে যাও তাহলে আর কিছু নেয়া যাবেনা, শুণ্য রিটার্ণ করো।

৩দিকে মুভ করার কন্ডিশন কেনো দেয়া হয়েছে? adjacent ৪টি সেলে মুভ করতে দিলে সমস্যা কোথায় হতো? তাহলে একটি সাইকেল তৈরি হতো,একটি ফাংশনের কাজ শেষ হবার আগেই রিকার্শনে ঘুরে ফাংশনটি আবার কল হতো,এই সলিউশন কাজ করতো না। এখানে আমরা যে ৩দিকে মুভ করছি তাতে কোনো সাইকেল তৈরি হচ্ছেনা, অর্থাৎ কোনো স্টেট থেকে শুরু করে সেই স্টেটে আবার ফিরে আসতে পারছিনা। সাইকেল যদি তৈরি হতো তাহলে রিকার্সিভ ফাংশন আজীবন চলতেই থাকতো। তাই ডিপি সলিউশন লেখার সময় অবশ্যই খেয়াল রাখতে হবে সাইকেল তৈরি হচ্ছে নাকি।

1004 – Monkey Banana Problem এই প্রবলেমটা অনেকটা উপরের প্রবলেমের মতো,সলভ করতে কোনো সমস্যা হবেনা। তুমি যদি বিএফএস/ডিএফএস পারো তাহলে uva-11331 প্রবলেমটি সলভ করে ফেলো, (হিন্ট:বাইকালারিং+ন্যাপস্যাক)। এছাড়া এগুলো ট্রাই করো:

Uva 11137: Ingenuous Cubrency(Coin change)
Codeforces 118D: Caesar’s Legions(4 state)
Light oj 1047: Neighbor House
Timus 1017: Staircases

চেষ্টা করো সবগুলো প্রবলেম সলভ করতে,আটকে গেলে সমস্যা নাই,চিন্তা করতে থাকো,এছাড়া ন্যাপস্যাক আর কয়েন চেঞ্জ সম্পর্কিত যতগুলো পারো প্রবলেম সলভ করে ফেলো,যেহেতু তুমি এখন বেসিক পরবর্তী পর্বগুলোতে ডিটেইলস কমিয়ে নতুন নতুন প্রবলেম আর টেকনিক নিয়ে বেশি আলোচনা করবো।
হ্যাপি কোডিং!
সবগুলো পর্ব

 

[নোটিস (২১ এপ্রিল ২০২০): ডাইনামিক প্রোগ্রামিং নিয়ে আমি নতুন সিরিজ শুরু করেছি। এই লেখাটির নতুন ভার্সন পাওয়া যাবে এখানে)

Print Friendly, PDF & Email

ফেসবুকে মন্তব্য

comments

Powered by Facebook Comments

83,314 times read (exlcuding bots)

43 thoughts on “কয়েন চেঞ্জ + রক ক্লাইম্বিং

    1. প্রবলেমে বলা আছে “Next line contains one integer (1<=G<=100) it’s the number of people in our group."। q টা এখানে G। তারপর বলেছে ". Print out the maximal value of goods which we can buy with that family." । q জন ফ্যামিলি মেম্বারের জন্য ম্যাক্সিমামটা বের করে পুরোটা যোগ করে দিয়েছি। আমি মূল লেখায়/কোডে ব্যাখ্যাটুকু যোগ করে দিচ্ছি,ধন্যবাদ।

  1. Sir, you have done a great job. first of all i would like to thank you for such a good work.if you kindly check my code and let me know where i did mistake , it will be great help to me.
    Problem Name : supper sale
    here is my code:

    #include
    #include
    using namespace std;

    int dp[1010][105];
    int w[1010],cost[1010],N;
    int cap[110],g,capa;
    int f(int i,int W){
    if(i==N+1)
    return 0;
    if(dp[i][W]!=-1)
    return dp[i][W];
    int p1=0,p2=0;
    if(W+w[i]>=capa)
    p1=cost[i]+f(i+1,W+w[i]);
    p2=f(i+1,W);
    dp[i][W]=max(p1,p2);
    return dp[i][W];
    }
    int main(){
    int t;
    cin>>t;
    while(t–){

    cin>>N;
    int r=0;
    for(int i=1;i>cost[i]>>w[i];
    cin>>g;
    for(int i=1;i>cap[i];
    for(int i=1;i<=g;i++){
    capa=cap[i];
    memset(dp,-1,sizeof dp);
    r+=f(1,0);
    }

    cout<<dp[0][1]<<endl;
    cout<<r<<endl;
    }
    return 0;
    }

  2. uva-10130 supersale প্রবলেমটিতে একটি আইটেম একবারের বেশি নেয়া গেলে ১২ নম্বর লাইনে( int profit2=call(i+1,w); ) i+1 এর জায়গায় i বানাতে হবে ,নাকি ১০ নম্বর লাইনে ( if(w+Weight[i]<=cap)profit1=Cost[i]+call(i+1,w+Weight[i]); ) ?

  3. ভাই আমি light oj 1231 প্রবলেম টা আপনের প্রথম টেকনিক ই করছি। টেস্ট কেস গূলো ঠিক আছে। BUT ACCEPT হচ্ছে না। here is my code: please help me

    #include
    #include
    #include
    using namespace std;
    long long func(int i,long long m,int tak);
    long long n,m;
    int coin[51],take[51];
    long long dp[51][1001][51];
    int main()
    {
    int t,cas=1;

    scanf(“%d”,&t);
    memset(dp,-1,sizeof(dp));
    while(t–)
    {

    scanf(“%lld%lld”,&n,&m);

    for(int i=0; i<n; i++)
    scanf("%d",&coin[i]);
    for(int i=0; i<n; i++)
    scanf("%d",&take[i]);

    printf("Case %d: %lld\n",cas++,func(0,m,1)%100000007);

    }

    return 0;
    }
    long long func(int i,long long m,int tak)
    {
    if(i==n)
    {
    if(m==0)return 1;
    else return 0;
    }
    if(m==0)return 1;
    if(m=0&&tak<=take[i])ret1=func(i,m-coin[i],tak+1)%100000007;
    ret2=func(i+1,m,1)%100000007;
    dp[i][m][tak]=(ret1+ret2)%100000007;
    return dp[i][m][tak];
    }

    }

  4. sorry problem eta:
    #include
    #include
    #include
    using namespace std;
    long long func(int i,long long m,int tak);
    long long n,m;
    int coin[51],take[51];
    long long dp[51][1001][51];
    int main()
    {
    int t,cas=1;

    scanf(“%d”,&t);
    memset(dp,-1,sizeof(dp));
    while(t–)
    {

    scanf(“%lld%lld”,&n,&m);

    for(int i=0; i<n; i++)
    scanf("%d",&coin[i]);
    for(int i=0; i<n; i++)
    scanf("%d",&take[i]);

    printf("Case %d: %lld\n",cas++,func(0,m,1)%100000007);

    }

    return 0;
    }
    long long func(int i,long long m,int tak)
    {
    if(i==n)
    {
    if(m==0)return 1;
    else return 0;
    }
    if(m==0)return 1;
    if(m=0&&tak<=take[i])ret1=func(i,m-coin[i],tak+1)%100000007;
    ret2=func(i+1,m,1)%100000007;
    dp[i][m][tak]=(ret1+ret2)%100000007;
    return dp[i][m][tak];
    }

    }

  5. ভাই function টা ঠিক মত upload হচ্ছে না। function eta:

    long long func(int i,long long m,int tak)
    {
    if(i==n)
    {
    if(m==0)return 1;
    else return 0;
    }
    if(m==0)return 1;
    if(m=0&&tak<=take[i])ret1=func(i,m-coin[i],tak+1)%100000007;
    ret2=func(i+1,m,1)%100000007;
    dp[i][m][tak]=(ret1+ret2)%100000007;
    return dp[i][m][tak];
    }

    }

  6. EXCUSE ME VAYIA ,
    IF WANT TO SOLVE UVA “SUPERSALE” PROBLEM IN THE CONDITION THAT WE CAN TAKE EACH ITEM ANY NUMBER OF TIMES THEN I THINK 10TH LINE WOULD BE :
    if(w+Weight[i]<=cap)profit1=Cost[i]+max(call(i+1,w+Weight[i]),call(i,w+Weight[i]));
    NOT 12TH LINE :
    int profit2=call(i,w);
    BECAUSE IT NEVER CAUSE THE PROBLEM TO STOP , HENCE RUNTIME ERROR.
    AM I RIGHT ?
    PLZ INFORM ME VAYIA…………..

  7. uva 10130,vaiya why this is showing “time limit”

    where is the problem & why……please answer…..

    #include
    #include
    #include
    #include
    #include
    #include

    using namespace std;

    #define mem(x,y) memset(x,y,sizeof(x));

    int n;
    int dp[1002][102];
    int weight[1002];
    int cost[1002];
    int CAP;

    int func(int i,int w)
    {
    if(i==n+1) return 0;

    if(dp[i][w]!=0) return dp[i][w];

    int profit1=0,profit2=0;

    if(w+weight[i]<=CAP)

    profit1=cost[i]+func(i+1,w+weight[i]);

    profit2=func(i+1,w);

    dp[i][w]=max(profit1,profit2);

    return dp[i][w];
    }

    int main()

    {
    int t;

    scanf("%d",&t);

    while(t–)
    {

    scanf("%d",&n);

    for(int i=1; i<=n; i++)
    {
    scanf("%d%d",&cost[i],&weight[i]);
    }
    int g;

    int total=0;

    scanf("%d",&g);

    while(g–)
    {
    mem(dp,0);

    scanf("%d",&CAP);

    total=total+ func(1,0);
    }

    printf("%d\n",total);
    }
    return 0;
    }

  8. knapsack problem:
    why you used int dp[1002][102]?
    first,1002 ok,because (1 <= N <= 1000).
    but second 102? why ?

    for every person we are calculating highest profit individually
    so w for that person must be in the range of weight capacity
    so why not dp[1002][cap+1]?
    need help vaia…

  9. ভাইয়া , ২ ও ৩ নং কোডের ৬ নং লাইনে if(i>=5) এর যায়গায় if(i>5) হবেনা ? ৫ নং কয়েন টা নিয়েও তো আমাদেরকে কাজ করতে হবে। 🙂

  10. ভাইয়া কয়েন এর প্রবলেমে

    রিটার্ন টাইপ
    return dp[i][amount]=ret1|ret2;
    এইটা দেয়া আছে…।।
    এখানে bitwise operator কি করতেছে এতা বুজতেছি না……।।

  11. লাইটওজেতে 1231 – Coin Change (I)
    কন্ডিশনটা দুইভাবে তুমি হ্যান্ডেল করতে পারো। ৩য় একটি স্টেট রাখতে পারো taken_i যেটা বলে দিবে i নম্বর তুমি কয়বার নিয়েছো,Ci বার ব্যবহার হয়ে গেলে পরবর্তী কয়েনে চলে যাও।
    ভাই এই ভাবে তো টাইম লিমিট পাস করে না ।
    My code :http://pastebin.com/thuhwqqY
    Help

  12. light oj er problem number 1231 e amar ei code er verdict wrong dekhacche….amar vul ta kothay??
    CODE:
    #include
    using namespace std;
    #define MOD 100000007
    int a[200],dp[1003][51],k,cnt,c[200],n;
    int call(int amount,int idx)
    {
    if(idx>n)
    {
    if(amount==k) return 1;
    return 0;
    }

    if(amount>k) return 0;
    if(amount==k) return 1;
    if(dp[amount][idx]!=-1) return dp[amount][idx];
    int ret=0;

    for(int take=1;take<=c[idx];take++)
    {
    if(amount+a[idx]*take<=k)
    ret+=call(amount+a[idx]*take,idx+1)%MOD;
    else break;
    }
    ret+=call(amount,idx+1)%MOD;
    return dp[amount][idx]=ret%MOD;

    }
    int main()
    {
    int t,i;
    long long ans;
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
    int j;
    scanf("%d%d",&n,&k);
    memset(dp,-1,sizeof (dp));
    memset(a,-1,sizeof (a));
    memset(c,-1,sizeof (c));
    for(j=0;j<n;j++)
    {
    scanf("%d",&a[j]);
    }
    for(j=0;j<n;j++)
    {
    scanf("%d",&c[j]);
    }
    ans=call(0,0)%100000007;
    printf("Case %d:%lld\n",i,ans);
    }
    return 0;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *