Suppose we have a sequence of containers each of which contains multiple items. Each item $I\_i$ is associated with an nonnegative weight $w\_i$, a nonnegative value $v\_i$, and $I\_i(C)$ denotes the ID of the container item $I\_i$ belongs to. Given a bag with capacity $B$, the problem aims to select items into the bag without exceeding the capacity $B$ under the constraints that items being selected must come from different containers. Formally, the goal is


$$\text{maximise } \sum\_h p\_h\*v\_h $$
subject to: (1) $p\_h=1$ or 0. (2) $\sum\_h p\_h\*w\_h \leq C$. (3) $\forall j,k$, if $p\_j=p\_k=1$, $I\_j(C) \neq I\_k(C)$.


I know we can reduce the traditional knapsack problem to my problem when the size of each container is 1. But this reduction does not imply that my problem is strongly NP-hard since the traditional knapsack problem is weakly NP-hard. **So my question is: can we reduce a strongly NP-hard problem to my problem?**


Another thing I want to share which is not really relevant though, is that my problem can be reduced to [knapsack problem with conflict graphs](http://www.optimization-online.org/DB_FILE/2008/10/2128.pdf) which is known to be strongly NP-hard.



Is this variant of knapsack problem strongly NP-hard?
The same dynamic programming solution works for your instance as for knapsack.
Just order the elements according to which container contains them.
Then for each weight/value/container\_of\_last\_added\_element triple, you can compute the optimum by dynamic programming.


