I've got the next problem, where I have two, instead of one, knapsacks. Formally, we have items $1, \ldots , n$ and each item $i$ has a positive integer weight $w_i \in \mathbb{N}$ and a positive value $v_i > 0$. Further, we have two knapsacks of capacities $W_1$ and $W_2$. We need to pack the items into the knapsacks to find the maximum cost of objects that can be packed in both knapsacks.

It’s allowed to break any items between 0 and 1.

Question: Is there any greedy algorithm that solves this problem?

  • $\begingroup$ Simply consider the two knapsacks as one with a capacity $W_1+W_2$. Then apply the standard greedy algorithm for the fractional knapsack problem. $\endgroup$ Jun 1, 2021 at 8:50
  • 1
    $\begingroup$ @InuyashaYagami This sounds more like an answer than a comment! $\endgroup$
    – phan801
    Jun 1, 2021 at 10:55


Your Answer

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

Browse other questions tagged or ask your own question.