How to solve this optimisation problem when I have varied profits associated with different bags?

46 Views Asked by At

Recently I came across an optimization problem. Suppose we have $n$ bags each with varied capacity say $c_j$ i.e. capacity of $j$th bag and $m$ items. There can be multiple instances of these $m$ items say $q_i$ i.e. the total quantity of item $i$. Now a particular item or multiple instances of the same item can be placed in one of the $n$ bags. There is a profit associated with these $n$ bags when an item is placed in it but this profit for an item will be different for each bag say $p_{ij}$ i.e. profit of item $i$ in $j$th bag. Now I have to maximize the profit. I know that $0 \text{-} 1$ multiple knapsack is NP hard. But I have no clue with this problem.