We have a normal knapsack problem but we can choose up to $t_i$ of the $i$-th object. How would you solve this problem with complexity less than $O(V(n + \sigma(t_i)))$ where $n$ is number of objects and $V$ is the total volume?

  • $\begingroup$ It seems the problem is NP-complete if all t_i are equal to 1. $\endgroup$ – gnasher729 Oct 28 '16 at 21:57
  • $\begingroup$ What does $\sigma(t_i)$ represent? $\endgroup$ – D.W. Oct 29 '16 at 5:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.