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 at 8:50
  • 1
    $\begingroup$ @InuyashaYagami This sounds more like an answer than a comment! $\endgroup$
    – phan801
    Jun 1 at 10:55

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.