মডিউল ১৮_০ঃ ইনট্রডাকশন

আজকের এই মডিউলে দেখবো 0-1 Knapsack Dynamic Programming এর একটি অ্যালগরিদম। 0-1 Knapsack একটি recursive problem যেইটিকে recursion ব্যবহার করে সমাধান করা যায় এবং সেইখানে কিছু অপটিমাইজেশনের কাজ আজকে আমরা করবো। এইটিকে Top Down এবং Bottom Up Approach এ সমাধান করা যায়।

0-1 Knapsack এর মিনিং হচ্ছে choice অথাৎ কোন একটা কিছু নিব অথবা নিব নাহ। নিব বা নিব নাহ এইরকম কোন প্রব্লেম পেলেই আমরা বুঝে নিব সেইখানে 0-1 Knapsack চালানো যাবে।

ধরো তুমি একটি chocolate এর দোকানে গেলা সেইখানে অনেক ধরনের chocolate রয়েছে, ,কিন্তু তুমি শুধুমাত্র ৩টি chocolate নিতে পারবা কারন তোমার ব্যাগে শুধুমাত্র ৩টি chocolate রাখা যায়। এখন তুমি অনেক ধরনের chocolate এর মধ্যে তুমি চেক করবা কোনটা নিবা আর কোনটা নিবা না, অবশ্যই তুমি সেই chocolate টি নিবা যেইটি বেশি মজা অথাৎ যেইটি value বেশি। এইখানেও আমরা 0-1 Knapsack ব্যবহার করে প্রব্লেমটি সমাধান করতে পারি।