I had a 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 3 properties, weight, profit and type. There are only 2 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 atleast 2 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$

$weight, 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.

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.