java - 为什么背包实现需要 n 作为参数

Question

当我阅读背包问题的解决方案(http://en.wikipedia.org/wiki/Knapsack_problem)时，我不明白为什么参数中有迭代次数 n。看来我们可以通过检查传递的限制来得出叶用例。前任。 15KG 背包问题，解决方案如下:

Value(n, W){ // W = limit, n = # items still to choose from
    if (n == 0) return 0;
    if (arr[n][W] != unknown) return arr[n][W]; // <- add memoize
    if (s[n] > W) result = Value(n-1,W);
    else result = max{v[n] + Value(n-1, W-w[n]), Value(n-1, W)};
    arr[n][W] = result;                // <- add memoize
    return result;
}

我的非内存方法如下所示，它更容易理解，至少对我来说是这样，并且还可以通过内存来改进。

static int n =5;
static int [] w = new int[]{12,2,1,4,1}; //weight
static int [] v = new int[]{4,2,1,10,2}; //value
public static int knapSack(int wt){
    int maxValue = 0,vtemp = 0, wtemp =0;
    if (wt ==0) return 0;
    for (int i=0; i<n; i++){
        if (w[i] > wt) continue;
        int tmp = v[i] + knapSack(wt - w[i]);
        if (tmp > maxValue){
            maxValue = tmp;
            vtemp = v[i];
            wtemp = w[i];
        }
    }
    System.out.println("wt="+wt + ",vtemp="+vtemp+",wtemp="+wtemp+",ret max="+maxValue);
    return maxValue;
}

所以我的问题是:

1. 为什么我们需要 n 作为参数？
2. 语句 if (s[n] > W) result = Value(n-1,W);让我更难理解为什么
3. 对于我的方法的内存版本，我看到了同样的大 O。还有其他区别吗？

谢谢。

Answer 1

您实际上是在解决一个不同的问题。第一段代码(带有 n)解决了 0-1 背包问题，您可以在其中选择至多拿取任何特定项目中的一个(即没有“复制”项目)。在这种情况下，您需要 n 来跟踪您已经用完的项目。

在第二段代码中，您要解决无界背包问题，在该问题中您可以无限次拿走每件元素。

它们都是 NP 完全背包问题的形式，但它们有不同的解决方案。