ডাইনামিক প্রোগ্রামিং এ হাতেখড়ি-২

(১ম পর্ব) (সবগুলো পর্ব)

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

 $n$ টা বস্তুর মধ্য থেকে $r$ টা বস্তু কত ভাবে নেয়া যায়?

এখন আমরা $^nC_r$ এর মান কিভাবে ডাইনামিক প্রোগ্রামিং এর সাহায্যে বের করা যায় সেটা নিয়ে আলোচনা করবো। $n$ টা জিনিসের মধ‍্যে $r$ টা জিনিস কতভাবে নেয়া যায় সেটাই $^nC_r$ বা $nCr(n,r)$। এখন যেকোনো একটি জিনিসের কথা চিন্তা কর। তুমি যদি জিনিসটা না নাও তাহলে বাকি $n-1$ টা জিনিসের মধ‍্য থেকে আরো $r$ টা জিনিস নিতে হবে, সেটা করা যায় $nCr(n-1,r)$ ভাবে। আর যদি তুমি জিনিসটা নাও তাহলে বাকি $n-1$ টা জিনিসের মধ‍্যে থেকে আরো $r-1$ টা জিনিস নিতে হবে, সেটা করা যায় $nCr(n-1,r-1)$ ভাবে। এই দুইটার যোগফলই হলো মোট উপায়।

$^nC_{r} =^{(n-1)}C_{r} + ^{(n-1)}C_{(r-1)}$

আমরা যদি মনে করি nCr(n,r) হলো একটি ফাংশন যা n আর r এর মানকে প্যারামিটার হিসাবে গ্রহণ করে তাহলে আমরা উপরের রিলেশন তাকে এভাবে লিখতে পারি:

$nCr(n,r) =nCr(n-1,r) + nCr(n-1,r-1)$

এবার হয়তো জিনিসটা আরো স্পষ্ট হয়েছে তোমার কাছে। কিন্তু রিকার্শনটা শেষ হবে কখন? অর্থাৎ বেস কেস কি? আমরা জানি $nCr(n,1)=n$ এবং $nCr(n,n)=1$ । এ দুটি শর্ত বেস কেস হিসাবে ব্যবহার করলে কোডটা হবে:

ফাংশন কল গুলো লক্ষ্য করলে দেখতে পাবে ফিবোনাচ্চির মতো এখানেও একটি ফাংশন বার বার কল হচ্ছে:

dp2

আমরা এই অতিরিক্ত ফাংশন কল সহজেই এড়াতে পারি আগের মতো একটা টেবিল রেখে। পার্থক্য হলো এবার টেবিলটা হবে ২-ডি,আর কোনো পার্থক্য নেই। আগে টেবিলটার সব ঘরে $-1$ রেখে নিবো, $-1$ দিয়ে বুঝাচ্ছে ঘরটি খালি আছে।

আমাদের সবগুলো ডিপি কোডই মোটামুটি একটা ফরমেট মেনে চলবে,সেটা এরকম:

$^nC_r$ এর ক্ষেত্রে প্যারামিটার ছিলো $n$ এবং $r$। বুঝতেই পারছো যতগুলো প্যারামিটার থাকবে মান টেবিলে সেভ করার জন্য তত ডাইমেনশনের টেবিল লাগবে। স্টেট বেশি লাগলে মেমরিও বেশি লাগে। অ্যারের প্রতিটি ডাইমেনশনের সাইজ প্রয়োজনমতো প্যারামিটার অনুসারে কমবেশি হবে। প্যারামিটারকে আমরা সাধারণত বলে থাকি স্টেট(State)।

