1
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Manfred Weis
    Oct 7, 2018 at 12:49
  • $\begingroup$ @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. $\endgroup$
    – Andreas Blass
    Oct 7, 2018 at 19:12
  • $\begingroup$ Have you considered moving this question to cs.stackeschange.com? $\endgroup$
    – S. Carnahan
    Oct 8, 2018 at 16:40

2 Answers 2

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.