Knapsack is a standard problem of dp (Dynamic programming) in which you need to pack a set of items, with given values and sizes (such as weights or volumes), into a container with a maximum capacity.

Identification

You have a container with a maximum capacity given. and given two arrays one array contains value and other containing weight/limits respectively. You have to find optimal value you can obtain within the bag's size limit. and we have a choice along arrays.

Knapsack can be divided into three sub problem.

1. Fractional Knapsack :- Easily solved using Greedy. In this problem you have given all thing that kanpsack have but you can use value in fraction means if you have given a weight $$$4kg$$$ with value of $$$10$$$ then we can use $$$1kg$$$ with a weight of $$$2.5$$$.

2. 0-1 Knapsack :- In this we can use one weight only one time also we can't break into pices. we have to use dp to find solution of this type of problem as we have a choice among array that we can choose it or not, so there must be overlapping subproblem so we have to store value that we had have already obtained.

3. Unbounded Knapsack:- In this type of problem we have no restriction on number of time a element, that means we can use a element any number of times to obtain it. But we can't break a piece into smaller pieces like in fractional knapsack. int this problem we have choice that we can choose a weight or not so this is also solved using DP.

0-1 Knapsack

Problem statment.

Given N items where each item has some weight and profit associated with it and also given a bag with capacity W,The task is to put the items into the bag such that the sum of profits associated with them is the maximum possible.

profit_array[]={1, 4, 2, 3, 5}, Weight_array[]={1, 8 , 5, 7, 9}, W(maximum capacity of bag)= 5.

Thinking process;

we can surely look that we have many choice in which we can get $$$5$$$ as weight like weight = $$$3+2$$$ in which we can get overall profit of $$$7+5$$$, if we choose $$$4+1$$$ we can get a value of $$$8+1$$$, like that.

we have to make choice on every element that we can choose it/pick it or not, here come the recursion in the figure in which we can write a code for a case then it will solve automatic.

we have two choice on every element that we can choose it or not.

Dry Run

lets describe base case and some restricted area

1. We are starting from $$$n-1$$$ index then if reach at $$$0th$$$ index then we have to return it

2. In every case when we are going to choose an index then we have to check that the index we hve choosen its weight is less than or equal to weight avaliable in bag.

Code With recursion

int rec(vector<int> &Weight, vector<int> &value, int i, int w)
{
    if (i == 0)
    {
        if (Weight[0] <= w)
            return value[0];
        return 0;
    }
    int pick = INT_MIN;
    if (Weight[i] <= w)
        pick = value[i] + rec(Weight_arr, value, i - 1, w - Weight_arr[i], dp);
    int not_pick = rec(Weight_arr, value, i - 1, w, dp);
    return max(pick, not_pick);
}
int knapsack0_1 (vector<int> weight, vector<int> value, int n, int maxWeight)
{
    return fn(weight, value, n - 1, maxWeight, dp);
}