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

本文探讨无界背包问题的时间复杂度是否真的为O(n×W)。无界背包问题定义为：给定背包承重W和n个物品，每个物品具有价值value_i和重量w_i，需计算总重量≤W时可获得的最大价值，与经典背包问题不同，此处允许重复使用同一物品。

针对该问题，有一种基于动态规划的标准解法：定义函数g:(CurrentWeight, CurrentItem)->MaxRemainingValue，通过遍历物品避免隐式图中的环，进而应用动态规划。以下是该思路的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;
}

// 返回剩余重量能获得的最大价值
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();

    // 所有物品重量为1
    weights = vector<int>(N_ITEMS, 1);

    // 物品价值为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)形式，无环。算法时间复杂度为O(E)，其中E为图的边数。在最坏情况（所有物品重量为1）下，每个顶点(item, weight)平均连接W/2个顶点，此时O(E)=O(W²n)。但网络上普遍称该算法时间复杂度为O(n×W)，理由是每个顶点仅计算一次，这与实际运行数据不符：

从表中可明显看出，当W较大时呈现*O(W²)*的趋势。

有人可能认为这种最坏场景无意义，可通过预处理选择同重量下价值最高的物品，此时最坏场景变为物品重量为[1,2,3,...,n]，此时边数约为O(W²logn + Wn)，算法时间复杂度应为O(W²logn + Wn)而非广泛认可的O(n×W)？

以下是该场景下的运行时间数据：

参考资料：

• [1] GeeksforGeeks 无界背包问题（允许重复选择物品）
• [2] 维基百科 背包问题动态规划预计算算法
• [3] Stack Overflow 为什么背包问题是伪多项式时间复杂度？

内容的提问来源于stack exchange，提问作者F. Bruno Dias