মডিউল ১৮_১ঃ Knapsack

আমরা Knapsack বুঝার জন্য নিচে দেয়া প্রব্লেমটি সমাধান করবো।

Problem Link: https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/U

এই প্রব্লেম বলা হয়েছে, আপনাকে N items দেয়া হবে, প্রতিটি item এর একটি weight এবং value দেয়া থাকবে। একটা item কে আপনি শুধুমাত্র একবারই নিতে পারবেন। item গুলোকে রাখার জন্য আপনার কাছে একটি ব্যাগ আছে এবং সেই ব্যাগটিতে একটি নির্দিষ্ট পরিমান পর্যন্ত weight বহন করতে পারে আর সেই weight টি হল W।

weight= [2,3,4,5]

value = [1,3,5,3]

W = 10

int knapsack(int n, int weight[], int value[], int W)
{
    if (n == 0 || W == 0)
        return 0;
    if (weight[n - 1] <= W)
    {
        // duita option
        // niye dekhbo, na niye dekhbo
        int op1 = knapsack(n - 1, weight, value, W - weight[n - 1]) + value[n - 1];
        int op2 = knapsack(n - 1, weight, value, W);
        return max(op1, op2);
    }
    else
    {
        // ekta option
        // na niyei dekhte hobe
        int op2 = knapsack(n - 1, weight, value, W);
        return op2;
    }
}

Knapsack এ আমাদের কাছে দুইটি অপশন থাকে একটি হলো নিয়ে দেখবো এবং আরেকটি হলো না নিয়ে দেখবো।

if (weight[n - 1] <= W)

যখন item টি weight আমাদের ব্যাগের weight W এর সমান অথবা ছোট হবে তখনই আমরা item টিকে নিয়ে অথবা না নিয়ে দেখতে পারবো।

// op1 e niye dekhbo item ti ke,
int op1 = knapsack(n - 1, weight, value, W - weight[n - 1]) + value[n - 1];

// op2 te na niye dekhbo item ti ke,
int op2 = knapsack(n - 1, weight, value, W);

op1 তে আমরা item টিকে নিয়েদেখবো তাই knapsack function টিকে recursive কল করতেছি সাথে এই item টির value যোগ করতেছি এবং কল করা সময় W- weight[n-1] এর মাধ্যমে নিয়া item টির weight বাদ দিয়েছি ব্যাগের weight থেকে কারন আমরা knapsack function টির base case দিয়েছে এমনভাবে যে , item শেষ হয়ে গেলে অথবা ব্যাগের মধ্যে অবশিষ্ট জায়গা না থাকলে return 0 করা হবে।

op2 তে আমরা item টিকে নিচ্ছি না তাই knapsack function কে recursive কল করার সময় শুধুমাত্র item number কে change করে কল করতেছি।

return max(op1, op2);

এরপর op1 এবং op2 থেকে যেই অপশনটি maximum value দিবে আমরা সেইটিকে নিচ্ছি return করতেছি।

else
{
    // ekta option
    // na niyei dekhte hobe
    int op2 = knapsack(n - 1, weight, value, W);
    return op2;
}

যেহেতু item টি weight আমাদের ব্যাগের weight W এর সমান অথবা ছোট না তাই item টিকে নিতে পারবো নাহ। এইজন্য item টিকে নিচ্ছি না তাই knapsack function কে recursive কল করার সময় শুধুমাত্র item number কে change করে কল করতেছি। আর সেই অপশনটিকে return করতেছি।

---

শুরু করলাম

যেহেতু W=10 (ব্যাগের weight) তাই আমরা if condition এ মধ্যে যেতে পারবো এবং, নিয়ে অথবা না নিয়ে দেখতে পারবো।

নিয়ার ফলে knapsack function টি recursive কল হয়েছে এবং W- item 4 এর weight বাদ দেয়া হয়েছে।

এইভাবে বাকি কল গুলোকে complete করা পর এইভাবে maximum value 9 বের ফাইন্ড করে ফেলবো Knapsack দিয়ে।