背包问题动态规划解法的时间复杂度

Question

我在这里看到了0-1背包问题的递归动态规划解决方案。我对此进行了记忆化并编写了以下代码。

private static int knapsack(int i, int W, Map<Pair<Integer, Integer>>, Integer> cache)
{
 if (i < 0) {
    return 0;
 }
Pair<Integer, Integer> pair = new Pair<>(i,W);
if (cache.contains(pair)) {
  return cache.get(pair)
}
int result = -1;
if (weights[i] > W) {
    result = knapsack(i-1, W);
} else {
    result = Math.max(knapsack(i-1, W), knapsack(i-1, W - weights[i]) + values[i]);
}
cache.put(pair, result);
return result;
}

能否有人向我解释一下，为什么时间复杂度应该是O(nW)，其中n是物品的数量，W是重量限制。

- Lee

Answer 1

是的，这就是我不喜欢递归的原因之一。你几乎总是可以将递归算法重写为仅使用循环而没有递归的算法。以下是仅使用for循环的算法：

A[i,j]=0 for j=0, 1, ..., W

For i=1, 2, ..., n
    For j=0, 1, ..., W
        A[i,j]=max(A[i-1,j], A[i-1,j-weight[i]]+value[i] // or 0 if the index is invalid

Return A[n,W]

很明显，这里的复杂度是O(nW)。我将留给您与您的代码进行比较。

- Ali

---

谢谢，阿里。我似乎喜欢递归的原因不同。一旦你为典型的动态规划问题想出了递归关系，它就非常容易实现。 - Lee

@Lee 无论如何，我希望我的答案能在一定程度上帮助你理解它的复杂性。 - Ali

Answer 2

如果你思考一下在DP的表格实现中，这个表格会是怎样的，就会更加明显。它有一个轴上的项目和另一个轴上的最大可达重量，每个可能的整数重量都有一行。对于某些重量集，为了找到最优答案，表格必须密集地填充。对于这些相同的重量集，您的备忘录哈希将需要Omega(nW)对，因此每个条目都是常数时间计算，计算所有的时间是相同的。思考如何获得成本高昂的重量集是一个很好的练习，我会把这个留给你。

- Gene

---

非常感谢。我现在理解得更好了。另外，如果你可以得出一个O(nW)的解决方案，为什么这个问题被认为是NP-难的呢？ - Lee

NP难问题是基于输入长度的运行时间定义的。若W的长度为ceiling（log W），则O（W）与O（2 ^＃W中的位数）相同，即指数时间。这类算法被称为“弱NP难问题”。 - Gene

Answer 3

可以通过子问题图来呈现递归动态规划算法。

子问题图由类似于非重叠子问题的顶点组成。而顶点中的有向边则表示递归调用。这些边实际上代表了子问题之间的依赖关系。

The runtime of the dynamic algorithm = (time to solve each subproblem)*(number of unique subproblems)

通常情况下，

the cost = (outdegree of each vertex)*(number of vertices)

对于背包问题，

每个顶点的出度最多为2=O(1)。这是因为在每个子问题中，我们尝试以最多两种方式解决它。

现在，如果我们检查子问题，我们可以找到一些模式，

The subproblem `(n,W)` depends on `(n-1,W)` and `(n-1,W-w(n))`.

`(n-1,W)` depends on `(n-2,W)` and `(n-2,W-w(n-1))`
`(n-1,W-w(n))` depends on `(n-2,W-w(n))` and `(n-2,W-w(n)-w(n-1))`

请注意，每个项目的重量最多可以变化为1到W。 （我们可以将此扩展模式与添加维度的动态斐波那契问题模式进行比较。）

因此，最多有n*W个独特的子问题。

由于我们只解决每个子问题一次，

运行时间= O（1）* O（nW）= O（n * W）。

- KRoy

---

那是一个很好的解释！ - Aleksandra Zalcman

Answer 4

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class Knapsack {
        double price;double kg;double pricePerKg;
Knapsack(double price,double kg, double pricePerKg){
    this.price=price;
    this.kg=kg;
    this.pricePerKg=pricePerKg;
}
public static List<Double> pricePerKg(List<Double> price,List<Double> kg){
    List<Double> pricePerKg = new ArrayList<Double>();
    for(int i=0;i<price.size();i++) {
        pricePerKg.add(price.get(i)/kg.get(i));
    }
    return pricePerKg;
}
public String toString() { return String.format("%s,%s,%s",price,kg,pricePerKg); }
    public static void main(String[] args) {
    List<Knapsack> list = new ArrayList<Knapsack>();
    double W=50;
    List<Double> price = new ArrayList<Double>();
    price.add(60.00);
    price.add(120.00);
    price.add(100.00);
    price.add(1000.00);
    ArrayList<Double> kg = new ArrayList<Double>();
    kg.add(10.00);
    kg.add(30.00);
    kg.add(20.00);
    kg.add(100.00);
    List<Double> pricePerKg =pricePerKg(price,kg);
    double weightCarry=0,currentWeight=0;
    double sum=0;
    for(int i=0;i<pricePerKg.size();i++) {
        list.add(new Knapsack(price.get(i),kg.get(i),pricePerKg.get(i)));
    }
    Collections.sort(list,new Comparator<Knapsack>() {
        @Override
        public int compare(Knapsack o1, Knapsack o2) {          
             return o1.pricePerKg > o2.pricePerKg ? -1 : o1.pricePerKg == o2.pricePerKg ? 0 : 1;
        }
    });
    System.out.println(list.toString().replaceAll(",", "\n"));
    for(int i=0;i<list.size();i++) {
        Knapsack li=list.get(i);
        weightCarry+=Double.valueOf(li.toString().split(",")[1]);
            if(weightCarry<W) {
                sum+=Double.valueOf(li.toString().split(",")[1])*Double.valueOf(li.toString().split(",")[2]);
              currentWeight=weightCarry;
            }
            else {
                sum+=(W-currentWeight)*Double.valueOf(li.toString().split(",")[2]);
            break;
            }
    }
    System.out.println("Fractional knapsack="+sum);
}
}

时间复杂度接近于O(nlogn)

- Virendra kumar