Here is the link to the question: https://www.spoj.com/problems/SCUBADIV/
Here is my solution:
#include <bits/stdc++.h>
using namespace std;
//oxy,nitro,weight,n,ov,nv
int knapsack(vector<int>oxy,vector<int>nitro,vector<int>weight,int n,int ov,int nv,map<string,int>&mp)
{
string key = to_string(ov)+"|"+to_string(nv)+"|"+to_string(n);
if(n <= 0 && (ov>0 || nv>0))
{
return 999999; // all cylinders explored
}
if(ov <= 0 && nv <= 0)
{
return 0; // base condition
}
if(mp.find(key)!=mp.end())
{
return mp[key];// already explored part
}
return mp[key] = min(knapsack(oxy,nitro,weight,n-1,ov,nv,mp),weight[n-1]+knapsack(oxy,nitro,weight,n-1,max(ov-oxy[n-1],0),max(nv-nitro[n-1],0),mp)); // find min weight.
}
int main() {
// your code goes here
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
scanf("%d",&t);
while(t--)
{
int ov,nv;
scanf("%d%d",&ov,&nv);
int n;
scanf("%d",&n);
vector<int>oxy(n);
vector<int>nitro(n);
vector<int>weight(n);
for(int i=0;i<n;i++)
{
int ox,nx,w;
scanf("%d%d%d",&ox,&nx,&w);
oxy[i] = ox;
nitro[i] = nx;
weight[i] = w;
}
map<string,int>mp;
// c<<knapsack(oxy,nitro,weight,n,ov,nv,mp)<<endl;
printf("%d\n",knapsack(oxy,nitro,weight,n,ov,nv,mp));
}
return 0;
}
However it is giving tle .. Can someone help please?
By keeping passing vector parameter in recursive function you are accident increasing both constant time and code's complexity
I mean you are actually cloning to a new vector and pass it to the next recursive