ডিপিতে সবথেকে গুরুত্বপূর্ণ অংশ হলো স্টেট বুঝতে পারা। ধরো তোমাকে ৫০মিনিটের মধ্যে একটা ক্লাস ধরতে হবে। এখন রাস্তায় তুমি কোন অবস্থায় আছো সেটা আমি জানতে পারবো যদি তুমি আমাকে দুটি তথ্য দাও: তুমি এই মুহুর্তে কোন জায়গায় আছো আর তুমি বাসা থেকে বের হবার পর কয় মিনিট পার হয়েছে। যেমন হয়তো তুমি ফার্মগেটে আছো আর বাসা থেকে বের হবার পর ২০ মিনিট পার হয়েছে। তুমি কি রঙের জামা পড়েছো বা তুমি কোন জুতা পড়েছো এটা কিন্তু এখানে গুরুত্বপূর্ণ না তাই এটা “স্টেট” এর মধ্যে পড়েনা।

 ০-১ ন‍্যাপস‍্যাক
কোনো এক রাতে তুমি চুরি করতে বের হলে!! বন্ধুর বাসায় জানালা দিয়ে ঢুকে দেখলে প্রচুর জিনিসপত্র,কিন্তু তোমার চুরি করার থলেতে জায়গা আছে মাত্র ১০ইউনিট,এর বেশি নিলে থলে ছিড়ে যাবে। প্রতিটা জিনিসের ওজন আছে আর একেক জিনিসের মুল্যও একেকরকম।

১. মানিব্যাগ: ১ পাউন্ড, ১২০টাকা
২. কোরম্যানের-বই: ৭ পাউন্ড, ৪০০টাকা
৩. ডিভিডি-কালেকশন: ৪ পাউন্ড, ২৮০ টাকা
৪. ফেলুদা-সমগ্র: ৩ পাউন্ড, ১৫০টাকা
৫. ফুটবল: ভর: ৪ পাউন্ড, ২০০টাকা

কোনো জিনিস নিলে পুরোটাই নিতে হবে, ৪টি ডিভিডির ২টি তুমি নিতে পারবেনা,ফেলুদা সমগ্রের অর্ধেক ছিড়ে আনতে পারবেনা। প্রথমদিন চুরি করতে গিয়েছো এই জন্য কিছু না ভেবেই তুমি ফটাফট দামি জিনিসগুলো ভরতে থাকলে। প্রথমেই তুমি ৪০০টাকার কোরম্যানের বই নিয়ে নিলে,তারপর ১৫০টাকার ফেলুদা সমগ্র নিয়ে বাসায় ফিরে আসলে,তোমার লাভ হলো ৫৫০ টাকা। বাসায় এসে হিসাব করে দেখলে তুমি যদি লোভীর মতো (greedy) দামী জিনিসগুলো আগে না নিয়ে একটু ভেবে-চিন্তে নিতে তাহলে ২৮০টাকার ডিভিডি,২০০টাকার ফুটবল আর ১২০টাকার মানিব্যাগ নিয়ে ফিরতে পারতে, তোমার লাভ হতো ৬০০টাকা। greedy অ্যলগোরিদমে অপটিমাল রেজাল্ট না পাওয়ায় তুমি চিন্তা করলে সবরকমের কম্বিনেশনে চেষ্টা করবে, প্রতিবার একটা করে জিনিস থলেতে ভরবে আর দেখবে আর কত লাভ করা যায়,প্রয়োজনে জিনিসটা থলে থেকে নামিয়ে রেখে আরেকটি নিয়ে চেষ্টা করবে। এবং সুবিধার জন্য তুমি লিস্টের সিরিয়াল অনুযায়ী জিনিস নিয়ে চেষ্টা করবে, ৩ নম্বর জিনিসের পরে ১ নম্বর জিনিস নিতে চেষ্টা করবেনা। কোনো সময় তোমার অবস্থা বুঝাতে ২টা তথ্যই যথেষ্ট।

১. তুমি এখন কত নম্বর জিনিস ট্রাই করছো।
২. এখন পর্যন্ত তুমি কত ইউনিট জিনিস নিয়েছো।

তুমি একটা ফাংশন লিখে ফেললে যেটা জিনিসপত্রের লিস্ট থেকে অপটিমাল রেজাল্ট বের করে দিতে পারে। ফাংশনটির রিটার্ন টাইপ আর প্যারামিটার হবে এরকম:

