Multi-dimensional Knapsack with Minimum Value constraints for Dimensions


In MDK, we have a vector $ W = \{W_1, W_2, …, W_d\}$ where each element corresponds to the maximum weight for the respective dimension in the knapsack.

I want to add a conditional constraint: $ V = {V_1, V_2, …, V_d}$ , where each $ i$ -th dimension in the knapsack must have a value sum greater than threshold $ V_i$ . I am not so much concerned with the total value sum.

I would like to show this problem is NP-hard. My intuition is that the additional constraint makes this problem harder than MKD and therefore is NP-hard. But clearly this doesn’t constitute a formal proof.