০-১ ন্যাপস্যাকঃ বটম আপ ও স্পেস অপটিমাইজেশন টেকনিক

এই টিউটোরিয়ালে আমরা ০-১ ন্যাপস্যাক এর বটম আপ এপ্রোচ নিয়ে কথা বলব! এর আগের পর্বে আমরা প্রব্লেমটি সম্পর্কে বিস্তারিত আলোচনা করেছি এবং প্রব্লেমটি সলভের টপ ডাউন এপ্রোচ সম্পর্কে জেনেছি। এই টিউটোরিয়ালটি পড়ার আগে তাই এই পর্বটিতে একবার ঢুঁ মেরে আসো।

 

টপ ডাউন এপ্রোচে আমরা কি করেছি মনে আছে?? আমরা রিকার্সিভলি নির্দিষ্ট ব্যাগ সাইজের জন্যে একটার পর একটা বস্তু নিয়েছি যাতে ব্যাগটাতে সবচেয়ে বেশি সংখ্যক জিনিস নেয়া যায় এবং যেহেতু প্রব্লেমটির অনেকগুলো ওভারল্যাপিং সাবপ্রব্লেম আছে, সেহেতু আমরা সেগুলোকে ‘Memoization’ পদ্ধতিকে একটি ২-ডি অ্যারেতে স্টোর করে রেখেছি যাতে পরবর্তীতে সেই মানগুলো আমরা ব্যবহার করতে পারি। রিকার্শনের চিত্রটি একটু ভালমত খেয়াল করলে দেখবে আমরা আমাদের ম্যাক্সিমাম ব্যাগের সাইজকে উপরে রেখে একটি করে বস্তু নিয়ে চেক করেছি, ফলে ব্যাগের সাইজ কমেছে এবং রিকার্শন ট্রি তে নিচে নেমেছে। রিকার্শন ট্রি তে উপর থেকে নিচে, অর্থাৎ পজিটিভ কোন একটি মান থেকে শূণ্যের দিকে গিয়েছি বলেই এই পদ্ধতিটিকে টপ ডাউন এপ্রোচ বলে।

 

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

 

কোন একটি বস্তু নেয়ার যুক্তিটি কিন্তু আগের মতই থাকবে। হয় আমরা একটি বস্তু নেব, অথবা নেব না। বস্তুটি নেয়ার সময় অবশ্যই চেক করতে হবে বস্তুটি ব্যাগে আঁটছে কিনা, অর্থাৎ বস্তুটির সাইজ ব্যাগের সাইজের সমান অথবা কম আছে কিনা। এখানে কিন্তু আবার মিঃ বিন এর মত বড় বড় শার্ট, প্যান্ট কাঁচি দিয়ে ছোট করে ব্যাগে ঢোকানো যাবে না! 😛

 

এবার তাহলে কোডটা লিখে ফেলা যাক!

 

int btup()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= s; j++)
        {
            if(w[i-1]<=j)
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+val[i-1]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    return dp[n][s];
}

 

এখানে আমরা প্রত্যেকটা বস্তু নেয়ার সময় দুটি জিনিস দেখছি। যদি আমাদের বস্তুটির সাইজ ব্যাগের সাইজের থেকে বড় হয়, তাহলে আমরা বস্তুটি নিতে পারব না, অর্থাৎ আমাদের ২-ডি অ্যারেতে ব্যাগের ওই সাইজের জন্য আমরা আগের বস্তুটি পর্যন্ত যতটুকু নিতে পেরেছি সেটাই আমাদের ব্যাগের বর্তমান সাইজের অপটিমাম সল্যুশন। কঠিন লাগছে কি? 😕 সমস্যা নেই, একটা উদাহরণ দিয়ে বলি! ধরি, আমাদের কাছে বস্তু আছে ৩টা – ২,৪ ও ৫ সাইজের। আমাদের ব্যাগের সাইজ হল ৭। প্রথমে আমরা ২ সাইজের বস্তুর জন্যে ব্যাগের প্রত্যেকটি সাইজের অপটিমাম ভ্যালু বের করলাম, এক্ষেত্রে ১ ছাড়া বাকি সবকয়টি সাইজের জন্যেই আমরা ব্যাগে বস্তুটি নিতে পারব। এরপর যখন আমরা ৪ সাইজের বস্তুটি বিবেচনায় আনব, তখন কিন্তু আমরা আর ১,২,৩ সাইজের ব্যাগের জন্যে বস্তুটি নিতে পারব না। কিন্তু ব্যাগ কিন্তু তখন খালি নেই, কারণ আমরা এর আগেই ২ সাইজের বস্তুটি নিয়ে নিয়েছি, সুতরাং যখন আমরা ২,৪ দুটি বস্তু বিবেচনায় রেখে ব্যাগের বিভিন্ন সাইজের জন্যে ভ্যালুগুলো বের করব, তখন যদি আমরা বস্তুটি নিতে না পারি, তাহলে আগের আইটেম পর্যন্ত আমরা যতটুকু ভ্যালুর বস্তু নিতে পেরেছি, সেটাই আমাদের অপটিমাম সল্যুশন।

 