মনে করি i নম্বর বস্তুটির ভর হলো weight[i] আর মূল্য cost[i]। আর ব্যাগের capacity=CAP। প্রতিবার তুমি i নম্বর জিনিসটি নিতে পারো যদি ব্যাগে জায়গা থাকে, অথবা তুমি i নম্বর জিনিসটি না নিয়ে i+1 তম জিনিস ট্রাই করতে পারো। i নম্বর জিনিসটি যদি তুমি নাও তাহলে লাভ হবে cost[i] + পরবর্তি স্টেটে লাভ, তাহলে আমরা cost[i] যোগ করে পরবর্তি স্টেটে চলে গিয়ে কত লাভ হয় সেটা হিসাব করবো।

i নম্বর জিনিসটি যদি তুমি না নাও তাহলেও লাভ বেশি হতে হবে তাই সেটাও আমাদের হিসাব করতে হবে:

লক্ষ্য করো এক্ষেত্রে কারেন্ট প্রফিট বা ওজনের কোনো পরিবর্তন হচ্ছেনা, কোনো কিছু না নিয়েই পরের স্টেটে গিয়ে দেখছি লাভ কত হবে। তাহলে সহজেই বোঝা যাচ্ছে অপটিমাল রেজাল্টের জন্য আমাদের profit1 আর profit2 এর মধ্যে বড়টা নিতে হবে,সেই মানটা আমরা রিটার্ণ করে দিবো।

তাহলে যদি তুমি func(1,0) কল করো তাহলে রিকার্শন তোমাকে রেজাল্ট বের করে দিবে। func(1,0) কল করার কারণ হলো শুরুতে তুমি ১ নম্বর জিনিসটা নিয়ে ট্রাই করবে এবং শুরুতে ব্যাগে সম্পূর্ণ খালি। যখন সবগুলো জিনিস নিয়ে ট্রাই করা হয়ে যাবে তখন রিকার্শন শেষ হবে। যদি $n$ টি জিনিস থাকে তাহলে বেস কেস হবে:

শুন্য রিটার্ন করছি কারণ সবকিছু নেয়া হয়ে গেলে আর প্রফিট করা সম্ভবনা। তোমার বোঝার সুবিধার জন্য সম্পূর্ণ একটা কোড দিয়ে দিলাম:

এই কোডে উপরের উদাহরণের ইনপুটটা নিচের মতো করে দিলে দিলে ৬০০ আউটপুট আসবে

4 10 //৫ টা জিনিস, ১০ ক্যাপাসিটি
1 120 //প্রতিটা জিনিসের ওজন এবং দাম
4 280
3 150
4 200

আমরা উপরের ইনপুটের জন‍্য কিভাবে ফাংশন কলে হচ্ছে তার একটা সিমুলেশন দেখি:

Blank Flowchart - New Page

ছবিতে প্রতিটা নোড প্রকাশ করছে আমরা এখন কোন জিনিসটা নিয়ে কাজ করছি এবং ব‍্যাগে কত ওজনের জিনিস আছে। তারপর জিনিসটা একবার ব‍্যাগে ভরে(যদি জায়গা থাকে) নতুন নোডে যাচ্ছি, আরেকবার না ভরে নতুন জায়গায় যাচ্ছি। নীল রঙ এর নোডগুলো হলো বেস কেস, কারণ আর কোনো জিনিস নেয়ার মত নেই। লক্ষ‍্য কর সবুজ রঙ এর নোডটায় একাধিক পথে আসা যায়, তাই আমরা প্রতিটি নোডের রিটার্ণ ভ‍্যালু ডিপি অ‍্যারেতে সেভ করে রাখবো।

কমপ্লেক্সিটি:

