Integral bounded knapsack problem solvable in O(knapsack_size*num_of_items)

The bounded knapsack problem is: you are given n types of items, you have u_i items of i-th type, and each item of i-th type weighs w_i and costs c_i. What is the maximal cost you can get by picking some items weighing at most W in total?

This problem is apparently reasonably popular, and there are many articles about it. However, most of those seem to be interested in approximate solutions or performance on random inputs. But what if we want to treat it as a usual algorithm problem - what is the best possible worst-case running time for solving it?

The best algorithm I could find on the Internet has complexity O(W*n*log(max(u_i)). It goes like this: instead of having u_i items of type i, we create several new types that are multiples of type i, for example items with weight 2*w_i and cost 2*c_i, then the same for 4 and so on, and declare that we have just one item of each type. We create the new types in such a way that the number of new types is logarithmic, and anything that was possible to represent using the old items is also representable using the new items and vice versa. We get a 0-1 knapsack problem with n*log(max(u_i) types which leads to a dynamic programming solution with the above complexity.

However, when this problem was given at a Codeforces contest yesterday, several people came up with a O(W*n) solution for this problem. First, we start with the standard dynamic programming solution: let dp_k,w be the best cost that we can get by packing the total weight of w using the first k item types. Each new type is then handled as follows: dp_k,w=min(dp_k-1,w, dp_k-1,w-wk+c_k, ..., dp_k-1,w-uk*wk+u_k*c_k). This dynamic programming has O(W*n) states, and each state is processed in O(max(u_i)).

But we can process each state in O(1) amortized time! Let's take a look at the above recurrence. First, we notice that we can separate all values of w into w_k groups, based on the remainder of division on w_k, and those groups can be handled separately. Then, for each group, the problem we need to solve is to find min(a_i, a_i-1+c, a_i-2+2*c, ..., a_i-k+k*c). By setting b_i=a_i-i*c, this expression is transformed into min(b_i+i*c,b_i-1+(i-1)*c+c, ...), which is just i*c+min(b_i, b_i-1, ..., b_i-k). Thus our problem is reduced to finding minimums of groups of k+1 consecutive numbers in a given array.

And this, in turn, is a well-known problem that is solvable in O(size of array) using one of the two methods: we can either maintain a sequence of incremental (from the end) minima for a segment of size k+1 and update it quickly when we shift one position to the right, or we can just separate the entire array into blocks of size k+1, and calculate the prefix and suffix minima for each block - this allows to find the minimum for any block of size k+1 by splitting it into two blocks with precomputed answers.

Is it well-known that bounded knapsack is solvable in O(W*n) worst-case?