I had an online round at a company where I was asked this question.
There are $N$ items, and you have to choose some items from them such that the total weight does not exceed $W$.
Each item has three properties, weight, profit and type. There are only two types of objects.
Type 0 item can be selected independently own their own.
A type 1 item cannot the selected on its own and needs another item of type 1.
Note: The problem does not say if this means what we have to select at least two type 1 items to select any at all, or that all the type 1 items must be in pairs.
Constraints:
$N < 10^3$
$W < 10^5$
$\mathit{weight}, \mathit{profit} < 10^5$
This is obviously (?) related to the knapsack problem, as without the restriction on the type 1 objects, it would actually be the 0-1 knapsack problem. How do I go about doing this? Any help and general ideas are extremely appreciated.