In the Knapsack Problem, you must pack items from a set of n items in a knapsack without exceeding its capacity in any of the given dimensions. For example, an item may have 4 dimensions that represent weight, volume, cost, and time. The knapsack has a maximum capacity for each of these dimensions that cannot be exceeded. Neither partial items nor multiple copies of items can be selected. An item i has a given value vi where i = 1, , n and we would like to maximize the total value of selected items without violating the capacities. Data for instances with different number of items is provided in an Excel File on Blackboard. Submit a well-written report that includes the following sections: 1) Formulate a mathematical Binary Integer programming model for this problem (Clearly define your decision variables, objective and constraints). 2) Implement the Binary Integer Program using MS-Excel and find the optimal solution using Solver for the instances provided. Include in your report both the Integer Program and the optimal solutions. 3) Develop a Greedy algorithm for the problem and provide Pseudo code for your algorithm. Present the rationale for your algorithms in one paragraph followed by the Pseudo code. 4) Implement the Greedy Algorithm you designed using a programming language of your choice. The data provided will be the input to the program and the output for each data instance needs to be the items selected, and the objective function value produced by the Greedy Algorithm. Report the results of the greedy algorithm. Include the results of your program in the report by taking snapshots of some of the programs output. Note: I encourage you not to hardcode the data into the program so that you can use the same program with different data sets and problem sizes. You may reuse this program for other data instances in future assignments to compare your results to other metaheuristics. Ideally, it is best to have each instance in a separate text file or Excel file that can be passed to the algorithm. However, since this may pose a challenge for some students, it is acceptable to include the data in your code file, but do not make the code itself specifically dependent on the data. For example, do not hardcode the problem size to 10, because you also need to solve problems of other sizes.

v	C1	C2	C3	C4	C5	C6	C7	C8	C9	C10
100	8	8	3	5	5	5	0	3	3	3
600	12	12	6	10	13	13	0	0	2	2
1200	13	13	4	8	8	8	0	4	4	4
2400	64	75	18	32	42	48	0	0	0	8
500	22	22	6	6	6	6	8	8	8	8
2000	41	41	4	12	20	20	0	0	4	4
Capacity	80	96	20	36	44	48	10	18	22	24