আমাদের কোডে ভিন্ন ভিন্ন স্টেট সংখ‍্যা $n*cap$ টা যেখানে $n$ হলো জিনিস সংখ‍্যা আর $cap$ হলো ব‍্যাগের ক‍্যাপাসিটি। ফাংশনের ভিতর কোনো লুপ নেই। তাই মোট $O(n*cap)$ টাইম কমপ্লেক্সিটিতে কোডটা চলবে। ডিপি অ‍্যারের আকার হবে $n \times cap$ , তাই স্পেস কমপ্লেক্সিটিও  O(n \times cap)।
এখন ছোট্ট একটা প্রশ্ন, ডিপি প্রবলেমে টাইম আর স্পেস কমপ্লেক্সিটি ভিন্ন হবে কখন?

এটাই হলো ক্লাসিকাল 0-1 knapsack প্রবলেম,ন্যাপস্যাক শব্দটির অর্থ হলো থলে। ০-১ নাম দেয়ার কারণ হলো তুমি কোনো জিনিস অর্ধেক নিতে পারবেনা,হয় পুরোটা নিবে অথবা নিবেনা। fractional-knapsack বলে আরেক ধরণের প্রবলেম আছে,সেটার আলোচনা অন্য কোনোদিন হবে। ন্যাপস্যাকে সলিউশন প্রিন্ট করা শিখতে সিরিজের চতুর্থ পর্বটা দেখো।

এখন তোমার এখন কাজ হলো এটার সম্পূর্ণ কোড ইমপ্লিমেন্ট করা। uva 10130 প্রবলেমটি সলভ করতে চেষ্টা করো।

ডাইনামিক প্রোগ্রামিং এ ভালো করার একমাত্র উপায় হলো প্রচুর চিন্তা করা। তোমাকে অনুরোধ করবো পরবর্তি পর্ব পড়ার আগে অবশ্যই আগের পর্বের সমস্যাগুলো নিয়ে খুব ভালো করে অন্তত ১দিন চিন্তা করবে।

(সবগুলো পর্ব)
পরের পর্ব-কয়েন চেঞ্জ,রক ক্লাইম্বিং

Print Friendly

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

comments

Powered by Facebook Comments

65,188 বার পড়া হয়েছে

