CodeWithYash

BY RECURSION:  Geeks For Geeks******************************************************************* class Solve{     public int knapsack(int w, int[] arr, int[] val, int n){         if(n==0 || w==0){             return 0;         }         else{             if(arr[n-1]>w){                 return knapsack(w,arr,val,n-1);             }             else{                 return Integer.max(knapsack(w,arr,val,n-1),val[n-1]+knapsack(w-arr[n-1],arr,val,n-1));             }         }     } } class Solution  {      //Function to return max value that can be put in the knapsack of capacity W.         static int knapSack(int w, int wt[], int val[], int n)      {          Solve obj1=new Solve();          int c=obj1.knapsack(w,wt,val,n);          return c;     }  } It will display Time Limit Exceeded Error. ----------------------------------------------------------------------------------------------------------------------------- BY MEMOIZATION Geeks for Geeks ************************************

 import java.util.Scanner; class KnapsackSolve{ public int knapsack(int[] arr, int n, int W , int[] val){ if(n==0 || W==0){ return 0; } else{ if(arr[n-1]>W){ return knapsack(arr,n-1,W,val); } else{ return Integer.max((val[n-1]+knapsack(arr,n-1,W-arr[n-1],val)),(knapsack(arr,n-1,W,val))); } } } } class O1KnapsackRecursion{ public static void main(String arg[]){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int arr[]=new int[n]; int val[]=new int[n]; for(int i=0;i<n;i++){ arr[i]=sc.nextInt(); } for(int i=0;i<n;i++){ val[i]=sc.nextInt(); } int W=sc.nextInt(); KnapsackSolve obj1=new KnapsackSolve(); int c=obj1.knapsack(arr,n,W,val); System.out.println(c); } } Time:O(N*W) Space:O(N*W)

 class Solution {     public long count(int arr[], int m, int n)      {         long t[][]=new long[m+1][n+1];        for(int i=0;i<m+1;i++){            for(int j=0;j<n+1;j++){                if(i==0){                    t[i][j]=0;                }                if(j==0){                    t[i][j]=1;                }            }                    }        for(int i=1;i<m+1;i++){            for(int j=1;j<n+1;j++){                if(arr[i-1]>j){                    t[i][j]=t[i-1][j];                }                else{                    t[i][j]=(t[i-1][j] + t[i][j-arr[i-1]]);                }            }                    }        return t[m][n];             }  } Approach: Dynamic Programming Application of Subset Sum problem with just one modification of traversing one element several times(as it is unbounded knapsack). Time: O(Array Size* Sum)[GFG Time: 0.6/1.5] Space:O(Sum) Thanks For Reading.😇

 class Solution {     public int findTargetSumWays(int[] nums, int target) {         int sum=0;         for(int i=0;i<nums.length;i++){             sum=sum+nums[i];         }         if((sum+target)%2!=0 || target>sum || target<-sum){             return 0;         }         else{             int val=(sum+target)/2;             int t[][]=new int[nums.length+1][val+1];             int count0=0;             for(int i=0;i<nums.length;i++){                 if(nums[i]==0){                     count0++;                 }                 }             //System.out.println(count0);             for(int i=0;i<nums.length+1;i++){                 for(int j=0;j<val+1;j++){                     if(i==0){                         t[i][j]=0;                     }                     if(j==0){                         t[i][j]=1;                     }                 }             }                           for(int i=1;i<nums.length+1;i++){                 for(int j=1;j<val+1;j++){