1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Hey, thank you so much! That really clears it up. $\endgroup$ Commented Apr 3, 2021 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.