无界背包问题的运行时复杂度真的是O(n×W)吗？

Question

给定一个背包容量为W，一组n个物品，每个物品具有某个价值value_i和重量w_i, 我们需要计算出在总重量≤W的情况下可以得到的最大价值。这与经典的背包问题不同，因为我们可以使用无限数量的一种物品（改编自[1]）。

这个问题有一个标准的动态规划解法：我们创建一个函数g: (当前重量，当前物品) -> 剩余最大价值来代替创建一个函数f: 当前重量 -> 剩余最大价值，然后遍历每个物品。通过这种方式，我们避免了g形成的隐式图中的循环，并且可以使用动态规划。C ++中此类函数的一个标准实现可以在这里看到：

#include<iostream>
#include<vector>
#include <chrono>
#define INF (int)1e8
using namespace std;
using namespace std::chrono;

const int MAX_WEIGHT = 10000;
const int N_ITEMS = 10;

int memo[N_ITEMS][MAX_WEIGHT + 1];
vector<int> weights;
vector<int> values;

void initializeMemo(){
    for(int i = 0; i < N_ITEMS; i++)
        for(int j = 0; j < MAX_WEIGHT + 1; j++)
            memo[i][j] = -1;
}

// return max possible remaining value
int dpUnboundedKnapsack(int currentItem, int currentWeight){
    if(currentItem == N_ITEMS)
        return 0;

    int& ans = memo[currentItem][currentWeight];
    if(ans != -1)
        return ans;

    int n_taken = 0;
    while(true){

        int newWeight = currentWeight + n_taken * weights[currentItem];
        if(newWeight > MAX_WEIGHT)
            break;

        int value = n_taken * values[currentItem];
        ans = max(ans, dpUnboundedKnapsack(currentItem+1, newWeight) + value);

        n_taken++;
    }

    return ans;
}

int main(){
    initializeMemo();

    // weights equal 1
    weights = vector<int>(N_ITEMS, 1);

    // values equal 1, 2, 3, ... N_ITEMS
    values = vector<int>(N_ITEMS);
    for(int i = 0; i < N_ITEMS; i++)
        values[i] = i+1;

    auto start = high_resolution_clock::now();
    cout << dpUnboundedKnapsack(0, 0) << endl;    
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cout << duration.count() << endl;

    return 0;
}

该解决方案遍历了一个DAG（我们从不返回任何项，因此这里没有循环，所有边的形式为（item，weight） ->（item + 1，new_weight））。 DAG的每个边缘最多只访问一次。因此，该算法的时间复杂度为O（E），其中E是图的边数。在最坏的情况下，每个权重都等于1，因此每个顶点（item，weigth）平均连接到其他W/2 个顶点。因此我们有O（E）= O（W·＃顶点）= O（W·W·n）= O（W ^ 2·n）。问题在于，无论我在互联网上查找什么，都说该算法的运行时复杂度为O（W·n），因为每个顶点只计算一次[1] [2] [3]。这种解释似乎没有意义。而且，如果是这样的话，上面的算法不应该运行得那么慢。这是算法运行时间×MAX_WEIGHT值的表格（请自行尝试此操作，只需运行上面的代码）：

MAX_WEIGHT    time (microseconds)
       100                   1349
      1000                  45773
     10000                5490555
     20000               21249396
     40000               80694646

我们可以清楚地看到，当W的值较大时，出现了一个O(W^2)的趋势，正如我们所猜测的。

最后，有人可能会问：这种最坏情况非常无聊，因为你只需要对每个重复的重量取最大值即可。确实，通过这种简单的预处理，最坏情况现在变成了重量为[1、2、3、4、......n]的情况。在这种情况下，大约有O(W^2·log(n) + W·n)条边（见下面的图片。我尽力了，希望你能理解）。因此，算法的运行时间复杂度应该是O(W^2·log(n) + W·n)，而不是像几乎所有地方都建议的那样是O(W·n)？

顺便说一句，这里是我得到的weights = [1, 2, 3, 4, ..., n]的运行时间：

MAX_WEIGHT    time (microseconds)
       100                    964
       200                   1340
       400                   2541
       800                   6878
      1000                  10407
     10000                1202582
     20000                5181070
     40000               18761689

[1] 无界背包问题（允许重复选择）

[2] 背包问题-动态规划

[3] 为什么背包问题是伪多项式时间？

- F. Bruno Dias

---

对于大的 n，W*n 占主导地位，而 W^2*log(n) 则相对较小。 - ad absurdum

谢谢，问题应该与n有关，而不是W。 - F. Bruno Dias

我还应该补充一点，使用这里展示的预处理方法，我们可能永远不需要担心 n 大于 W 的情况，因为我们最多只会取 W 个不同的值。所以保留术语 W^2*log(n) 是有益的。 - F. Bruno Dias

Answer 1

你说的没错，你的算法运行时间确实是O(nW²)。下面是一个简单的方法来看清楚这一点：有O(nW)个网格单元需要填充，并且每个单元需要O(W)的时间来处理，因为你最多可以拿W份任意物品。

然而，有一种比你在这里提出的更快的计算答案的方法。具体地说，我们可以通过使用以下见解来消除你代码中的内部while循环。假设你想要使用列表的前n个项目并且有可用容量W来制作最大可能的值。有两个选项：

如果第n个物品的重量超过W，你就不能带走它。最好的选择是从前n-1个物品中获得最大价值，并且重量不超过W。

否则，你有两个选择。你可以说“我对这个物品不感兴趣”，在这种情况下，你将最大化前n-1个物品的价值，并且重量不超过W。或者你可以说“我至少想要其中一个”。在这种情况下，如果物品的重量为w，那么你现在还剩下W - w的重量。然而，你并没有排除使用更多该物品副本的可能性。因此，你可以递归地计算使用重量W - w时从最后n个物品中获得的最大价值，并加上一个物品的价值。

换句话说，与其在每个点上问“我想要多少个这个物品的副本？”，不如问“我是否已经完成了这个物品的副本，还是我想要再多一个副本？”这样可以将表格中每个元素的工作量降低到O(1)，这也是O(nW)运行时间的来源。

- templatetypedef

---

你说得对。我可能应该再看一遍CS 101；( - F. Bruno Dias