০-১ ন্যাপস্যাকঃ টপ ডাউন

ধরো, তুমি একদিন লটারিতে ফার্স্ট প্রাইজ জিতেছো! তো আগেই বলা ছিল, লটারীতে ফার্স্ট প্রাইজ জিতলে ৫টা আকর্ষণীয় গিফট দেয়া হবে – এর মধ্যে আছে আইফোন, ম্যাকবুক, প্লে স্টেশন, ডিএসএলআর ক্যামেরা আর নগদ ১ লক্ষ টাকা। উফফ, ভাবতেই ফিলিং বড়লোক! 😀 নাচতে নাচতে জিনিসগুলো আনতে গিয়ে দেখলা, সাথে ছোট্ট করে লেখা ছিল ‘শর্ত প্রযোজ্য’ যেটা তুমি আগে দেখো নাই। শর্তটা হচ্ছে, তোমাকে একটা ব্যাগ দেয়া হবে এবং ওই ব্যাগে ৪ কেজির বেশি জিনিস নেয়া যাবে না। রক্ত তো মাথায় চড়ে গেল! 😡 কিন্তু এখন কিছুই করার নাই। তোমার এখন যা করণীয় তা হচ্ছে, যেভাবেই হোক সবচেয়ে বেশী লাভ করা এবং যেভাবেই হোক ওই লটারীর আয়োজককে বাঁশ দেয়া। তার মানে তুমি এমনভাবেই জিনিসগুলো নিতে চাইবে যাতে সর্বোচ্চ যত দামী জিনিস নেয়া সম্ভব, ততটাই নিতে পারো।

 

বাঁশ দিতে গিয়ে তুমি কিন্তু কোন জিনিস নষ্ট করে দিয়ে আসতে পারো না। কারণ ল্যাপটপের অর্ধেক অংশ ভেঙে শুধু স্ক্রিণটা নিয়ে আসলে তোমার কোন লাভ হচ্ছে না। এটার জন্যেই আসলে এই প্রব্লেমটার নাম হয়েছে ০-১ ন্যাপস্যাক। অর্থাৎ হয় তুমি কোন জিনিস নিতে পারবে, অথবা নিতে পারবে না। কোন জিনিসের শুধু কোন একটা অংশ আলাদা করে নেয়া যাবে না।

 

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

 

প্রব্লেমটা আগে পড়ে ফেলো একবারঃ

 

KNAPSACK – The Knapsack Problem

 

প্রব্লেমটায় বলা আছে যে, তুমি সাগরে ঘুরতে যাচ্ছো, একটা নির্দিষ্ট S সাইজের ব্যাগ নিয়ে। তোমার কাছে N সংখ্যক জিনিস আছে। জিনিসগুলোর প্রত্যেকটিরই একটি নির্দিষ্ট সাইজ এবং ভ্যালু আছে। তোমাকে এমনভাবে জিনিসগুলো নিতে হবে যাতে ভ্যালু সর্বোচ্চ হয়। একদমই বেসিক ০-১ ন্যাপস্যাক প্রব্লেম।

 

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

 

যেহেতু সবচেয়ে বেশি ভ্যালু ব্যাগে নিতে হবে, সেহেতু প্রথমেই যেই এপ্রোচ মাথায় আসার কথা সেটা হচ্ছে Greedy Approach.  কিন্তু গ্রিডী এপ্রোচ এখানে কাজ করবে না। তুমি হয়ত লোভীর মত প্রথমেই সবচেয়ে দামী জিনিসটা নিলে যেটার ওজন অনেক বেশি, তাই ব্যাগে আর কোনকিছু নেয়ার জায়গায়ই থাকল না। কিন্তু ওই একটা ভারী জিনিসের জায়গায় তুমি যদি অনেকগুলো কম ওজনের ছোট ছোট জিনিস নাও, তাহলে ওই সবগুলোর মোট দাম কিন্তু ওই একটা জিনিসের মোট দামের থেকে বেশি হতে পারে। তাই ভাবিয়া করিও কাজ, করিয়া ভাবিও না।

 

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

 

‘লোভে পাপ, পাপে WA’

 

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

 

টপ-ডাউন এপ্রোচঃ টপ-ডাউন মেথড বোঝার জন্য প্রথমেই রিকার্শন বুঝতে হবে। রিকার্শন না বুঝে থাকলে এখান থেকে ঘুরে আসতে পারো।

 

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

 

