মডিউল ১৮_২ঃ Knapsack Recursive Approach

প্রথমে নিচের ওয়েবসাইটটিতে যাবেন,

https://recursion.vercel.app/

এরপর Pre-defined templates এর মধ্যে 0-1 Knapsack কে choose করবেন।

এরপর নিচের কোডটি দিয়ে দিবেন এবং Global variables , function call এ মানগুলো সেট করে দিবেন।

def fn(n, W):
  if(n==0 or W==0): return 0
  
  if(weight[n-1] <= W):
    op1 = fn(n-1, W-weight[n-1])+value[n-1]
    op2 = fn(n-1, W)
    return max(op1, op2)
  else:
    op2 = fn(n-1, W)
    return op2

Run button এ ক্লিক করলে visualizationটি show করবে।

এইভাবে আপনি নিজেই 0-1 Knapsack এর recursion এর approach টিকে visualization করতে পারবে।

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

#include <bits/stdc++.h>
using namespace std;
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;
    }
}
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;
    cout << knapsack(n, weight, value, W) << endl;
    return 0;
}

Time Complexity: O(2^n)