为我的递归解决方案推导数学公式？

Question

在这个问题中，我们有不同价值的物品，但所有物品的重量都无关紧要。我们有一个利润目标，我们希望通过挑选这些项目来获得利润。但是我们想要最少数量的物品并且物品是无限的。

假设我们的目标是 10，并且我们有值为 1、2、3、4 的项目。我们想要 4,4,2 而不是 3,3,3,1。它们的总价值相同，但我们想要的是具有相同利润的最少数量的商品。

我已经导出了动态和递归的方法来解决它，但对我来说麻烦的是我无法为我的递归方法导出数学公式。

这是我的递归方法

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;
    }

Answer 1

假设您要求的是算法的大 O...

这看起来像是一个简单的暴力求和搜索。不幸的是，这些运行的时间不容易估计，并且取决于输入值及其计数 (N)。我看到的这种解决方案的 Big-O 估计是这样的：

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))

如果我没记错的话。

为我的递归解决方案推导数学公式？

Deriving a mathematical formulation for my recursive solution?

algorithm

recursion

knapsack-problem

time-complexity