মডিউল ১৮_৫ঃ Knapsack Bottom Up Approach

আগের সেই Knapsack এর ইনপুটটি দিয়ে এখন আমরা Knapsack Bottom Up Approach টি দেখব।

weight= [2,3,4,5]

value = [1,3,5,3]

W = 10

Knapsack Bottom Up Approach বুঝার জন্য নিচের দেখানো চিত্রের মত একটি টেবিল একে ফেলবো।

এখন শুরুতে আমরা base case চিন্তা করলে দেখি n==0 || W==0 হলেই return 0 করতাম , এখন Bottom Up Approach এ 0 row এবং 0 column এ 0 রেখে দিব।

নিচের চিত্রে n=1 , W=1 index এ কি মান বসবে সেইটির প্রসেসটি দেখিয়েছি।

নিচের চিত্রে n=1 , W=2 index এ কি মান বসবে সেইটির প্রসেসটি দেখিয়েছি।

এইভাবে বাকি গুলো প্রসেস সম্পন্ন হওয়ার পর dp নামের 2D array টি এইরকম হবে।

আমাদের উপরের প্রশ্নের n=4 এবং W=10 ছিল তাহলে, dp[4][10] হল 9, এইটি উত্তর।