# 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.