# Knapsack on two kinds of objects, where you cannot choose type 2 objects on their own

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.

I think this can be solved the same way that knapsack problem is solved using dynamic programming.

I present the problem for the case where type 1 items are to be selected in pairs, but the other case is solvable in a similar way.

Suppose the weights are $$\{w_1, …, w_n\}$$, the profits are $$\{p_1, …, p_n\}$$ and the types are $$\{t_1, …, t_n\}$$. Let's define, for $$w\in [\![0, W]\!], i \in [\![1, n]\!], j\in\{0,1\}$$, $$K(w, i, j)$$ representing the maximum profit using a knapsack of capacity $$w$$, using items $$1, …, i$$, with a parity of type 1 items equal to $$j$$.

We want to determine $$K(W, n, 0)$$. Using this definition, we can calculate $$K(w, i, j)$$ by distinguishing if we take or not the $$i$$-th item:

$$K(w, i, j) = \max(K(w-w_i, i - 1, j \oplus t_i) + p_i, K(w, i - 1, j))$$ (where $$\oplus$$ is the addition modulo 2)

With this formula, we can then compute $$K(W, n, 0)$$ in time complexity $$O(nW)$$.

In the case you just need to pick at least two items of type 1 if you want any, $$K(w, i, j)$$ could represent the maximum profit with $$j\in \{0, 1,2\}$$ representing respectively exactly zero type 1 item, exactly one type 1 item or at least 2 type 1 items.

• Hey, thank you so much! That really clears it up. – Soumya Pattanayak Apr 3 at 18:34