Propose 1 a constructive heuristic to solve the 0-1 Multi-Constraint Knapsack Problem (MKP).

a. The MKP is a version of the Knapsack problem where instead of maximizing the utility of a knapsack subject to a single constraint (e.g., weight) you are maximizing the utility of the knapsack subject to multiple constraints (e.g., weight, volume, radioactivity, etc). Thus, each item will have a utility score u i , and parameter values for each of these constraints (e.g., w i , v i , r i ). (Please note this is not the multiple constraint, multiple knapsack problem from a prior homework. There is only a single knapsack.)

b. The 0-1 MKP focuses on the specific situation where you can either bring an item or not (i.e no duplicates and no partial items.)