Before discussing about the algorithm, let's understand the problem first.

So, Now the question is What is 0/1 Knapsack Problem ?

Knapsack is like a container or a bag. Suppose we have given some items which have some weights with profits. We have to put some items in the knapsack in such a way total value produces a maximum profit.

For example, suppose we have given an array of weights such that weights = {15, 30, 45} and an array of profits / values such that values = {60, 100, 150} and the total weight of the knapsack means the bag is 50. Now find the maximum profit i.e. maximum values which can be adjusted in the knapsack / bag.

Now, let's discuss the problem follow by the approach : -

Given,

weights = {15, 30, 45}

values = {60, 100, 150}

weight(w) = 50

1st Step - Weight of 1st item is 15 < 50 (w). Therefore, inserting this in the knapsack.

Now, the knapsack has 1 item with value = 60 and weight = 15. But the capacity is 50 that means we can insert more here.

2nd Step - Weight of 2nd item is 30 < 50-15) (w). Therefore, inserting this in the knapsack.

Now, the knapsack has 2 item with value = 60, 100 and weight = 15, 30. But the capacity is 50 that means we can insert more here.

3rd Step - Weight of 3rd item is 45 > (50-15-30) (w). Therefore, we can't insert this into our knapsack.

So, finally the knapsack has 2 item with value = 60 + 100 = (160) and weight = 15 + 30 = (45). So the maximum profit here is 160 which will be our answer means the output.

I hope, the approach will be clear to you. If not then please read it again.

Now moving towards it's algorithm / program using Dynamic Programming : -

Program(C++) using Memorization Method of Dynamic Programming -

#include<iostream>
#include<vector>
using namespace std;
const int N = 1e3+2;
int wt[N], val[N], dp[N][N];
int Knapsack(int n, int w){
    if(n<=0 || w<=0){
        return 0;
    }
    if(dp[n][w]!=-1){
        return dp[n][w];
    }
    if(wt[n-1]<=w){
        dp[n][w] = max(Knapsack(n-1,w-wt[n-1])+val[n-1], Knapsack(n-1,w)); 
    }
    else if(wt[n-1]>w){
        dp[n][w] = Knapsack(n-1,w);
    }
    return dp[n][w];
}
int main(){
    int n;
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>wt[i];
    }
    for(int i=0; i<n; i++){
        cin>>val[i];
    }
    int w;
    cin>>w;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            dp[i][j] = -1;
        }
    }
    cout<<Knapsack(n,w);
    return 0;
}

Program(C++) using Tabulation Method of Dynamic Programming -

#include<iostream>
#include<vector>
#define vi vector<int>
using namespace std;
int main(){
    int n;
    cin>>n;
    vi wt(n);
    for(int i=0; i<n; i++){
        cin>>wt[i];
    }
    vi val(n);
    for(int i=0; i<n; i++){
        cin>>val[i];
    }
    int w;
    cin>>w;

    int t[n+1][w+1];
    for(int i=0; i<n+1; i++){
        for(int j=0; j<w+1; j++){
            if(i==0 || j==0){
                t[i][j] = 0;
            }
        }
    }
    for(int i=1; i<n+1; i++){
        for(int j=1; j<w+1; j++){
            if(wt[i-1]<=j){
                t[i][j] = max(val[i-1]+t[i-1][j-wt[i-1]], t[i-1][j]); 
            }
            else if(wt[i-1]>j){
                t[i][j] = t[i-1][j];
            }
        }
    }
    cout<<t[n][w];
}