Variant of the Knapsack Problem I've got problem on integer programming, specifically with the following knapsack problem. I'd be happy to get some suggestions on how to solve the problem in a time efficient way.

There are 120 items $i$, each with weight $w_i$ and the value $v_i$. Each item can be selected only once (or zero times). For each of them one has to chose a quality level ($a$, $b$, $c$, $d$ or $e$).
The higher the level, the higher is its weight and its value. Both are precalculated for all items and stored in matrix.

Now the question is, given a capacity $W$, how to get the optimal levels for each of the items. Since the item set is relatively huge, the aspects of computational complexity might be of special relevant, I guess.

Can you tell me which algorithms can be use for this variant of the knapsack problem? Thanks a lot!
If you set both the values and the weights of each item corresponding to the lowest four levels to $0$, this problem is exactly the standard knapsack problem, so it is no easier than the standard knapsack problem, i.e. it is NP-hard.

You can use the dynamic programming algorithm for the standard knapsack problem to solve this problem, except that you should consider six cases instead of two: the item is not chosen, or its level $a,b,c,d$ or $e$ is chosen, then take the maximum value. The complexity is $O(nmW)$ where $m$ is the number of levels.