#include<bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
using ll = int64_t;
using namespace std;
int memo[1001][100001];
int value[1001];
int weight[1001];
int n,C;
int dp(int id, int remW){
if((id==n) || remW==0) return 0;
if(memo[id][remW] != -1){
return memo[id][remW];
}
if(remW < weight[id]){
return memo[id][remW] = dp(id+1, remW); //moved on
}
return memo[id][remW] = max(dp(id+1, remW), value[id]+dp(id+1, remW - weight[id]));
}
void solve(int kes){
//write solution here
cin>>n>>C;
FOR(i, 0, n) cin>>weight[i];
FOR(i, 0, n) cin>>value[i];
memset(memo, -1, sizeof memo);
printf("%d\n", dp(0, C));
}
int main(){
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
//cin>>t;
for(int i = 0; i < t; i++)
solve(t);
}
HINT :
Relate it with Knapsack(classical) and you are good to go.
Recursive DP works with memoization (that too if time complexity is permitted).
I have actually solved it with Knapsack, but the problem is even with memoization the recursive solution is too slow (gets TLE on 2 of the testcases), but iterative solution works fine.
Instead of using m x n 2D array use 2 x n array
REFER THIS FROM Gfg =>https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/
int knapSack(int W, int wt[], int val[], int n) {
}
// Driver Code int main() { int val[] = { 60, 100, 120 }; int wt[] = { 10, 20, 30 }; int W = 50; int n = sizeof(val) / sizeof(val[0]);
}
THe space u r taking is of order of 10^8 which is indeed the reason for time complexity .Try using 2 x n 2D array instead
Refer to my code for more clarification Link: https://cses.fi/paste/2af885b03126b6a436292e/
How is it relevant? In the end, the time complexity is O(n*x)
https://cses.fi/paste/c106d1a30a05424036e90d/
Well, the constraints are a bit tight, but recursion in itself slower than iteration in case of CPP Refer here