SPOJ Dynamic Programming: KNAPSACK

Today I started with solving Dynamic Programming problems and the first one on the refresher list was the classical 0/1-Knapsack.

I found an online judge, SPOJ, testing solutions to this problem here: https://www.spoj.com/problems/KNAPSACK/

Here is my accepted(https://www.spoj.com/status/KNAPSACK,chandniverma/) solution to the same:

import java.util.*;
import java.lang.*;

class Main
{
 public static void main (String[] args) throws java.lang.Exception
 {
  Scanner sc = new Scanner (System.in);
  int s = sc.nextInt();
  int n = sc.nextInt();
  
  int[] size = new int[n+1];
  long[] val = new long[n+1];
  for (int i=1; i<=n; i++) {
   size[i] = sc.nextInt();
   val[i] = sc.nextInt();
  }
  sc.close();
  
  long[][] memo = new long[n+1][s+1];
  for (int i=0; i<=n; i++) {
   for (int j=0; j<=s; j++) {
    memo[i][j] = -1;
   }
  }
  System.out.println(getMaxVal(size, val, s, n, memo));
 }

 private static long getMaxVal(int[] size, long[] val, int s, int n, long[][] memo) {
  if (n<=0 || s<=0)
   return 0;

  if (memo[n][s] != -1)
   return memo[n][s];

  if ((s-size[n]) >= 0) {
   return memo[n][s] = Math.max (
    val[n] + getMaxVal(size, val, s-size[n], n-1, memo),
    getMaxVal(size, val, s, n-1, memo)
    );
  } else {
   return memo[n][s] = getMaxVal(size, val, s, n-1, memo);
  }
 }
}

This solution works with a complexity of O(n*s) where n is the number of items under consideration and s is the size or capacity of the bag.

You can always find my SPOJ profile with solved problem list at https://www.spoj.com/users/chandniverma/.

You can also checkout my recent-most submissions at SPOJ on https://www.spoj.com/status/chandniverma/.

Feel free to share optimisations and improvisations in comments below!

See ya next time!

<3✌