Deriving a mathematical formulation for my recursive solution?-CodePudding

In the question we have items with different values but all of the items weight doesn't matter. We have a goal of profit that we want to have by picking those items. But we want to have least amount of items and items are infinite.

So let's say our goal is 10 and we have items with values of 1,2,3,4. We want to have 4,4,2 rather than 3,3,3,1. They have same total value but what we wanted was the least amount of items with the same profit.

I already derived both dynamic and recursive methods to solve it but the trouble for me is that I just can not derive a mathematical formula for my recursive method.

Here is my recursive method

static int recursiveSolution(int[] values, int goal, int totalAmount) {
        if (goal == 0)
            return totalAmount;
        if (goal < 0)
            return Integer.MAX_VALUE;
        totalAmount  ;
        int minAmount = Integer.MAX_VALUE;
        for (int i = 0; i < values.length; i  ) {
            minAmount = Math.min(minAmount, recursiveSolution(values, goal - values[i], totalAmount));
        }
        return minAmount;
    }

CodePudding user response：

Assuming that what you are asking for is the Big-O of your algorithm...

This looks like a simple brute-force summation search. Unfortunately, the run-time of these are not easy to estimate and are dependent on the inputs values as well as their count (N). The Big-O estimates that I have seen for this type of solution are something like this:

Let 
    N = the number of values in the `values[]` array,

    Gv = PRODUCT(values[])^(1/N)
        (the geometric mean of the `values[]` array),

    M = the target summation (`totalAmount`),

Then the complexity of the algorithm is (very approximately)

    O(N^(M/Gv))

If I recall this correctly.