ans = max(knap_sack(bag_sz,item+1), value[item] + knap_sack(bag_sz-weight[item], item+1));

 

knap_sack হচ্ছে আমাদের রিকার্সিভ ফাংশন, যেটা রিকার্সিভলি আমাদের আসল উত্তরে আমাদের পৌছে দেবে।

 

যেকোন রিকার্শনের ক্ষেত্রে প্রথমেই যে জিনিসটা নির্ধারণ করতে হয়, সেটা হচ্ছে বেসকেস। কারণ রিকার্সিভ ফাংশন টার্মিনেট করার কন্ডিশন ঠিক করে না দিলে রিকার্শন অনন্তকাল ধরে চলতেই থাকবে। এখানে বেসকেস মূলত ২টা,

১) ব্যাগের সাইজ যদি ০ হয়ে যায়, অর্থাৎ আর কোন জিনিস না নেয়া যায় এবং আইটেমের সংখ্যা যদি আমাদের নির্ধারিত আইটেমের সংখ্যার থেকে বেশি হয়ে যায় অর্থাৎ আর কোন জিনিস যদি নেয়ার না থাকে তবে আমরা ০ রিটার্ন করে দেব।

২) ব্যাগের সাইজ যদি নেগেটিভ আসে, তার মানে ওই জিনিসটা নেয়ার মত জায়গা আমাদের ব্যাগে নেই। কিন্তু আমরা কিন্তু প্রথমেই জিনিসটার ভ্যালু যোগ করে দিয়েছি আমাদের এন্সারে, তাই এই ভ্যালুটা আমাদের বিয়োগ করে দিতে হবে।

 

if(bag_sz < 0)

        return –value[item];

 if(bag_sz==0 || item > n)

        return 0;

 

প্রব্লেমের টেস্টকেসটার ক্ষেত্রে রিকার্সিভ ফাংশনটা কিভাবে কাজ করবে সেটা নিচের ছবিতে দেখানো হয়েছে

 

Knapsack
যেকোন ফাংশন থেকে বামে – যখন জিনিসটি নেয়া হচ্ছে এবং ডানে – যখন জিনিসটি নেয়া হচ্ছে না

 

এখানে তো আমরা সিম্পল একটা রিকার্সিভ ফাংশন লেখলাম, ডিপি কোথায় ব্যবহার করলাম। 😕 যদি এই কয়টা লাইন দিয়ে রিকার্সিভ ফাংশনটা লিখে ফেলতে পারো, তাহলে সাবমিট দিয়ে দেখতে পারো। নগদে তোমাকে TLE(Time Limit Exceeded) দেখাবে।

 

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

 

আগে লেখা লাইনটার তাহলে এই ছোট্ট পরিবর্তন করতে হবে আর সাথে একটা শর্ত জুড়ে দিলেই হবেঃ

 

if(dp[bag_sz][item]!=-1)

        return dp[bag_sz][item];

dp[bag_sz][item] = ans = max(knap_sack(bag_sz,item+1), val[item] + knap_sack(bag_sz-w[item], item+1));

 

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

 

ছোট্ট এই উদাহরণটার জন্যে হয়ত মনে হতেই পারে, এ আর এমন কি, কয়েকটাই তো মাত্র কাজ। কিন্তু যখন S,N উভয়ই অনেক বড় হবে, তখন কিন্তু এই একই কাজ বারবার করার পরিমাণটা অনেক বেশি বেড়ে যাবে। এজন্যেই, শুধুমাত্র রিকার্সিভ ফাংশন লিখে প্রথমবার তুমি TLE খেয়েছো!

 


int knap_sack(int bag_sz, int item)
{
    if(bag_sz < 0)                  
        return -val[item-1];          
    if(bag_sz==0 || item > n)
        return 0;
    if(dp[bag_sz][item]!=-1)
        return dp[bag_sz][item];
    dp[bag_sz][item] = ans = max(knap_sack(bag_sz,item+1), val[item] + knap_sack(bag_sz-w[item], item+1));

    return ans;
}

 

এটুকু বুঝতে পারলে নিচের প্রব্লেমগুলো সলভ করে ফেলতে পারোঃ

 

RPLB – Blueberries (SPOJ)

10664 – Luggage (UVA)

 

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 )

Connecting to %s