I am given the prices of rocks and a value to each rock in arrays. I must recursively (using only the 4 variables listed) check all possible combinations of rocks to find the highest price that is under or equal to the max weight allowed for the rock combinations.

For example:

price = {50, 10, 30, 40} weight = {20, 5, 10, 30} maxWeight = 25; index = 4;

In this case the highest price that can be found is 50, because the weight of 20 is below 25 and the value is 50. This is higher than the weight of 5 + 10 which is also below 25, but their values combined only add up to 40, which is less than 50.

Example 2:

price = {50, 10, 30, 40} weight = {20, 5, 10, 30} maxWeight = 30; index = 4;

In this case the highest price is 80. This is because the weights 20 + 10 add up to the max weight 30, and their values add up to 80. The second highest value would be the weights 20 + 5 which add up to less than the max weight and their values would give 60. The third highest value would be 40 which can be found using either the 5 + 10 weights or the 30 weight.

The method calling these values would look like this:

public static int maxValue(weight[], price[], maxWeight, index) { }

Is it possible to use this method recursively to find the best combination of rocks that are under the max weight and provide the highest price?

Please comment if you have any confusions.

## Answer

Your problem is the well known Knapsack problem and there is not any known efficient algorithm to solve it.

Probably you are looking for the recursive solution:

static int naive_knapSack(int[] v, int[] w, int size, int index) { // no more items if (index >= v.length) return 0; // we cannot use the current item if (size < w[index]) return naive_knapSack(v, w, size, index + 1); // the maximum value will be taking in account the current index OR not return Math.max( naive_knapSack(v, w, size, index + 1), // ignoring this item v[index] + naive_knapSack(v, w, size - w[index], index + 1) // using this item ); }

but, if the knapsack size fit in memory (e.g. less than 4G) exists a dynamic programming solution with `O(n^2)`

cost:

static int knapSack(int[] v, int[] w, int size) { int[][] m = new int[w.length + 1][size + 1]; for (int i = 1; i <= w.length; i++) for (int j = 0; j <= size; j++) m[i][j] = w[i - 1] > j ? m[i - 1][j] : Math.max(m[i - 1][j], m[i - 1][j - w[i - 1]] + v[i - 1]); return m[w.length][size]; }

In that it is basically the same, but each option of the recursion is memoized (it is only calculated once). You would get the same result if you memoize the previous recursive function.

We can compare both outputs

int[] v = new int[]{50, 10, 30, 40}; int[] w = new int[]{20, 5, 10, 30}; // specific cases System.out.println(knapSack(v, w, 25)); System.out.println(knapSack(v, w, 30)); System.out.println(naive_knapSack(v, w, 25, 0)); System.out.println(naive_knapSack(v, w, 30, 0));

with same result (note the first solution **is not 50** is 60)

60 80 60 80

but, the efficiency of the recursive algorithm is exponential when the dynamic programming algorithm is polynomial, to compare using only 34 items

// efficiency int ITEMS = 34; int[] V = IntStream.range(0, ITEMS).map(i -> ThreadLocalRandom.current().nextInt(1, 50)).toArray(); int[] W = IntStream.range(0, ITEMS).map(i -> ThreadLocalRandom.current().nextInt(50, 150)).toArray(); int itemsWeight = Arrays.stream(W).sum(); int capacity = ThreadLocalRandom.current().nextInt(itemsWeight >> 2, itemsWeight >> 1); long t0 = System.nanoTime(); int r1 = naive_knapSack(V, W, capacity, 0); long t1 = System.nanoTime(); int r2 = knapSack(V, W, capacity); long t2 = System.nanoTime(); System.out.printf("r1 = %d, t1 = %f%nr2 = %d, t2 = %f%n", r1, (t1 - t0) * 1e-9, r2, (t2 - t1) * 1e-9);

we get

r1 = 481, t1 = 11,11 seconds r2 = 481, t2 = 0,004 seconds