মডিউল ১৮_৪ঃ Knapsack Top Down Approach ইমপ্লিমেন্টেশনসহ

এতক্ষন আমরা Knapsack problem টিকে recursion দিয়ে সমাধান করেছি, এখন এই প্রব্লেমটির সমাধানকে আরো optimization করতে গেলে আমরা Memoization করে থাকি, এই Memoization পার্টটি হচ্ছে DP approach।

int knapsack(int n, int weight[], int value[], int W)
{
    if (n == 0 || W == 0)
        return 0;
    if (dp[n][W] != -1)
    {
        return dp[n][W];
    }
    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 dp[n][W] = max(op1, op2);
    }
    else
    {
        // ekta option
        // na niyei dekhte hobe
        int op2 = knapsack(n - 1, weight, value, W);
        return dp[n][W] = op2;
    }
}

আগের কোডটির সাথে যদি compare করা হয়ঃ

এখন আমরা recursive call করার আগেই চেক করে নিচ্ছি যে আমাদের 2D array এর মধ্যে আগে থেকে n, W এর অপশনটি store করা আছে কিনা। যদি থাকে তাহলে সেই অপশনটি আবার বের না করে 2D array থাকা অপশনটি return করে দিয়েছি। যদি র 2D array এর মধ্যে আগে থেকে n, W এর অপশনটি store না থাকে। তাহলে আগের মত recursive call করে op বের করেছি , এখন return করার আগে 2D array এর n,W index এ এখন বের করা অপশনটিকে store করেছি, এরপর সেই অপশনটিকে return করেছি।

এইভাবে Memoization করে আমাদের কোডটির time complexity অনেক কমে যায়।

উপরের চিত্রে visualize করা input টিতে Memoization ছাড়া করলে এইভাবে এতগুলো কল হয়ে থাকে।

এরপর Memoization করলে time complexity অনেক কমে যায়। উপরে কালো মার্ক করা n,W কে নতুন করে আবার বের করতে হয় নি, কারন সেইগুলো আগে বের করা হয়েছিল এবং সেইটিকে 2D array তে store করায়, সেইটি আবার নতুন করে বের করতে হয় নি।

সম্পূর্ণ কোডটি

#include <bits/stdc++.h>
using namespace std;
const int maxN = 1000;
const int maxW = 1000;
int dp[maxN][maxW];
int knapsack(int n, int weight[], int value[], int W)
{
    if (n == 0 || W == 0)
        return 0;
    if (dp[n][W] != -1)
    {
        return dp[n][W];
    }
    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 dp[n][W] = max(op1, op2);
    }
    else
    {
        // ekta option
        // na niyei dekhte hobe
        int op2 = knapsack(n - 1, weight, value, W);
        return dp[n][W] = op2;
    }
}
int main()
{
    int n;
    cin >> n;
    int weight[n], value[n];
    for (int i = 0; i < n; i++)
    {
        cin >> weight[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> value[i];
    }
    int W;
    cin >> W;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= W; j++)
        {
            dp[i][j] = -1;
        }
    }
    cout << knapsack(n, weight, value, W) << endl;
    return 0;
}

Time Complexity: O(n * W)