knapsack-dp

knapSack_dp.cpp

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<utility>
using namespace std;
  int max(int a,int b)
  {
      return (a>b)? a : b;
  }
 int getMaxProfit(vector<pair<int,int>> item,int n,int c)
 {
     vector< vector<int> >grid(n+1,vector<int>(c+1,0));
     
       int i=1,j=1;
     for(int i=1;i<=n;i++)
     {
         for(j=1;j<=c;j++)
         {
             if(item[i-1].first<=j)
             {
                 grid[i][j]=max(grid[i-1][j],item[i-1].second+grid[i-1][j-item[i-1].first]);
             }
             else
             {
                 grid[i][j]=grid[i-1][j];
             }
         }
     }
       
     
     return grid[n][c];
 }

void getMaxProfit(){
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    vector<pair<int,int>>items;
    pair<int,int>itm;
    int wt,val;
    int N,cap;
    cin>>N>>cap;
    
    for(int i=0;i<N;i++)
    {
        cin>>wt>>val;
        itm=make_pair(wt,val);
        items.push_back(itm);
    }
      //for(int i=0;i<N;i++)
        //  cout<<items[i].first<<" "<<items[i].second<<endl;
    cout<<getMaxProfit(items,N,cap)<<endl;
}
int main()
{  int t;
 cin>>t;
     while(t--)
     getMaxProfit();
}