I am trying to do the knapsack problem without hardcoding the array, how would I do this? Be sure and show all possible solutions! This is important! 

You may assume that the largest capacity (as well as any individual weight) is 100 and the largest number of weights is 25. You may also assume that the weights are sorted from largest to smallest. The basic idea is to send a capacity and an array of weights to a recursive method and to either insert the weight or not. In either case call the method again with a reduced capacity and a shorter array OR with the same capacity and a shorter array. There should be a base case(s) for easy capacity and/or easy array. IF you do it this way, you would probably return another array which would be the potential solution array which of course would only be printed it it is truly a solution. 

Example input: 20 11 8 7 6 5

out: 8 7 5

Here is my code so far: class Knapsack { 

 public static void main(String[] args) throws Exception { 

 int values[] = {10, 40, 30, 50}; 

 int weights[] = {5, 4, 6, 3}; 

 int W = 10; 

 System.out.println(knapsack(values, weights, W)); 

 } 

public int knapsack(int W, int weights[], int values[], int n) { // Base Case if (n == 0 || W == 0) return 0; // If weight of the nth item is more than Knapsack capacity W, then // this item cannot be included in the optimal solution if (weights[n - 1] > W) { return knapsack(W, weights, values, n - 1); } // Return the maximum of two cases: // (1) nth item in the solution // (2) not in the solution else { int included = values[n - 1] + knapsack(W - weights[n - 1], weights, values, n - 1); int not_included = knapsack(W, weights, values, n - 1); return Math.max(included, not_included); } } 

}