Beginning Java Data Structures and Algorithms

Solving the 0-1 Knapsack Problem Using Recursion

To write a code for solving the 0-1 knapsack problem by implementing the recursive approach.

Remember that this is a recursive top-down approach, thus it repeatedly computes the same subproblems for an exponential runtime complexity (2ⁿ). The following code snippet solves this problem using a recursive approach:

public int recursiveAux(int W, int weights[], int values[], int n) {  if (n == 0 || W == 0)    return 0;  if (weights[n - 1] > W)    return recursiveAux(W, weights, values, n - 1);  return Math.max(values[n - 1] +   recursiveAux(W - weights[n - 1], weights, values, n - 1),   recursiveAux(W, weights, values, n - 1)); }

Snippet 4.6: Recursive solution for the 0-1 Knapsack problem. Source class name:  ...