আর যদি আমাদের বস্তুটি ব্যাগে ঢোকানো যায়, অর্থাৎ বস্তুর সাইজ ব্যাগের সাইজ থেকে ছোট হয়, সেক্ষেত্রে আমরা সেই আগের মতই বিবেচনা করব, বস্তুটি আমরা নিলে বেশি লাভ হবে নাকি না নিলে বেশি লাভ হবে। দুটি ভ্যালুর মধ্যে ম্যাক্সিমাম ভ্যালুই আমাদের ওই সাইজের ব্যাগের জন্য অপটিমাম সল্যুশন! কনসেপ্টটা আরও একটু ক্লিয়ার করার জন্যে নিচের ছবিটা দেখতে পারোঃ

Knapsack - Bottom Up

স্পেস অপ্টিমাইজেশনঃ

 

আমরা যে ২-ডি অ্যারেটি নিচ্ছি, সেটা (বস্তুর সংখ্যা * ব্যাগের সাইজ) স্পেসের। এখন, যদি আমাদের ব্যাগের সাইজ অনেক বড় হয় অথবা অনেকগুলো বস্তু থাকে, সেক্ষেত্রে অনেকসময় আমাদের কোড build ই হবে না, কারণ এসব ক্ষেত্রে অ্যারের সাইজ এত বড় হয়ে যেতে পারে, যা কম্পাইলার হ্যান্ডেল করতে পারে না। সেক্ষেত্রে কি করা যায়!!!

 

এক্ষেত্রে আমাদের যেই কাজটা করতে হবে – যেভাবেই হোক আমাদের স্পেস কমাতে হবে। কোডটা একটু খেয়াল করে দেখো, ব্যাগের প্রত্যেকটি সাইজের অপটিমাম ভ্যালু বের করার জন্যে শুধুমাত্র এর আগের ইন্ডেক্সের ভ্যালুটা আমাদের দরকার হচ্ছে। তার মানে, আমাদের এর আগে বের করা সব সাইজের ব্যাগের অপটিমাম ভ্যালুগুলো অমূলক! সুতরাং, আমরা যদি আমাদের ২-ডি অ্যারে এভাবে DP[2][n] (n=bag size) ডিক্লেয়ার করি, তাহলেই কিন্তু আমাদের আসল কাজটি হয়ে যাচ্ছে। আমরা যদি প্রথম ভ্যালুটি ০ ইনডেক্সে রাখি, তাহলে পরের ভ্যালুটি ১ নং ইনডেক্সে রাখব এবং সেক্ষেত্রে ০ নং ইনডেক্সের ভ্যালুটি ব্যবহার করব। বুঝতেই পারছো, এর পরের ভ্যালুটি আমরা ০ নং ইনডেক্সে রাখব এবং ব্যবহার করব ১ নং ইনডেক্সের ভ্যালুটি। এই জিনিসটাকেই বলা হয়ে থাকে, ‘স্পেস অপ্টিমাইজেশন’!

 

এটার কোডটা আর লিখলাম না। আইডিয়াটা আগের মতই, শুধুমাত্র স্পেস অপ্টিমাইজ করে লেখার জন্য আগের কোডটিতে ছোটখাটো একটু চেঞ্জ করতে হবে। স্পেস অপ্টিমাইজেশন কোডটা ঠিকঠাকমত লিখেছো কিনা, সেটা বুঝতে নিচের প্রব্লেমটা সলভ করে ফেলতে পারোঃ

 

LKS – Large Knapsack (SPOJ)

Advertisements

2 thoughts on “০-১ ন্যাপস্যাকঃ বটম আপ ও স্পেস অপটিমাইজেশন টেকনিক

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s