[https://practice.geeksforgeeks.org/problems/0-1-knapsack-problem0945/1#](url) ``` int knapSack(int W, int wt[], int val[], int n) { int t[n+1][w+1]; memset(t,-1,sizeof(t)); if(n==0 || w==0){return 0;} if(t[n][w]!=-1){ return t[n][w];} else{ if(w>=wt[n-1]) t[n][w]=max(val[n-1]+knapSack(w-wt[n-1],wt,val,n-1),knapSack(w,wt,val,n-1)); else t[n][w]=knapSack(w,wt,val,n-1); return t[n][w]; }}}; ```