0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\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$
    – Inuyasha Yagami
    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

0

Reset to default

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.

Browse other questions tagged or ask your own question.