Container loading recursive

Problem

There are some containers with different weights. A ship can hold maximum W weight. The problem is to find out what is the maximum we can load this container using the containers so that it does not exceeds W

Problem variation

An integer array is given, and an integer k is given. Find out the maximum sum possible using the elements of the array which does not exceed k

Solution

This is similar to the previous problem of finding out whether we can make a sum of k using the numbers. But here instead of trying to make k as the sum, we try to reach as near as possible to the number k but not more than k. In a similar fashion we will use dynamic programming to solve this problem. We will device a function which takes to key parameters index and sum and returns the maximum sum possible not exceeding sum. And using the items from index to end of the array. So at every recursion we have two choice whether to include the index-th element in the optimal solution or not. Suppose our function signature is func(index,sum), then func(0,k) returns the final answer. So at each step if the index-th element is included then the final sum becomes element+func(index+1,sum-element). Whereas if it is not included then the sum is func(index+1,sum). The functions examine these two values by calling recursive functions and returns the greater of these two. To minimize the complexity we keep a two dimensional integer array which is initialized after computing the value of func. So that later call to the function with same value does not need recomputation. In this way we calculate only once per cell of the two dimensional array. As the array dimensions are n and k, the complexity is O(nk).

Code

public class MaximumSumUptoKRecursive
{
 public static void main(String[] args)
 {
  int[]arr={4,6,3,9};
  System.out.println(getMaxSum(arr, 14));
 }
 public static int getMaxSum(int[]arr,int k)
 {
  Integer[][]memo=new Integer[arr.length+1][k+1];
  return getMaxSum(memo,arr,0,k);
 }
 private static int getMaxSum(Integer[][]memo,int[]arr,int i,int k)
 {
  if(i==arr.length)
  {
   return 0;
  }
  if(memo[i][k]!=null)
  {
   return memo[i][k];
  }
  if(arr[i]>k)
  {
   memo[i][k]=getMaxSum(memo,arr, i+1, k);
   return memo[i][k];
  }
  memo[i][k]=Math.max(getMaxSum(memo,arr,i+1,k), 
   getMaxSum(memo,arr,i+1,k-arr[i])+arr[i]);
  return memo[i][k];
 }

}

Index