0 1 Knapsack Problem

#include<iostream>
#include<bits/stdc++.h>
using namespace std;



int main()
 {
	int T;
	cin>>T;
	while(T--)
	{
	    // n=Number of elements w=Total Weight
	    int n,w;
	    cin>>n>>w;
	    
	    // Weight of a Produt
	    vector<int> wt(n);
	    
	    // Profit we will get for each Product
	    vector<int> profit(n);
	    
	    
	    
	     for(int i=0;i<n;i++)
	        cin>>profit[i];
	        
	     for(int i=0;i<n;i++)
	        cin>>wt[i];
	   
	    
	    int dp[n+1][w+1];
	    
	    
	    // Intialize DP Matrix
	    for(int i=0;i<=n;i++)
	        dp[i][0]=0;
	    for(int j=0;j<=w;j++)
	        dp[0][j]=0;
	    
	    
	    for(int i=1;i<=n;i++)  // Products
	    {
	        for( int j=1;j<=w;j++)  // Total weights
	        {
	            if(wt[i-1] > j)  // Neglect the current Product
	                dp[i][j]=dp[i-1][j];
	            else  // We can Consider it
	            {
	                dp[i][j]=max(dp[i-1][j],profit[i-1] + dp[i-1][j-wt[i-1]]);
	            }
	            
	        }
	    }
	    
	    // Print the DP matrix
	    
	    for(int i=0;i<=n;i++)
	    {
	        for(int j=0;j<=w;j++)
	            cout<<dp[i][j]<<" ";
	       cout<<end;
	    }
	    
	    //Finding which Elements are considered
	    int j=w;
	    int i=n;
	    list<int> considered;
	    while(i!=0)
	    {
	        if(dp[i][j]==dp[i-1][j])
	        {
	            i--;
	        }
	        else
	        {
	           considered.push_front(i); 
	           j=j-wt[i];
	           i--;
	        }
	    }
	    for(auto i:considered)
	        cout<<i<<" ";
	    cout<<endl;
	       
	}
	return 0;
}