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

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

假设您要求的是算法的 Big-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))

如果我没记错的话。