给定一个背包重量 W 和一组 n 个项目，每个项目都有一定的值 value_i 和重量 w_i，我们需要计算我们可以从总重量≤ W 的项目中获得的最大值。这与经典的背包问题不同，这里我们允许使用无限数量的项目示例（改编自[1]）。
对于这个问题，有一个标准的解决方案，使用动态编程：而不是创建一个函数 f：CurrentWeight -> MaxRemainingValue，我们创建一个函数 g：（CurrentWeight，CurrentItem）-> MaxRemainingValue，迭代每个项目。这样我们就避免了由 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，因此每个顶点 （项，权重） 平均连接到其他 W/2 个顶点。所以我们有O（E）= O（W·#vertexes）= 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）。
顺便说一句，这里是我为案例权重= [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][https://www.geeksforgeeks.org/unbounded-knapsack-repetition-items-allowed/](https://www.geeksforgeeks.org/unbounded-knapsack-repetition-items-allowed/)
[2] https://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming_in-advance_algorithm
[3]为什么背包问题是伪多项式？