However, when this problem was given at a Codeforces contest yesterday, several people came up with a O(W*n) solution for this problem. 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. 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. 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. The best algorithm I could find on the Internet has complexity O(W*n*log(max(u i)). 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? However, most of those seem to be interested in approximate solutions or performance on random inputs.

This problem is apparently reasonably popular, and there are many articles about it. What is the maximal cost you can get by picking some items weighing at most W in total?

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.

Bounded knapsack problem