34 thoughts on “ডাইনামিক প্রোগ্রামিং এ হাতেখড়ি-২

  1. কোডটি করেছি… Accepted ও হয়েছে…কিন্তু রান টাইম তো অনেক বেশি !!! 🙁
    1.088 sec !!!
    কমানো যায় না ??? contest time এ Time Limit পাবো নাতো ???

    1. হয়তো কমানো যায়। ডিপি অ্যারে বার বার initialise না করে একটা বুলিয়ান অ্যারে দিয়ে কাজটা করলে রানটাইম কমবে। যেমন:
      if(dp[n][r]!=-1) return dp[n][r]; এটার যায়গায় লেখা যায়:
      if(vis[n][r]==1) return dp[n][r];
      vis[n][r]=1;
      এখানে vis একটা বুলিয়ান অ্যারে,তাই memset করতে অনেক কম সময় লাগবে।

  2. [
    এডিট: নতুন ছবি আপলোড করে দিলাম, কমেন্ট বক্সের নিচে লাল রঙে লিখে রেখেছি “(ইংরেজী ফন্টে বাংলা মন্তব্য মুছে ফেলা হতে পারে)” তাই কমেন্টটা ছাপালামনা, আগে এ ধরণের মন্তব্য ছাপালেও এখন থেকে না ছাপানোর সিদ্ধান্ত নিয়েছি।ধন্যবাদ।
    –শাফায়েত
    ]

    1. freopen ফাংশন দিয়ে ফাইল থেকে ইনপুট নেয়া যায়, scanf ফাংশন কিবোর্ড থেকে ইনপুট না নিয়ে “in” নামের ফাইল থেকে নিবে, বারবার ইনপুট কপি-পেস্ট করার থেকে এটা অনেক সুবিধা।
      memset দিয়ে ডিপি অ্যারের প্রতিটি পজিশনে -1 বসিয়েছি।

      1. ‘memset’ ব্যাবহার করলে কোডব্লক্সে এই লাইটা আসেঃ
        D:\Books\Code\Online Judge\New-1 knapsack.c|31|warning: incompatible implicit declaration of built-in function ‘memset’|
        আর আমার আঊটপুট 600 না দেখিয়ে 0 দেখাচ্ছে।
        কোড লিঙ্কঃ http://ideone.com/oPDnE3

        1. কোডের অনেক জায়গাতেই সমস্যা আছে, তুমি কি কোড ঠিকমতো চেক করেছো? আরেকজনকে কোড দেয়ার আগে নিজে ভালোমত কয়েকবার ডিবাগ করবে। for(i=0; i

  3. লাইট ওযে এর ১০০৬ নাম্বার প্রবলেমটা accepted হচ্ছেনা… ওভারফ্লো হচ্ছে এই ইনপুট এর জন্যঃ ১ ৯৯৯৯ ৯৯৯৯ ৯৯৯৯ ৯৯৯৯ ৯৯৯৯ ৯৯৯৯৯ ৯৯৯৯

    আমার কোডঃ
    http://pastebin.com/Yn2CGiCd

    1. cin বাদ দিয়ে scanf নাও। তবে আসল সমস্যা হলো dp অ্যারেটা মেমসেট করতে অনেক সময় লাগছে, 1000*50 ডাইমেনশন নাও, AC হবে। ডিপি প্রবলেমে সবসময় এই ব্যাপারটা খেয়াল রাখতে হবে, যত বেশি মেমরি নেয়া হবে সেটা মেমসেট করতে তত বেশি সময় লাগবে।

  4. ভাইয়া, আমার কোড আমার pc তে ঠিকমতো কাজ করছে। কিন্তু UVA তে wrong answer দেখাচ্ছে। critical input গুলো কী বলা যাবে? আর আমার কোডটা একটু চেক দেখবেন প্লিজ। http://ideone.com/HaQsCu

  5. ভাইয়া ফাহিম ভাইয়ের ব্লগ থেকে জোবায়ের ভাই এর ব্লগ এর লিঙ্ক টা পাই । লিঙ্ক ঃ
    http://zobayer.blogspot.com/2009/12/cse-102-attacking-recursion.html

    ভাইয়া এখান থেকে একটা নতুন তথ্য পেয়েছি । সেটা হোলো প্রায় যেকোনো লুপিং এর কোড নাকি রিকার্শন এর মাধ্যমে করা যায় । ওখানে আপনার একটা কমেন্ট ও দেখেছিলাম । মানে আপনিও ব্লগটি পরেছেন ।

    এখন সমস্যা টা হোলো Incremental for লুপ টা রিকার্শনের মাধ্যমে ভালোভাবেই বুঝতে পেরেছি । কিন্তু Decremental for লুপ টা তে একটু সমস্যা হচ্ছে । যদিও চিত্র টা দেখে কিছুটা বুঝেছি তারপরো খটকা রয়ে গেছে ।
    => একই রকম রিকার্শন এর কোড কিন্তু কাজ করবে দুটো দু রকম । এ জায়গাটায় একটু প্রব্লেম আছে । এটা কি একটু ক্লিয়ার করে দেয়া যায় ??
    ধন্যবাদ ।

  6. // vaiya amar nCr code ki vul hobe ? Please dekhben.
    #include
    using namespace std;

    long int c[1002][1002];
    long int dp(int n,int r)
    {
    if(n<r) return c[n][r]=0;
    if(r==0||(n==1 && r==1)) return c[n][r]=1;
    if(c[n][r]!=-1) return c[n][r];
    else return c[n][r]=dp(n-1,r)+dp(n-1,r-1);
    }
    int main()
    {
    int n,r;
    memset(c,-1,sizeof(c));
    scanf("%d%d",&n,&r);
    dp(n,r);
    printf("%d",c[n][r]);
    return 0;
    }

Leave a Reply

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


Time limit is exhausted. Please reload CAPTCHA.