Is it possible to recursively check the max value of all combinations in a java array-CodePudding

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.

CodePudding user response：

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)

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