| 8 | // Space: O(n) |
| 9 | #include<bits/stdc++.h> |
| 10 | int ks(vector<int> &val, vector<int> &wt, int ind, int W){ |
| 11 | if(ind==0) { |
| 12 | if(wt[0]<=W) return val[0]; |
| 13 | return 0; |
| 14 | } |
| 15 | int nt=ks(val,wt,ind-1,W); |
| 16 | int t=INT_MIN; |
| 17 | if(wt[ind]<=W) |
| 18 | t=val[ind]+ks(val,wt,ind-1,W-wt[ind]); |
| 19 | return max(t,nt); |
| 20 | } |
| 21 | |
| 22 | int maxProfit(vector<int> &val, vector<int> &wt, int n, int W) |
| 23 | { |