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

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

<pre class="language-cpp"><code class="lang-cpp"><strong>int knapsack(int n, int weight[], int value[], int W)
</strong>{
    if (n == 0 || W == 0)
        return 0;
    if (dp[n][W] != -1)
    {
        return dp[n][W];
    }
    if (weight[n - 1] &#x3C;= 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;
    }
}
</code></pre>

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

<figure><img src="/files/PgC67SKJuhE63ABMntXv" alt=""><figcaption></figcaption></figure>

এখন আমরা 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 করেছি।&#x20;

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

<figure><img src="/files/W1WIGPTSRURUaiaeh7Oi" alt=""><figcaption></figcaption></figure>

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

<figure><img src="/files/BxVBqLhiQq7yEa4j6qin" alt=""><figcaption></figcaption></figure>

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

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

```cpp
#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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://phitron.gitbook.io/algorithm/knapsack/_-knapsack-top-down-approach.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.