2

当我阅读背包问题的解决方案（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;
}

我的 non-memoize 方法如下所示，至少对我来说更容易理解，也可以通过 memoization 进行改进。

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) 结果 = Value(n-1,W); 让我更难理解为什么
  3. 对于我的方法的记忆版本，我看到了同样的大 O。还有什么不同吗？

谢谢。

4

1 回答 1

0

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

在第二段代码中，您正在解决无界背包问题，在该问题中，您可以无限次地拿每个物品。

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

于 2013-08-20T02:47:51.523 回答