Consider the following instance of knapsack problem:

No. of objects n=3, knapsack capacity m=20 profit (p1,p2,p3)= (25, 24, 15) and weight (w1, w2,w3)=(18, 15, 10)

Given,

weights = {18, 15, 10}

values = {25, 24, 15}

weight(w) = 20

Here, the weight of the knapsack is 20. So, we can only put any 1 item in the knapsack.

On putting, 1st item - value will be 25 and weight will be 18.

On putting, 1st item - value will be 24 and weight will be 15.

On putting, 1st item - value will be 15 and weight will be 10.

Since, value 25 is maximum and it's weight is also less than the knapsack.

So, we will put only 1st item in the knapsack.

So, the program for this question using Dynamic Programming will be : -

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];
}