# 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!

• welcome to MO! I find your question interesting, but I would like to see some clarification regarding the quality levels: what do they affect? You write "the higher the level, the higher its weight and value"; are weight and value the same or different properties that happen to have equal value? If you could provide a linear programming formulation of your problem, that would surely enhance your question and more likely generate the feedback you are looking for. – Manfred Weis Oct 7 '18 at 12:49
• @ManfredWeis I conjecture that the "weights" are the things whose total is to be bounded by the "capacity" $W$ and that the "values" are the things whose total is to be maximized for "optimum levels". I agree with you that this (or whatever connection the OP intended between weights, values, capacity, and optimization) should be specified in the question. – Andreas Blass Oct 7 '18 at 19:12
• Have you considered moving this question to cs.stackeschange.com? – S. Carnahan Oct 8 '18 at 16:40

## 2 Answers

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.

Your basically want to solve a variant of the 0-1 Knapsack problem. Your variant includes the following changes to the standard problem: for each item instead of one set of $$[wi, vi]$$, you have five sets corresponding to each of the quality levels.

Normal 0-1 Knapsack can be solved using dynamic programming in $$O(nW)$$ time and $$O(nW)$$ space where $$n$$ is the number of items and $$W$$ is the size of the Knapsack.

In your case, the complexity will be $$O(nqW)$$ time and $$O(nqW)$$ space where $$q$$ is the number of quality levels. If $$q << n$$, then we are back to $$O(nW)$$ time and $$O(nW)$$ space.

Refer this handout for a quick brush-up on the actual recurrence relation.